MikeMirzayanov's blog

2013-2014 CT S01E09: Codeforces Trainings Season 1 Episode 9
By MikeMirzayanov, 11 years ago, translation, In English

Welcome to 2013-2014 CT S01E09: 2011 German Collegiate Programming Contest (GCPC 2011) + GCJ 2009 R3 C-D. The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

The registration will be available on the Gym page and will be opened until the end of the training. Be careful registering team: please, choose only whose members who will take part in the contest.

Good luck!








  • Vote: I like it
  • +72
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suffix tree -_- I give up on you -_______-

    → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Does it mean problems will be about suffix trees?

→ Reply
»
11 years ago, # |
  Vote: I like it -13 Vote: I do not like it

What does the picture talk about? A book with Suffix Tree or some Suffix Tree problems?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D I used 12! permutations and checking the validity of permutations, Does not anybody has some smarter solution for this?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice idea :) Thank you :)

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good solution, but still wondering, what's wrong with mine..

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much for your help!

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      WAT? Backtrack got AC :|? It seems that tests weren't generated properly :P. There exists a linear solution (which I haven't found)!

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any clue for problem L? I am totally out of ideas.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Two things:

  1. problem analysis of A-J: here

  2. 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).

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It looks like he spent the first 4 hours to code and then submitted all of them later lol =)

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
I found some team include mine couldn't accept the problem K because WA on test 5. I want to know the reason, THANKS. My algorithm is about Perfect Elimination on a chordal graph.
→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Im sure N is big in the problem and your factorial-computing function causes stack overflow.

    → Reply
»
11 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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...

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you suggest me well-prepared Polish ACM-ICPC contests (differ from CERC)?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By the way, can you clarify, what that statement in B mean? As for me, I still don't get it.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is analysis only in German for E. Can anybody explain solution(at least briefly)?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I usually write checkers by myself if they are absent. Regarding to GCPC 11, possibly, I've asked jury members.

    → Reply