SRM 572: hmnn

As I write this around the end of the challenge phase. I can tell for sure that I solved the easy problem correctly. The medium one is a bit more of a mystery.

Div1 500: The one with digits

You have a set of guesses for a number of at most 9 digits. For each guess, you also know the number of correctly guessed positions it had. If there is a unique result for the number, return it. If there are no results, return "Liar", else return "Ambiguity".

This was looking tough until I noticed that the number of digits is at most 9. It is large for trivial brute force, but not TOO MUCH larger.

My first approach was optimized backtracking. Makings sure to crop the search whenever there is certainty a digit position would be wrong.

It is also necessary to cut the search whenever you find more than one result.

First tests seemed promising. But I was able to come up with a test case that made it time out. (A Liar case).

But it seems unlikely that a non-"Liar" case would require many steps. So I added something that stops the search if it had too many iterations. Then it instantly returns "Liar".

This makes the approach at least hard to challenge. I wonder if it can beat system tests. To reduce the probability of a crafted case laying in the system tests, I made it randomize the order in which it picks the characters ^^.

Update: As I write this post, I failed this problem in the system tests. The writer found a case that is not Liar and has a solution further away from the ones I try.

Div1 250: The one with strings

Your oldPassword must be changed in a way that the K first characters are equal to the K last characters. Return the minimum number of characters to change.

When the K first and last characters do not overlap, this is kind of trivial, you got two strings that have to be the same.

When they overlap, it is a bit different. For example: "lol" and K=2. This time all of the characters have to be the same.

I think that because I once wrote a problem that had a similar solution, I decided to use DFS right away. Each letter belongs to some group of letters that must be made equal. Then for each group, it is easy to pick a letter that minimizes the cost - the one that appears the maximum number of times.

It works as follows:

For each i (Between first K or last K characters): If i is less than K, it is connected to another character in the last K characters. And vice versa. Each connected component must be equal. We can use a Depth-First search to find each of these components.

This problem was enough to have a relatively good result. My prior experience writing for that netease contest receives all the credit.

Challenge phase, comments, etc

I found a submission for the medium problem that had the simple brute force I tried at first. The one without cutting the number of tries. Even though I had the challenge case prepared, I took too long to paste it. A red coder got those 50 points.

It was a good match. Good to see optimized brute force does not pass easily in the medium problem.