Polichka's blog

Codeforces Round #106 (Div. 2)
By Polichka, 13 years ago, translation, In English

Hello everybody!

Today Codeforces Round # 106 for Div2 participants will be. And all who wants can take part in this competition. You will have the opportunity to break from parents with Peter, to learn some interesting facts about the Martians and to solve, of course, interesting problems for you as we hope.

This round has been prepared by a team of three people: Gerald, NALP и Polichka. We express our gratitude for their help to Artem Rakhov (RAD), Mike Mirzayanov (MikeMirzayanov) and Maria Belova (Delinur) .

Score distribution: 500-1000-1500-2500-2500.

Good luck and high rating to all!

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

Comments Comments (59)
| Write comment?
»
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I love this normal Score distribution, last contest is really unfair ...

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

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

      However, i mean 500-1000-1500-2500-2500, not participants rating distribution.

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

good luck everybody

→ Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

I like the problmsets, thank you, Gerald NALP and Polichka. Wait for the editorial.

How to solve problem D and E? Would someone give me a hint? Thanks.

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

    D: f(i,j,x,y) = number of possible coloring sequence i..j, with i having color x and j having color y

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

      How to deal with the conditions? condition 2: A matched pair can have exactly one color. condition 3: No two neighboring colored brackets have the same color.

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

        In short: when you found some neighbor brackets, check them. When you found 2 matching brackets, check them.

        A bit more details (I may forgot some cases): When i and j are matching brackets, f(i,j,x,y) = sum( f(i',j',x',y') )

        --> you consider x & y, x & x', y & y' if they satisfies conditions

        When i and j are not matching brackets, f(i,j,x,y) = sum( f(i,j',x,x') * (f(j'+1,j,y',y))

        --> you consider x' and y' if they satisfies conditions.

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

    for D, my idea was a DP. Scan from left, chose matching brackets. Color them in colors which are allowed, Now rest of string are divided in two parts. Solve them recursively.

    Example : (()()()())()()()()(()) gets divided into ()()()() and ()()()()(())

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

this contest I have the same problem, as last div2: after I submit my hack, nothing happens, and even page doesn't reload, but hack is submitted well

Firefox 10.0, Ubuntu 11.10

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

    Same here (Firefox 11.0 beta, Windows 7).

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

    I failed to submit solution to A at the first time, i.e. I did submit but it seems the server didn't receive it.

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

Most points from hacks in this round (800)? =D

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

    You were lucky with the room.

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

      Really? I see 10 (more than my successful challenges) unchallenged solutions for problem 2 which failed the system tests (including yours) in your room =)

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

        You are right, I'm just kinda dumb :\

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

          Hey, I didn't mean it like that =/ Also, there were 6 solutions that failed system tests in my room, so I missed a large number of them, I can say I had some luck to have 14 wrong solutions in my room, in that specific problem.

          Btw, at first I submitted a solution that gave the wrong answer for 0:10 but it passed pretests, that's why I managed to make so many hacks, because I knew where to look for a specific mistake =)

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

            No, I'm seriously, also, I failed A and B because of time pressure.

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

              Yeah, that happens. It's important to keep calm to make sure we don't slip on the "easy" problems.

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

    What tricky cases (not covered by the pretests) were there in B?

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

      00:10

      Not a few people overlooked the fact that the maximum possible base is 59.

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

      I did all my 8 challenges in problem B, the most common one was 0:10 for people that output -1 when it works for base 36 (or some other base < 60). There was one person in my room that checked minutes <= 60, that wasn't covered in the pre-tests either.

      EDIT: evima beat me to it =P

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

Two bugs: 1. After hacked i got javascript alert "Undefined" instead of "your solution have been hacked" 2. When i tried to hack other solution nothing happened after giving input and after 10-15 seconds it showed "the solution have been hacked or resubmitted", later in hack page i've seen that my hack was successful.

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

    I experienced the second bug twice. In my case, the first hack was successful, but the second one was ignored (someone was faster).
    I got the same message "the solution have been..." regardless of whether the hack was successful.

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

    I got bug1 too. It happened to me last round too I posted it on my blog and nobody replied to me and now same problem still exists.

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

BTW, there is an O(n log n) algorithm for E. I see that most passed solutions are O(nm). Waiting to see which one is in the editorial ;)

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

    Can anybody please tell more about your O(n log n ) approach for E ?

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

      Let me sketch both approaches.

      Let's call the long word s. For every short word w: we are to say whether there is an i such that w[1..i] and w[i+1..end] both occur in s, and w[1..i] occurs before w[i+1..end] (so that they don't overlap). It only makes sense to consider the leftmost occurence of w[1..i], and the rightmost occurence of w[i+1..end]. So we are interested in the values f[i] and g[i], where f[i] is the position of the leftmost occurence of w[1..i] in s, and g[i] is the position of the rightmost occurence of w[i+1..end] in s. Once we have f and g, we can easily check whether there exists an index i such that g[i]-f[i] is large enough (larger or equal to i, I think). And if we have a method of computing f, then we can use it to compute g (it's pretty much just f for both strings (s and w) reversed). So we're left with how to compute f.

      The O(nm) approach: search for every word w in s, using KMP. During matching, we virtually get the f[i] array as a byproduct (this is clear if you know how KMP works).

      The O(n log n) approach: we use a Suffix Array for s (and s reversed to compute g). There are fast algorithms for SA construction (even linear-time). We also precompute a Range-Minimum-Query structure for the SA. Now how to compute f: for every prefix (starting from i=1), we find the range [a,b] such that sa[a..b] corresponds to the indexes in s which begin with w[1..i]. We compute this range from the previous one using a binary search. We then run an RMQ query on sa[a..b] to find the minimum index (which is the f[i] that we want).

      The details can be seen in my solution ;)

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

    You must have come from a parallel universe. Most accepted solutions I saw so far has O(M+N) complexity

    Edit: Sorry, I miscalculated :(

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

      O(M+N) really? All I saw ran KMP (or some string matching) for each small string and that would be O(MN)

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

      Is it possible to delete I comment? now my older comment makes no sense :D

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

    suffix array?

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

    O(N*logN) is also not a feasible solution since you HAVE to examine the words. So it is at least O(N*logN + M) or more likely O(N*logN + L), where L is the sum of characters in all M words :) (yeah, I know M is usually much smaller than N*logN, just making a note). My solution uses hashes instead of Knuth-Morris-Pratt and also has time complexity of O(N * M). To be honest I'm also curious about the logarithmic solution.

    Also, if you use suffix array and then do a binary search in it for each word wouldn't you get time complexity of O(N + M * logN * 1000) or something?

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

      Yes, my algorithm is actually O((n + L) * log n). I'm just treating the value in parentheses as n, since in the problem, L is also <= 100000 ;)

      The algorithm can even be made linear-time using very advanced techniques. Not that it would run faster ;)

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

Y U NO HACK ME :(

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

Thank you to the codeforces team for that contest. This contest has very good questions and very well pretests.

→ Reply
»
13 years ago, # |
  Vote: I like it -28 Vote: I do not like it 
Two complaints:
1. Why Am I getting logged out again n again?.
2. Problem C, was not good. Any idiot can also guess that answer without proving.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I would suggest enabling cookies and checking the check-box "log me in for a month".

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

Hi...my submission ID for problem B is 1168221. My program gave correct output for 1st pretest on my system and also on Ideone.com but it is judged wrong on pretest 1. It is giving an additional output of 23 in the end. Please resolve the issue. :( :(

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

    ignore

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

      it is showing 23 at the end which is not required...please double check it.

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

        Same thing has happened to me also. It has added 23 at the end resulting in pretest:1 failure.

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

@admin . Hello, My submission for Problem B whose id is 1167928 gives correct answer for pretest 1 on my system as well as on ideone.com. My my submission has been judged to be wrong on pretest 1 itself. On codeforces for pretest 1 it outputs an extra 23, but 23 is not printed for the same input on my system and not even on ideone.com. Please look into the matter ans resolve the issue.

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

I got Judgement Error on my first try (1166157) of 149C - Division into Teams and after I submitted again the same answer, the two submissions were judged as Pretests Passed and I got a -1 because of the resubmission. Can anyone fix the score please?

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

@admin:My submission id : 1168245 : It is failing for Pretest1 for Problem B. I am getting correct answer on my machine (using g++ compiler) but when solution is submitted, '23' is additional printed in codeforce's compiler resulting in wrong answer of pretest 1. I see same thing has happened to other person also, who have complained in this forum. Is there bug in codeforce's compiler.Please check

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

    I think it caused by roundoff errors and/or c++ optimization. Those who complained this problem in the forum use the cmath function pow(double,double), which can cause roundoff error in some environment, even though the parameters are integers.

    And, when I ran dragonfire's code with some additional std::cout for debug, then extra '23' is disappeared (see my submission: 1170942).
    This is sooo strange, but probably it suppressed the compiler optimization and the calculation became correct

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

What's the proof that makes the solution of taking the odd indexes in a team and the even in the other -after sorting the numbers- work in problem C?

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

    Let a1 >= ... >= an. Then the difference between teams' strength is a1 — a2 + a3 — a4 + a5 — a6 + ... <= a1 — a3 + a3 — a5 + a5 — a7 + ... <= a1.

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

When will the editorial be available? I'm in very need to it :(

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

Is it possible to arrange some contests on weekends? Looks like the upcoming ones are either on Friday or Monday. Thanks.

→ Reply