Wednesday, November 21, 2012
Saturday, November 17, 2012
Joy of solving easy problems
The similarity of two strings is defined as the length of their longest common subsequence. That, in turn, is defined as the longest string that can be obtained from both strings by dropping some characers. For example, the similarity of strings CATGT and GACTT is 3, as they have common subsequences of length 3, ATT and CTT, but no common subsequence of length 4.
You are given a string consisting of letters A, C, G, T (by far the most popular background for string problems these days :)). You need to find another string consisting of those four letters, and of the same length as the given string, that is least similar to the given string. Of course, there might be many such strings - for example, for CATGT discussed above there any many strings of the same length with similarity 1, like GAACC or TAAAC.
Can you solve it quickly?
This problem is not difficult, but I've enjoyed receiving "Accepted" from the judging system for this problem a lot. Most contests need easy problems, and it is so much better when those problems are not "easy because you just have to implement what's described in the problem statement", but "easy because you can just figure it out quickly".
Saturday, November 10, 2012
Results of "kill backtracking" contest
The best testcase was actually found quickly - on the same day I've posted the contest to my blog, June 11, 2010. Here it is:
...2...
.2.....
.......
.......
.......
.....8.
.......
The trick is: we set up a pattern that has many possible solutions in the upper-left corner - but, all of those solutions but one require more than two stars. And we only have two stars available here because we have an 8 in the bottom-right corner, and just 10 stars in total - but the algorithm doesn't know and thus it tries different possible allocations of stars around 2s, then tries all possibilities for places where we don't have any adjacent digit - meaning we're free to put or not put a star there, only to find out in the end that there's not enough stars left.
This testcase requires 730272354 recursive calls. It was found by Dimon.Sobolev, felix.halim, Max.Khodak, shd, endagorion, merettm and mbuzdalov, in that order - congratulations!
The next best testcase found requires 629909575 calls:
I know it's been a long time, but if any of the participants remembers anything about the contest, I'd like to hear your impressions :)
Here is the breakdown of the contest website visits by country:
Saturday, October 27, 2012
Petr Mitrichev Contest 10 solution ideas
You can still solve the problems for practice at http://codeforces.com/gym/100110, and you can even start a virtual contest when you'll see that standings of other teams as they appeared at the particular time into the contest.
When making this contest, I've tried to add a flavor of exploration (as opposed to just using standard algorithms), since that actually resembles my work quite a bit. Please tell whether you liked that or not!
In particular, I like problem C the most, and I'm pretty sure it can be solved for 8x8, 10x10 or even 20x20 fields - but I don't know how. We can probably set up a challenge to solve it for 10x10. My feeling is that some statistical methods should be the most powerful here.
Here are the solution ideas. Those are not complete solutions, but I hope they can guide you in the right direction. Problem statements can be found here. You can also find a video of myself doing analysis of this contest (without problem G) in Russian at http://youtu.be/FN6FRXiQ7JE. Please don't read below if you still want to try solving those problems yourself :)
Problem A. Asymmetric Art.
This problem can be solved with backtracking. The straightforward backtracking tries all possible subsets, but that's obviously too slow. We can do several optimizations: first, let's consider the numbers in increasing order, and when taking each number we can 'mark' all numbers that we can't take anymore because of this new number. This is not fast enough, but we can additionally truncate our search by saying 'if we've reached number x, then we'll take not more than answer[n-x] more numbers', where answer[y] is the number of items in the largest quasi-symmetric-triple-free subset for n=y. Then we can find all answer[] values in under one minute, and then send a program that has all answers hardcoded for judging.
Problem B. Lots of Combinations.
We need to do two things: find (n,k) modulo 10**10, and check if (n,k) is greater than or equal to 10**10. The second part is relatively easy - if k <= n-k, then we can incrementally compute (n,1), (n,2) and stop as soon as we exceed 10**10. For the first part, we notice that it's enough to compute the answer modulo 2**10 and modulo 5**10, and then use the Chinese remainder theorem. Computing the answer modulo 5**10 is done by first calculating the power of 5 in (n,k) separately, and then calculating (n,k) with all powers of 5 removed from all numbers using the fact that we can now use division and thus just need to calculate factorials (skipping numbers divisible by 5) modulo 5**10, and numbers modulo 5**10 is a periodic sequence.
Problem C. Curiosity.
I'm pretty sure there are lots of different approaches that work in this problem. The two main directions I'm aware of is finding large blocks of data without unknowns and combining them together, or using various dynamic programming approaches that consider all possibilities. My solution is of the second kind: assume we've chosen the 6x6 field. We can then use dynamic programming to find the minimum possible number of contradictions in the input data (places where we know the color of some cell but it's different from the actual cell we're on). Now I use simulated annealing to find the 6x6 field that has zero contradictions. Of course, since all input files are given to you, you can do this without any time or memory limits and then just submit the discovered answers.
Problem D. Domination.
Since one of the dimensions is small (up to 10), we can do dynamic programming using a cut in that dimension as our state. More specifically, suppose we have filled first k columns and first p cells in the (k+1)-th column. Then we're only interested what happens on the first p cells in the (k+1)-th column and the last (n-p) cells in the k-th column. Each cell can be in four states (has '1', has '2', has '0' and doesn't have an adjacent '2', has '0' and already has an adjacent '2' (let's call this state '3')), yielding 4**10=2**20 states, but it turns out we don't need all of them - some pairs of adjacent cell states are not useful: '21' and '11' can always be replaced by '23', and '20' is plain impossible. That brings the number of states down significantly, but the program is probably still too slow. The final touch is to notice that things become periodic if we fix n and increase m.
Problem E. Easy Learning.
This one probably has even more different solutions than C. There is a lot of theory for this kind of problem that I don't want to recite here, my solution was using gradient boosting.
Problem F. Hash.
There are two main approaches here. One is called Pollard's rho algorithm, and does not depend on the hash function much, the other actually uses the specific hash function we use. Consider values x_i = hash('1000 zeroes but i-th character is 1') - hash('1000 zeroes'). Then we need to find two disjoint subsets of x_i with the same sum. Let's do the following trick: sort all x_i, and take y_1=x_2-x_1, y_2=x_4-x_3, y_3=x_6-x_5, and so on. It's not hard to see that now we have 500 numbers (2 times less), but the numbers themselves are about 1000 times less on average, and we still need to find two disjoint subsets with equal sums. Repeating this several times gets us numbers that are so small that two of them are bound to be equal. This problem has some very tricky cases when b=2 - you should watch out for those!
Problem G. RLE Size.
Here, you just need to carefully consider all cases. Each block of consecutive '?' signs can be solved on paper, based on what's to the left of it and what's to the right, and then you can just implement the formulas you've discovered on paper in your program.
Problem H. Good Students and Bad Students.
This problem can be solved greedily. Let's go from the highest numbers to the lowest numbers, and gradually fill all groups. Whenever we encounter a student that wants to be in the upper half, we place it in the first upper half that still has empty slots, if any. Whenever we encounter a student that wants to be in the lower half, we place it in the first lower half that has the corresponding upper half completely filled, if any, and in the first free upper half slot otherwise. The proof is a bit tricky but doable.
Problem I. Tennis Scores.
This was the classical 'long statement, straightforward but long code' problem. You just had to carefully calculate the probabilities of game outcomes for each player's serve, then use those to calculate the probabilities of set outcomes, and then use those to calculate the probabilities of match outcomes. It's important to notice that set outcomes depend on who's serving first in the set.
Problem J. Three Squares.
This problem was supposed to be solved numerically. One step that you need to make to avoid falling into a trap is to realize that we're not always rotating all three squares by the same angle, however improbable that might look. Here's an example:
Then you could either just iterate over possible rotation angles with a reasonable step and check whether there's intersection (since all coordinates are integers, there's no possibility to create a particularly nasty case for that solution), or, if you want a more robust solution, you can do a search in the 3-D space of angles that repeatedly splits the search space in two, but then throw away certain branches when we can see that for all possible triples in that branch there's still an intersection.
Thursday, October 25, 2012
Petr Mitrichev Contest 10 - this Saturday!
The contest will be held at http://codeforces.com/gyms. In order to take part, you need to have an account on codeforces.com. Both teams and individual participants can join. The contest itself will be at http://codeforces.com/gym/100110, but this link will be accessible only after the start of the contest.
There will be 10 problems of varying difficulty (most are quite difficult) for 5 hours. Your solution needs to be correct on all test cases to be accepted (the standard ACM ICPC rules). People will be ranked by the number of solved problems, and by total penalty time in case they're tied on solved problems, so don't be late! :) Note that in each problem you need to read the input from a file and write the output to another file - so don't read from stdin and don't write to stdout!
Feel free to ask any questions that you might have, and also please tell if there are any issues with the contest system - it's the first time I'm using codeforces.com/gyms.
Monday, October 22, 2012
Time and venue for Petr Mitrichev Contest 10
Wednesday, October 3, 2012
TopCoder Open 2012 Finals Commentary
16:09 - That's it about this TCO. See you next year! Feel free to ask me questions in comments, I'll do my best to answer.
15:57 - Marathon results! ainu7 is the champion, Psyho is second!
15:54 - Algorithm results! Both 500s and ACRush’s 250 fail. Egor, meret, RAVEman are the only non-zero scorers, in that order. Egor is the champion!
15:48 - They’ve announced design results (which were alredy known in advance), now development.
15:31 - I've taken a look at RAVEman's and andrew's 500s, and they both only consider moves by small_constant*first_vector+other_small_constant*second_vector. I fear that doesn't work for the following reason: when the vectors are very long, close in length to the size of the board, there can be two cells that can only be reached from one another via a linear combination with larger coefficients. So I'd bet on both 500s failing.
15:29 - They are starting announcements, but they usually do other tracks first and algorithm last.
15:21 - Waiting for systest. Currently RAVEman with just 500 first, andrewzta with just 500 second, Egor, meret and ACRush with just 250s from third to fifth. Let's hope at least the champion has one working problem :)
15:18 - ACRush one more -25 on RAVEman's 500, kills RAVEman's 250, -25 on meret's 250. Meret has got -25 on both standing 500s.
15:18 - Egor has got -25 in the meantime as well. Still above meret.
15:17 - And gets -25. Meret is also preparing the testcase for RAVEman’s 500.
15:15 - ACRush is preparing a testcase for RAVEman’s 500.
15:13 - assuming both remaining 500s will also fail, it's Egor vs meret challenge battle. Both have made their moves, still less than 50 separates them. ACRush gets -25 on Egor's 250.
15:10 - meret bring’s down marek’s 250, RAVEman brings down iwi’s 500, Egor brings down Andrew’s 250.
15:08 - admins are giving out a prize for another contest during intermission, using loudspeakers. What an AWFUL decision!
15:07 - RAVEman preparing a large and presumably tricky case for 500.
15:05 - iwi submits 500 but I'm not sure he has at least tested for TLE.
15:03 - marek.cygan doing nothing, meret writing his 1000, his solution has “layers” in it - we had an idea that involved layers, too, so that can be a correct solution.
15:02 - most people fight with not-passing-examples in 500.
15:00 - apparently RAVEman's 250 is wrong, and he's fixing it... And he resubmits!
14:59 - five minutes before the end. Marek has submitted and resubmitted his 250. I’m betting on many last-second submissions.
14:52 - actually nika’s hypothesis seems to be true and it’s even not hard to construct that ordering: let’s try all possibilities for the first vertex. Then, at every step the next vertex can be constructed by doing the following: if a vertex has more edges to the already constructed vertices then it’s closer to the last marked vertex. Also, if a vertex has less edges to the vertices yet to be constructed, then it’s also closer to the last marked vertex. And the only way both those numbers can be the same for two vertices is when they’re isomorphic. So we just reconstruct the ordering greedily.
14:45 - meanwhile, andrewzta and RAVEman have submitted the 500. I have a bad feeling about andrewzta's one, though, as he has probably patched his solution quickly to pass the sample case but he couldn't rewrite a large part of his solution since I've seen it.
14:44 - if that's true, then the solution is to handle groups of isomorphic vertices at once, and then the number of states will be really small - just linear.
14:42 - nika has the following conjecture for 1000: omitting isomorphic vertices, the ordering of vertices is uniquely determined up to a complete reversal.
14:41 - andrewzta's medium seems far from completion - he iterates over pairs of vectors but his check if the given pair of vectors gives a symmetry is too simple.
14:38 - shangjingbo’s 1000 is not working only on the last example case, which is huge. Poor guy :(
14:34 - RAVEman optimizing his 500, it’s working in 0.9s on what seems to be close to worst case. Will he submit soon?
14:29 - ACRush coding 500, meret coding 1000.
14:27 - Rustyoldman reports that iwi and andrewzta are coding their 500s.
14:18 - Meanwhile, ACRush resubmits 250. Current standings: Egor (with resubmit), RAVEman and meret (no resubmit), andrewzta and ACRush (with resubmit). ACRush has also opened the 500. RAVEman is coding on 500 and shangjingbo is coding on 1000.
14:15 - About 1000: maybe something like this can work - let’s start putting numbers from 1 to N. After we’ve put numbers from 1 to K, all that matters is which vertices are assigned the last D numbers, and which vertices have an assigned number at all. And because of the restrictions, I’d hope that the number of states will be quite small. But I’m not sure how to estimate that.
14:08 - Rustyoldman reports that nobody is still coding on 500 or 1000. meret submits 250.
14:06 - By the way, bmerry was test-solving 250 and 1000 in this round, and it took him 12 and 44 minutes respectively.
14:05 - RAVEman submits 250 as well. I’m trying to think about 1000...
14:02 - andrewzta submits 250, iwi gave up on 1000 and opened 500. ACRush went to 1000 after 250. Marek.cygan gave up on 500 and went to 1000. It’s 25 minutes into the contest and it’s weird we have just 3 submissions on the 250.
13:58 - about 250: First, we can forget about E by XORin S and E, and just making player A’s goal to achieve all zeroes. How can player A win? The only way is that the entire string has just one segment of consecutive ones. But how could B allow to make that happen? If the string has length of at least 5, it looks like B can always prevent that on his move, so when length is at least 5 we should just check if A can win in one turn, and when length is at most 4, the number of states is just 16 and we can analyze the entire game using the usual means.
13:55 - meanwhile, Egor submits and resubmits the easy, adding one more small “if” clause, ACRush submits the easy a bit later but has higher score because of Egor’s resubmit. Everybody who’s opened 500 and 1000 is working on paper.
13:51 - I’ve test-solved 500 before this contest. The basic idea is - any good tiling is defined by two “basic” shift vectors. In fact, if we fix the two basic shift vectors, then all vertices are split into groups of equal vertices, and we just need to check that all vertices in each group have the same color (it won’t be a problem to form a connected piece afterwards). Now all that remains is to iterate over all possible pairs of shift vectors and carefully check everything. This can be simplified further by noticing that we can always choose one of the basic vectors to be horizontal (but it might be up to size^2 in length then).
13:50 - formal problem statements: http://apps.topcoder.com/forums/?module=Thread&threadID=763920&start=0&mc=2.
13:47 - 500: A good tiling of the plane that is split into grid cells that are colored black or white is such tiling where each piece is a connected block of cells, all pieces are equal (will coincide after some transition), including colors, and the tiling itself is periodic (for each three tiles X, Y, Z there’s a tile at Z+(Y-X)). What is the smallest possible size of piece of a good tiling which has a given rectangle as its part?
13:45 - 1000: you are given a connected undirected graph with M vertices, and must assign distinct numbers from 1 to N (N >= M) to its vertices so that adjacent vertices have numbers differing by at most D, and non-adjacent vertices have numbers differing by at least D+1. How many ways are there to do that? N is up to 100, M is up to 50, D is up to 8.
13:43 - marek goes for 500, iwi and shangjingbo go for 1000, everybody else for 250.
13:41 - 250: you are given two strings S and E of the same length, consisting of ‘0’ and ‘1’ characters. Player A can (but is not forced to) choose its substring and change all ‘0’s to ‘1’s and vice versa. Player B can (but is not forced to) do the same for just one character. Player A’s goal is to obtain string E, and player B’s goal is to prevent him from doinh so. What is the minimum number of turns he needs (assuming both play optimally)?
13:37 - everything looks fine this time. Two minutes before start!
13:35 - based on this, spectators propose a new strategy: if meret and ACRush submit a problem very quickly, code maximum flow _before_ opening it :)
13:34 - ACRush has apparently been coding most of this time, implementing Dinic algorithm for maximum flow.
13:28 - not much happening now, people are relaxing, admins say everything will be fine this time :)
13:17 - Egor and andrewzta playing air hocket. Meret, [[iwi]] walking around the room. marek.cygan talking with friends. ACRush looked at something on a laptop and went walking with a surprised face. RAVEman talking with friends as well. Can’t find shangjingbo in the arena.
13:14 - the problems turned out to be more serious than expected. The new start time is 13:40. Hysterical laughing from contestants :)
13:12 - it looks like the contest won’t start at 13:15, too. The technical issues still unresolved. This must be a very nervous time for all contestants.
13:05 - admin announcement: The match will start at 13:15.
13:02 - Egor and andrewzta are playing "Cities": each player should name a city that has not been named before that starts with the last letter of the previous named city. So far: Moscow, Warsaw, Wrozlav, Voronezh, Hurghada, Athens, Sarajevo, Osaka, Astana, Amsterdam, Malmo, Orel, Ljubljana, Astrakhan, Novosibirsk.
13:00 - marek.cygan: "The winner will be the one who can find the problemset".
13:00 - 250, 500, 1000. No news on contest start time.
12:59 - it looks like the contest start is postponed, there’re some technical issues.
12:49 - 10 minutes before the start. Andrewzta showed up, now almost everybody is coding the easy problem from the wildcard round for practice, except meret who’s writing max flow again.
12:44 - Everybody is preparing except Egor and andrewzta - the two Java coders. One doesn’t need much preparation when there’s no necessary bolierplate :) Egor is already ready, andrewzta not yet here.
12:35 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Finals. The round will start in about 25 minutes. I will update this post with new comments.