gridnevvvit's blog

Codeforces Round #302
By gridnevvvit, 11 years ago, translation, In English

Hello Codeforces!

Soon you are lucky to participate in Codeforces Round #302, and I am writer of this contest.

I want to thank Max Akhmedov (Zlobober), Alexander Ignatyev (aiMR), Danil Sagunov (danilka.pro) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring will be next:

  1. Div1: 500 — 1000 — 1750 — 1750 — 2500
  2. Div2: 500 — 1000 — 1500 — 2000 — 2750

Contest finished, congratulations to winners:

Div1:

  1. Petr
  2. qwerty787788
  3. -XraY-
  4. kraskevich
  5. Merkurev

Div2:

  1. nka55
  2. never_retired_phoenix
  3. lowsfish

Editorial

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

Comments Comments (123)
| Write comment?
»
11 years ago, hide # |
 
Vote: I like it +42 Vote: I do not like it

"you are lucky to participate in Codeforces Round #302" I think I am lucky to participate all Round :D

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

That's strange! Contests are starting later and later in my country (first 8:00 pm, then 8:30 and now 9:00!), but the time in Codeforces' contests page is the same! Do the time modes in countries change so frequently?!

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

Where are these coders ?! Just 2555 registrants for now ?!

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

One more time. A good round on codeforces good luck and have fun everyone!!!!! who do you think will win this round? someone in special ??

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

I hope a nice contest with interesting problems for all the participants.

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

hope problem A isn't going to be HACKY! :D

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

Hoping good results and high ratings... and a lot of hacks!!!

→ Reply
»
11 years ago, hide # |
← Rev. 5  
Vote: I like it +44 Vote: I do not like it

I only say I must give up

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

Are all samples included in the pretests or just the first one?

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

Problem B confusing statement cause me a wrong submission. Should codeforces neglect the wrong submission before the announcement ?

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

    oh if we maximize also it gets accepted.

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

    yeah, it is extremely rare that a problem description (in this case div2 B) is changed multiple times during the contest.

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

    Let me clarify what happened during the contest.

    The original statement looked like the following:

    [start of the fragment]

    We will assume that a set of cells is an island, if the following conditions hold:

    • each cell of the set is covered with sand;
    • from each cell of the set you can get to any other cell of the set by moving only through the cells of the set, considering that in one move you are only allowed to move from one cell to a side-adjacent one;
    • you cannot add any cell to the set so that conditions 1 and 2 hold (in other words, the set of cells should be maximal).

    [end of the fragment]

    It is definition of the island that has nothing common with the rest of the statement. The given definition is one of the classical definitions of the connected component: the connected component is a maximal (i. e. unextendable, not maximum size!) set of vertices such that any two of them are connected with a path.

    In English words "maximal" and "maximum" have different meanings. For example, here you can see two different objects: maximum matching and maximal mathcing. When we say maximum, we mean maximum-cardinality. When we say maximal we mean such set that can't be extended with any other element without losing some property. And this was explicitly said in previous statement. It doesn't say that you should have no way to convert sea cell to a sand cell such that conditions 1 and 2 hold; it says that you should have no way to add an existing cell without losing conditions 1 and 2.

    Also, this part describes the definition of island. The actual task follows after this paragraph and it doesn't say anything about maximizing any kind of value. It is also illustrated by the sample test.

    Nevertheless, we've seen many clarification requests asking why the answer to the sample test isn't maximal in some manner. So we decided to clarify this part as possible. We said twice in global announcements that this definition is a usual definition of the connected component. That still didn't work, some people still were asking questions. Then we decided to even rewrite the definition making it less formal (!) but more clear to a newbie. But we want to point out the fact that at no moment the question was incorrect.

    You can try to formulate by yourself what is "connected component", it's not easy to do that without mentioning maximalness in some way. On CodeForces we usually try to provide formal definitions of things used in problems. Unfortunately, it sometimes leads to such issues.

    After a long discussion we decided to leave everything as it is and make the round rated. After all, there were lots of people who understood the statement correctly.

    Also, as someone noticed above in comments, even if you try to maximize something (total size of all components, for example) and you do that correctly, you will get your "Accepted" since our checker accepts all solution that have k connected components, no matter which size they have.

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

      The description that you posted was absolutely correct and unambiguous, you should not have clarified or changed anything. The current description is wrong:

      //start description

      We will call a set of sand cells to be island if it is possible to get from each of them to each of them by moving only through sand cells and by moving from a cell only to a side-adjacent cell. The cells are called to be side-adjacent if they share a vertical or horizontal side. It is easy to see that islands do not share cells (otherwise they together form a bigger island).

      //end description

      Nothing in that description says that a proper subset of an island isn't be an island. Not only is it not "easy to see" that islands don't share cells, it's wrong: if they share cells, they form a bigger island, but they're still islands anyway.

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

        That's what I mean by less formal. Of course you are right but the saddest part is that tens of questions per minute almost immediately disappeared when we rewritten the statement in such informal manner.

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

      I don't understand. Is this an island?

      SSS
SLS
SSS

      It does not satisfy rule 3, you can still add some cells to the set. (Please correct me if I am wrong)

      I understand that you just wanted to say "a smaller subset of cells of an island is not an island". But the definition is problematic here, because, unlike the usual graphs with nodes and edges, you have "sea cells" and "land cells" here.

      The first clarification doesn't help too (it even reinforced the feeling that you have to add as many cell as possible.) The island is the maximal set of sand cells on existing picture (meaning that you can add no new cell from the existing picture without

      Also an alternative way to clarify things is to add an extra sample that contradicts the belief.

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

        You cannot add anything because adding an 'S' will not extend the set because it is not covered with sand.

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

        PlayTheGame is telling everything correctly above. Regarding the alternative way to clarify things: in this case I don't see how adding another sample could have saved the situation since the main confusion already happened because of the first sample test.

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

          Thanks, I agree. I got confused too.

          I think next time better avoid the terms set and connected component in Div 2 A, B as there are many contestants from middle school who never learned about sets, and some contestants are not familiar with graphs (in a problem which does not require knowledge in graphs).

          They are grey, green and blue after all.

          Thanks for the hard work and explaining to me.

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

What is the hack test of problem D in div1?? I think my solution is correct :(

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

    You can let your code run this case:

    200000

    1 2 2 2 ... 2 2 2

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

      My output for your test is : 543973825 87947641 543973825 543973825 543973825 ...
      Is this correct?

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

    A hack against division via multiplicative inverse: (ideone)

    How to construct it:

    factor 1000000006: 2 500000003
factor 500000002: 2 41 41 148721
factor 148720: 2 2 2 2 5 11 13 13

    So, to get a subtree with answer 148720, we have to unite eight chains of lengths (2-1) (4 times), (5-1), (11-1) and (13-1) (2 times). After that, the subtree contributes a multiplier of 148721 to its parent. Proceed with constructing 500000002 from three short chains and the 148720 subtree... and so on.

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

      I constructed such test using binary representation of MOD: divide it by 2 while possible and add subtree with one node. when it becomes odd, subtract 1 and build new subtree with it

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

      There is an easier way of getting it, as you can easily add +1, by adding one more edge. 1000000006=6+10^9=6+(1+3*3)^9

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

I am one of those, who was registered, but didn't participate, because.. there were no any strong ideas in any problem..
Imho, there should be at least one easy enough problem in Div.1 in order to have a more honest rating.

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

    Problem Div.1A is a typical dp problem, isn't it?

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

      I don't think so: the naive solution, which I could generate, was O(n^4) and after optimization worked 5 secs at max test. I could not invent any O(n^3) approach during the whole round :)

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

        So, you still think that you didn't participate because the problems were boing or because you get scared by the first problem, which, as far as I can see, you weren't able to do? N ^ 3 was the typical dp, and I heard that there is a solution in N ^ 2 too.

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

          Because I could only solve A in N^4 and have not enough time to finish D.

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

            D could be solve writing a very short code.You said in the above coment that the problems didn't have any strong ideas.I think that they were preety cool E seems awesome even tought I didn't solve it.I couldn't solve C and B was very interesting(In my opinion).You insulted the contest just because you couldn't solve A...

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

              No, you get me wrong: the problems were interesting, but I could not find any solution of them, which i sure enough to code or submit.

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

      Its a variant of knapsack with repetitions allowed.

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

you are lucky to participate in Codeforces Round #302 he said

Good luck and have fun he said

:(

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

Did better than usual, fun problems! Maybe I'll become Green again!

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

How to solve Div2 C Writing Code?

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

    it must be dynamic programming.. my code keep getting WA on pretest 6 anyway :(

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

    f[j][k] — count of plans with j lines and k bugs. f[j][k] = (f[j][k] + f[j-1][k-a[i]]) % mod

    → Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it 
     MEM(dp,0);
    dp[0][0]=1;
    FOR(i,n){
        FOR(j,m){
            for(int k=0;k<=b-a[i];k++) 
                dp[j+1][k+a[i]]= (dp[j+1][k+a[i]]+dp[j][k])%v; //dp[i][j] where i represents the number of lines and j represents the number of bugs.
        }
    }
    ll ans = 0;
    for(int i=0;i<=b;i++)
    ans = (ans + dp[m][i])%v;

    I got WA 6 because I was running the k loop upto b (instead of b-a[i]) which was causing WA.

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

Problem B was quite confusing. Also the announcement just changed the problem. I think this round should not be rated

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

I guess almost all solutions will fail on testcase when divisibility by 109 + 7 was involved. I thought that my code handled it correctly, but unfortunately not and I was hacked probably using such testcase.

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

    I was hacked also by such a testcase. How can we deal the problem when the number is divisible by 1000000007?

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

      One way of doing it is keeping then number in form a·(109 + 7)b. When it is necessary to divide by 109 + 7 reduce b, otherwise multiply a by modular inverse.

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

        You can't do this in this manner.

        Of course we can't keep a explicitly, because it will grow too large. We also can't keep just the reminder a%109 + 7, because if you have some number x in this representation then you don't know representation of x + 1.

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

          We can actually do it in this particular case. When we pass this value to a child of a vertex, all what we need to know is whether it is zero or not(modulo 10^9 + 7). If it is not zero(that is, b = 0), a mod 10^9 + 7 is obviously a correct value. If it zero(that is, b > 0), it is, again, correct, because it is 0 regardless of a. Put it another way, we never need to add one to a number in this representation.

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

          How to do it, if is not possible to represent x + 1 using the x value of that representation?

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

Anybody else who got WA #11 on Div2 C?

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

I wrote (almost) correct algorithm for B and D, expecting it to pass. Then I tried to solve C for like 20mins and still have no idea how to solve it. So I decided to code whatever greedy & dp comes to mind (I first code some DP, which got WA5, so I added some greedy).

Now I failed B & D, but my C is correct.

So surprised...

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

    What sort of greedy? I just used set cover.

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

      Uhm, it's very complicated to describe in words, but I'll try.

      So first, about the DP solution:

      • Let's call f(i, S) = minimum cost after we used first i characters, to make the set of strings S good.
      • For each (i, S), I tried each character c. Let S2 be the set of strings where the (i+1)-th character is c --> I use f(i,S) to update f(i+1, S | S2)
      • Note that I always use whole set S2, which is obviously wrong.

      So I updated my DP, allowing adding single character at a time, using min(cost to change this character, cost to change all same characters),

      which I think must still be wrong, and I think the correct thing to do here must be considering all subsets of S2.

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

        If I'm reading your code right, when your DP updates mask | TWO(x) using a single character, mask | TWO(x) hasn't been processed yet, so it can add another single character when you get to that mask.

        So your code actually is considering all subsets, and it is actually the correct solution (iterating over all subsets would clearly TLE).

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

          But how can adding single element at a time like this be correct? In case I add 2 strings x and y with the same character c (at position i), the cost that I'm adding equal:

          min(a(x,i), sum(a(z,i) where s(z,i)==s(x,i))
+ min(a(y,i), sum(a(z,i) where s(z,i)==s(y,i))

          In case sum(a(z,i)) is smaller, I added a(y,i) twice.

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

            In case sum(a(z,i)) is smaller, that means update(f[i][mask | maskSet[i][c]], t + costSet[i][c]); is strictly better than your single character update, so that doesn't matter.

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

i cant be happy anymin

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

You should not maximize the sizes of islands.

That was after a lot of WAs. -_-

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

    I think case 1 itself was self-explanatory that it is not necessary to maximize the sizes of islands. If we had to maximize the size of islands, one of the possible answer could have been: YES

    LLLLL

    LLLLL

    SSSSS

    LLLLL

    LLLLL

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

O(NMB) is too slow for A Div1? I got TLE.

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

The time limit for A is way too tight.

I suppose there was a 500 500 500 case in the pretest. Branch predictor and memory causes it to TLE in system tests.

When I resubmit the same code, case 7's time increased from 25xx ms to 29xx ms.

UPD: gridnevvvit has replied that using long long instead of int causes solution to TLE. I strongly believe that the jury should NOT test for such differences.

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

How is Div2 D / Div1 B supposed to be solved?

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

Rule 3 : Ignore rule 3 XD

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

Does anyone know when the ratings will be updated?

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

Worst feeling of missing Rank-1 just because you kept the array size in Problem A one less than what is required. Silly mistakes!! :\ :(

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

I wonder if BFS was an overkill for DIV 2 Probelm B? Also tricky testcase. Watch out for number of island =0! eg-> 1 0. I messed up due to this. COrrected it now to get AC :/

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

    BFS was certainly an overkill for this problem. You just have to create islands skipping one cell after each island. A simple traversal of O(n*n) does the job.

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

Problem — A

Why my Solution skipped? — 11027863

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

What is the complexity of this solution 11033699 for Div.1D ?

→ Reply
»
11 years ago, hide # |
← Rev. 4  
Vote: I like it -13 Vote: I do not like it

Is it written anywhere that today's contests are unrated? seems something is missing in the highlighted area which exists in other rated contests!

UPD: Actually I wanted to tell about rating changes, but some reason the picture had not shown. However, Ratings are updated and all confusion went out of the air!

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

I wish I had fixed my hacked B 30 seconds earlier......

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

What was the official solution of E. My O(S(32 + N / 32)) passed with 3.7 seconds and 54MB.

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

Can someone explain why my Solution on Div2 B got a TimeLimit in the first Testcase? On my Computer i got an solution instantly and uploaded it twice in the contest

http://mirror.codeforces.com/contest/544/submission/11031166

I noticed that i have an WA as well, but there wasn't enough time to fix both...

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

/**/

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

What an awful contest?!

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

I didn't receive email notification for this round :(

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

My code (for Div1 D) is getting WA. I couldn't find it. What do you think is my mistake?

Submission: 11058128

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

    0 has no mod inverse.

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

      So, it's not possible to do it by dividing, I can't fix it, right?

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

        I think so. In my solution, I do extra preprocessing during build to get the result by only multiplication. Edit: You can use mod inverse to solve this problem too, but you should treat the cases containing "dividing 0" specially. This can be done by recording more data in your "build" function.

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

Why the memory limit is 64MB, not 256MB, in Div.1 E?

→ Reply