Добро пожаловать на 2013-2014 CT S01E09: 2011 German Collegiate Programming Contest (GCPC 2011) + GCJ 2009 R3 C-D. Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.
Так как это тренировка, то возможно набор задач будет расширен, если для значительного количества участников он окажется простым.
Регистрация на тренировку будет доступна со страницы Тренировки и будет открыта до окончания тренировки. Регистрируя команду, выберите именно тех её членов, кто будет писать тренировку.
Удачи!
I just realized that since I moved from summer to winter time, the contest starts unpleasantly earlier. Damn it.
Great pic, btw. Suffix trees: so simple! :D
Suffix tree -_- I give up on you -_______-
Does it mean problems will be about suffix trees?
What does the picture talk about? A book with Suffix Tree or some Suffix Tree problems?
For Problem D I used 12! permutations and checking the validity of permutations, Does not anybody has some smarter solution for this?
If you choose 7 values (let's say the first seven minus the pre-defined ones), you can solve a system of equations and obtain the remaining 5. So it's enough to consider at most
possibilities for those, and check the validity.
Nice idea :) Thank you :)
To get the lexicographically smallest solution, we should choose 7 special points. If I index all 12 points from up to down and from left to right, we should choose 1, 2, 3, 4, 6, 7, 9. Am I right? Sorry for my poor English.
You can generate permutations step by step and check lines when they are filled. In my solution I checked first line after fixing just 5 numbers, second — after 8 and so on.
Sooo, it's finally over and I can ask questions. In the problem B I used dynamic programming to search the largest common substring: dp[i][j] = (similar(s1[i],s2[j]) ? dp[i-1][j-1] + 1 : 0). But I got WA 7. Is the idea wrong?
Not sure, but given the constraints and time limit, it was enough to write an O(N2) bruteforce (try all possible shifts of the 2nd string with respect to the 1st one, find the overlapping parts and count their longest common substring in just 1 linear pass).
Good solution, but still wondering, what's wrong with mine..
it should be correct, I had same implmentation for this. see http://ideone.com/0yTgsj
initially I was also getting WA 7. Reason being for odd n, I was understanding the atleast half part wrongly.
Initially I had something like if(ans>=(n)/2)puts("POSITIVE"); else puts("NEGATIVE");
I changed it to if(ans>=(n+1)/2)puts("POSITIVE"); else puts("NEGATIVE");
and it got accepted :)
I had "if (ans*2 >= n)".. With your condition no improvement as well :( By the way, there was nothing in the statement about it. Strange as for the pedantic Germans. But, anyway, thanks.
UPD I found the mistake: i didn't assign zeroes to dp[] array for every new test case. Kind of annoying :( Thanks for your code, I wouldn't have found the error without it.
Does anybody know the solution for problem K? I had an idea which was based on the fact that the answer is at most 3 (I noticed some triangle pattern in the corresponding graph), but I can't seem to get past test #5. Thanks in advance.
The graph will be planer graph , so according to map coloring theorem at most 4 color will be needed . So , by using backtracking + prunning you can check for at most 3 color, otherwise ans will be 4 .
Thank you very much for your help!
WAT? Backtrack got AC :|? It seems that tests weren't generated properly :P. There exists a linear solution (which I haven't found)!
Any clue for problem L? I am totally out of ideas.
Well.. There is no problem for ideas, there is many problem to write it:) First off all, let's create a solution if we can solve problem by O(n), where n — number of palindromes. Let's called d0 — number of positions where even number of palyndromes in prefix, d1 — number of positions where not even number of palyndromes in prefix. It's easy to understand that total numbers of good subranges is d[0]*(d[0] — 1)/2 + d[1]*(d[1] — 1)/2; OK. How to find d0 and d1 faster? Try to solve it fast for range 10^(k — 1) ... 10^k — 1, that is to all numbers lenght k. Let k is not even, note that if we know last palyndrome and his middle was not '9', we know where is next palyndrome — for distance 10^((k — 1)/2). We can check that all positions before palyndromes with it middle '1', '3', '5', '7', '9' in d1, another in d0.
But i totally don't know how to write all it fast.
Two things:
problem analysis of A-J: here
evandrix sure is amazing here for a green coder: he submitted 10 problems at once and only got 1 WA (and even that on sample).
It looks like he spent the first 4 hours to code and then submitted all of them later lol =)
I am newbie in sport programming. Couldn't you help me, what's wrong? How to improve this code for problem A? It talks "Runtime error on test 2" http://pastebin.com/4VCEB30Q
Im sure N is big in the problem and your factorial-computing function causes stack overflow.
Emmm... Excuse me, could you tell me, how that has happened that during the training so many people got B accepted? Have you got another problem description than me? Or some kind of clarification which was not showed to virtual participants? "Regions of equal length of DNA strings are similar to each other, whenever |(a[i] − b[j])| ≤ 1, where a[i], b[j] are lower-case letters." — this is the worst problem statement I have ever read. Today, some teams from University of Warsaw trained on this problemset and no one understood it properly. Few teams tried many possibilities and coded few different programmes for few different interpretations of this statement and finally got AC but this is ridiculous. And E — maybe even more ridiculous description. Note to self — don't ever train on German problemset — really poor problems (only G required any creativity but still it's not an excellent problem) and statements of B and E were so utterly messed up...
Could you suggest me well-prepared Polish ACM-ICPC contests (differ from CERC)?
In my opinion all contests prepared by University of Warsaw are really good. Enjoyable problems and clear statements. AMPPZ (Polish Collegiate Programming Contest) in 2011, 2012, 2013 were prepared by UW and I think that these are really good contests.
By the way, can you clarify, what that statement in B mean? As for me, I still don't get it.
There is analysis only in German for E. Can anybody explain solution(at least briefly)?
The biggest difficulty in this task is to guess the right description, because it is not written anywhere :P. What you should guess is that order in this task matters. If you create B and C from A it is important that B is on left and C is on right (can anybody point me where it is written in statament? I don't think so). And resulting order should be as in the output string. No more diamonds are allowed. If you figure out this statement, the rest is realy easy. Just compute a table dp[i][j][c] which denotes "least cost which lets you transform diamond "c" into whole substring of resulting string from i-th to j-th letter. This can be easily done in O(l^3*r).
Thanks! It's really difficult to understand this task in right way(we haven't done it:) ). But why does this solution work fast? C*L*R*(N^3) — it seems to be large number of operations(even with /4 because of inner loops).
Excuse me, but where did you get checkers and jury solutions for GCPC 11? They're not published on the official constest page. I'm asking, because I tried to create the training in the Gym based on GCPC 12, and faced the absence of checkers.
I usually write checkers by myself if they are absent. Regarding to GCPC 11, possibly, I've asked jury members.