gridnevvvit's blog

Codeforces Round #302
By gridnevvvit, 10 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?
»
10 years ago, # |
  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
»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    Seems that it's your country where time zones are changed frequently :)

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

    It seems Chinese students are lucky because we always do it in 00:30am.
    LoL~~~

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

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

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

    I re-checked my email right now, I didn't received notification about this round. I am visiting CF quite often, so I knew about contest anyway; but some people may actually miss round becuase of missing notification.

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

      Yeah I didn't get one too.

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

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

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

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

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

I only say I must give up

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

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it -9 Vote: I do not like it

    Edit: my comment is wrong.

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

      You are wrong, it is our strict rule to always put samples as the prefix of pretests following in the same order.

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

        Sorry... Don't know what made me understand samples as "All test cases"

        → Reply
»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    oh if we maximize also it gets accepted.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← 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
  • »
    »
    10 years ago, # ^ |
    ← 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
    • »
      »
      »
      10 years ago, # ^ |
      ← 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
      • »
        »
        »
        »
        10 years ago, # ^ |
          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
    • »
      »
      »
      10 years ago, # ^ |
      ← 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
      • »
        »
        »
        »
        10 years ago, # ^ |
          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
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← 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
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            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
»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
    ← 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
    • »
      »
      »
      10 years ago, # ^ |
        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
  • »
    »
    10 years ago, # ^ |
      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
    • »
      »
      »
      10 years ago, # ^ |
        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
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Thanks for the tip, that's a lot cleaner :) .

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        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
»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        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
      • »
        »
        »
        »
        10 years ago, # ^ |
          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
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            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
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              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
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
              ← 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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Its a variant of knapsack with repetitions allowed.

      → Reply
»
10 years ago, # |
  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
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

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

How to solve Div2 C Writing Code?

→ Reply
  • »
    »
    10 years ago, # ^ |
      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
  • »
    »
    10 years ago, # ^ |
      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
  • »
    »
    10 years ago, # ^ |
      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
»
10 years ago, # |
  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
»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
      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
    • »
      »
      »
      10 years ago, # ^ |
        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
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← 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
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← 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
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            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
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Anybody else who got WA #11 on Div2 C?

→ Reply
»
10 years ago, # |
← 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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What sort of greedy? I just used set cover.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        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
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← 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
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            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
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              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
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks. I'm happy to see that my code is actually correct =)

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

i cant be happy anymin

→ Reply
»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
    ← 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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is exactly what I asked as a question just before the first announcement.

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

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

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

    My O(NMB) solution works 500ms on fpc. What language are you use?

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

    Same here. Can't understand why the time limit is set so strictly time and again.

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

    What was the approach to solve it?

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

      dp[i][j][k] = No of ways for first i persons to write j lines and causing k bugs

      dp[i][j][k] = dp[i-1][j][k] + dp[i][j-1][k-a[i]]

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

        I got a memory limit exceeded with that approach. Allocated an array of 500 * 500 * 500.

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

          Notice that dp[i] depends on only dp[i-1]. Hence you can do the dp with just M*B memory. See my accepted solution for more details.

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

            Yeah, that's the catch! Thanks :)

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

            can you explain more about "Notice that dp[i] depends on only dp[i-1]" please?

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

              Well if we are in state (i, j, k) we can either transition to (i + 1, j, k) or (i, j + 1, k + a[i]). So the calculation of a state (x + 1) only depends on x and nothing else.

              → Reply
»
10 years ago, # |
← 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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Yeah, I have similar issue as I see.

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

    What is the reason to make array size as a power of 2? It leads to problems with cache.

    For example, you can increase 512 to 520 and got Accepted: 11026552 and 11034250.

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

      Thanks for the idea. Next time I won't make it power of 2.

      I never thought that I could get TLE due to branch predictor behavior / cache collision.

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

      Why exactly does this happen?

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

        Because cache internally uses a hash function based on several least significant bits of memory block address. When the second dimension is a power of two, accessing a[i+1][j] will most likely result in a hash collision that will slow down everything.

        More info here: http://danluu.com/3c-conflict/

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

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

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

Rule 3 : Ignore rule 3 XD

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

Does anyone know when the ratings will be updated?

→ Reply
»
10 years ago, # |
  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
»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
    ← 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
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem — A

Why my Solution skipped? — 11027863

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

    because your solution like another solution :D

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

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

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

    O(n2).

    In case 39, the calls calc(0, false), calc(1, true), calc(2, true), ..., do O(n) operations each.

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

      It looks that case 39 is my hack :-)

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

    Well, I think it's sigma(deg(i)^2), which can be O(N^2) in worst case.

    → Reply
»
10 years ago, # |
← 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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Highlighted area like?

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

      Hello mihir, Sorry, for some reason, the attached picture was not shown. The picture link is here. But now it is showing and all things are going like other usual rounds. Thanks. :)

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

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

→ Reply
»
10 years ago, # |
  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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    My solution works in and uses linear amount of memory

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

      Then why 7 seconds time limit? Is there a huge constant or something?

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

    where is editorial??

    → Reply
»
10 years ago, # |
  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://codeforces.net/contest/544/submission/11031166

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

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

/**/

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

What an awful contest?!

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

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

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

    0 has no mod inverse.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        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
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← 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
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply