cgy4ever's blog

Codeforces Round #290
By cgy4ever, 10 years ago, In English

Fox Ciel is back!

I invite you to participate in Codeforces Round #290, which will start at the standard time on next Monday:

This is my 4th round on Codeforces, my previous rounds: #190, #228, #270.

Last Div1 Round (#286) is so hard, so after notice that, we decide to reduce the difficulty of this round. (For example, current Div1-E was used as Div1-D) I hope more people can enjoy all tasks in this round: this time no task requires advanced knowledge like linear space or Fourier Transform.

The background story will be Fox Ciel's life: learning programming, play games, traveling, have dinner and so on.

Like Round #228, top-20 contestants that are currently at Petrozavodsk training camp will be rewarded with nice Codefores T-Shirts. Contestant may be a team member, jury, coach, organizer, or whoever else involved in camp, no matter of status.

As usual, thanks to Zlobober for giving great suggestions and test my round, and MikeMirzayanov for the platform (Codeforces and Polygon).

Good luck and have fun!

Update1: Score Distribution is ... Div2: Standard (500 — 1000 — 1500 — 2000 — 2500), Div1: a bit unusual ... (500 — 1000 — 1500 — 2250 — 2250)

Update2: Editorial: http://codeforces.net/blog/entry/16173

Update3: Congratulation to our winners:

Div1:

  1. Petr

  2. Endagorion

  3. mmaxio

  4. jqdai0815

  5. tourist

They are all people who solved 5 tasks!

Div2:

  1. SkullSkin

  2. joshkirstein

  3. gabrielinelus

  4. UnknownNooby

  5. Andrey_WK

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

Comments Comments (184)
| Write comment?
»
10 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Nice! I love your contests! Always I think that a little easier problems are better.The best programmers will certainly be in their place,and other competitiors will get more fun.

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

i'm not in Petrozavodsk training camp, but i want t-shirts too :)

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

"advanced knowledge like linear space" :P

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

hmm, i always thought that Bredor was the author of Round #228. ;)

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

    Look at his head carefully in his profile photo :)

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

Doesn't using the current Div1-E as Div1-D make it harder, not easier? The D task will be hard as E task, and E task will be even harder!

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

    It means the previous D will be the current E.

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

      actually, minimario's translation was correct. It seems that the author has his wording wrong.

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

        Maybe you are right, I'm not good at grammar. Then how to express it properly?

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

        I parsed it as "the upcoming Div1-E was initially supposed to be Div1-D". But the points is this round is going to be easier than the last Div1 round, at least according to the author.

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

The contest is from China. The time is 19:00 in Russia it means 00:30 in China! an it will last for two hours that is 2:30 AM! Will you be awake that time? :D
Anyway, Thank you for the contest... It's my 100th contest and I'm really scared because my rating change in your last contests was : -54 , -74 , -127 :D



UPDATE : This time my rating change was -106 :|
cgy4ever...

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

    Afaik, cgy4ever is from China, but not in China.

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

    It start at 8:30 am here (California), I hope I can get up at that time.

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

    We all get used to competing programming contests at late night, since almost all contests of Topcoder, Codeforces, Hackercup and GCJ are hosted on bedtime in China (UTC+8). So I'm sure cgy4ever would be awake if he were in China (But he is in US now, Chinese topcoders always get up late :P).

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

    .

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

    next one -213

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

    last time your rating change was -127,this time -106, so that's an improvement by +21 !!!

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

Didn't provide much help to Fox Ciel in last round . Will try to impress Fox Ciel atleast this time

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

Thank you for making this contest :)

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

YES

A CGY4EVER ROUND

!!!

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

finally a Div 1 + Div 2 round after 4 continuous Div 2 only rounds :)

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

Congratulations on advancing to the onsites of Facebook Hackercup cgy4ever.

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

    Thanks!!

    Now I've advanced to nearly all big onsite finals at least once: GCJ(2011), TCO(2013,2014), Yandex(2014, but can't participate due to visa issue), FHC(2015) and ICPC(2015).

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

~~~~~~~~

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

I've registered but I might not be able to participate. Will my rating be affected if I never even open the contest page? (like on TopCoder).

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

    Your rating is not affected if you don't make any submission. (You can open the problems and decide to leave if you don't want to submit without any rating change.)

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

I wish good rating for all

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

I Love my rating :

1616 :))

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

hoping to taste div1 after the competition

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

Its good that its two division contest, otherwise merging it results in some weird rating change like #270 and GoodBye 2014 because too many top coders registered for this round.

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

My first contest, wish me luck.

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

    My first Div1 contest, wish me luck.

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

Get ready to rumble!

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

Good luck

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

Wow, over 6000 registrants in total. Can CodeForces handle it?

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

Why I can't hack other code?

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

    Make sure you locked your solution for that task first.

    And make sure you are in the same room with that person.

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

      He's only submitted problem A. And I really can't think of a bug someone would have in coding such a problem. :) I think he asked why nobody has made mistake in implementing A. :D

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

That feeling when you hacked tourist :))

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

    Liar!

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

      No it was mkirsche that hacked tourist, Ximera was just pointing it out. I was also confused at first.

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

    That alone made this a successful contest as far as I'm concerned. :D

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

Oh! TAT! In my room,only I locked the code!And I was waiting a coder locked his code then I will hack him! But when I found a coder has locked his code,he used java and I can't hack him.I am so sad! Maybe I should average up and I can go to the div1....

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

    You can hack any solution, not only those that are locked. (Of course, hacking an unlocked solution means the owner can still get to fix it.)

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

what was the hacking case in div-1 A

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

    2 bacrr bac

    it should be impossible

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

      thnx missed it completely ....and got hacked :(

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

      I handled this case, still got WA in test 12 :(

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

    Possibly it is

    2
aa
a

    But I am not sure if it is a valid test case

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

    I suppose something like 2 abcx abc

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

    What's test 12 for Div1-A?! I can't see full test. It's a huge test and shows "...". I try all of the special test cases mentioned in this post but my code still shows "Impossible" instead of "abcdefghijklmnopqrstuvwxyz" (the answer for the test 12). Here's my submission: 9688819

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

So what's the solution for D?

It seems that we need to ignore nodes contained in a cycle, and do a DP on the resulting forest. I had a O(N4) DP for solving a single tree, but I'm afraid it would TL (especially with recursion). Then I thought that to count the number of eliminations of size k, we need to count the number of subtrees of size treesize - k, which results in a O(N3) DP, but that totally ignores the order of elimination. Is there a O(N3) solution after all?

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

    To solve a tree of size S I used this algorithm: for each node, find the number of ways to remove K nodes such that the node is not removed (if K < S) or is removed last (if K = S). Then an ending subtree of size N is counted N times (once by each of its member nodes), so we adjust for overcounting by dividing by N.

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

    O(N4) with 3 seconds TL (and nothing else that could have the same complexity) and only in one small loop? Plus with O(N3) memory? I'm pretty sure it would work if you don't do something utterly stupid.

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

      For some reason I still have the impression (from sometimes before) that anything more than 108 is slow. Time to forget that and move on :)

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

        Depends on what it is. Processor instructions: no. Actually 4 times (common with DP) less simple C++ instructions: no. Insertions in a map of constant size: probably yes.

        It's better to risk it and find out in such a case.

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

    We should exclude not only cycles but some other vertices too, for example if cycle is conected to another cycle etc.

    We have rooted trees (connected to some bad vertex), and unrooted trees... and well I in both cases we can compute the answer using dp in N^3. Then we can join answers for trees using binomial coefficients in O(TN) where T is number of trees.

    But I didnt have enough time to debug my solution, so maybe it's wrong.

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

      What I meant was that we should exclude nodes that are part of some cycle. That includes your case :)

      Yeah, I think you were doing it the right way.

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

great contest i'm waiting for your next contest thank you

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

Last minute, CF was down! I couldn't submit my A solution :( Actually I solved A but I was waiting for solving another problem too, after I submitted B and Got Pretest Passed, I wanted to submit A too. Which is now undone thanks to codeforces :D

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

    i wrote a submission for b, but haven't ten more secs to submit(

    my last round i submitted C 2 minutes before the end.) nevertheless, i need more time to get div1 membership :/

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

what was the solution for div1 b or div2 d? I tried pd with a knapsack, but the numbers were to big i think for that. Are there some tricks for big numbers? or is there another approach?

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

    A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n. Since we want that to apply to all n, then the GCD should be equal to 1. The solution is DP with state (i, GCD) (last used card and current GCD of cards). We can use a map to store the states since the number of different possible GCDs is quite small.

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

      that was also my idea, but forgot the fact that the number of GCD is small. thanks!

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

      How to prove that the number of different GCDs is quite small?

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

        Because it should be the divisor of some number ai and ai ≤ 109. Numbers in that range can't have many divisors (less than 100 I believe). EDIT: Ooops, my guess was wrong, thanks for correction Andrei1998!

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

          In fact, 735134400 has 1344 divisors, so a safe guess would be 1500.

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

      "linear diophantine equation" is probably an overkill ;-)

      Basic number theory: Given x and y, their smallest positive integer linear combination spc(x, y) is given by sx + ty = spc(x, y) = gcd(x, y). You just need to find the minimal cost subset such that spc(a1, a2, ..., ak) = gcd(a1, a2, ..., ak) = 1.

      Note that gcd converges quickly as the subset size increases, assume that integers in the subset are distinct.

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

        Overkill or not, it's how that type of equations is called. Then again, anyone who has done a bit of number theory knows what a diophantine (I imagine the name doesn't sound horribly different in other languages) equation is, not to mention linear.

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

      "A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n"

      Is there a proof for this?

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

    Yes, you are right, the gcds are too big to do dp with them, but the right thing to do there is to note that the number of useful gcds is small enough (my calculation ended up being ~60000 different gcd's), so you can map them to 1-60000 and then do dp.

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

      thanks! unfortunately, i'm not used to mapping and tried some tricks with big numbers, but they didn't work...

      i definitely have to learn how to map

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

Best message ever :v (And definitely, I didn't submit that -_- )

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

thanks for A. sweatest shit I ever eaten...

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

    WOW you have eaten shit ???

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

      -YES FROM YR MOTHERS BUTT

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

      Сum on!

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

        Have you paid for Visual Studio ? :-)

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

          Yep, obviously, and for uTorrent too

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

          It's freely available to students (under some usage restrictions). Say, if you have ISIC card (or another proof of enrollment), you are eligible for DreamSpark program which includes a lot of Microsoft software free of charge (not for commercial usage, of course).

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

Div1 A

What's the answer for:

2
aa
aa

?

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

How to solve Division1 C? Task looks like a Euler path, but I don't know how to solve it.

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

    Although i have not participated in the contest but i think this problem can be solved using topological sort this way . Please correct me if i am wrong some where ..

    We can take each pair of string and find the first miss match then we put a directed edge from one character to the other (offcourse miss match pair is taken) then find whether there is a cycle or not in the graph . if there is a cycle then it is impossible otherwise find the topological sorting .

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

      He asked for Div1-C, not Div2.

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

    No, a set of cycles.

    You can notice that any two neighbours need to have different parities, so you have a bipartite graph describing possible neighbourings; you want to match each vertex of each partition to exactly two other vertices.

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

      ai >= 2. Yep, only even lenght, I miss this restrict. Thx

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

      Is it correct to find one bipartite matching then remove the edges of this matching from the original graph and find a second matching? I wrote the solution and it passed the sys.tests, but I couldn't prove it's correct.

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

        It's not correct. Try test:
        6
        10 2 26 5 3 9
        or its permutations. System tests are weak.

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

          UPD: The following proof that we need two perfect matchings is correct, but finding two perfect matchings sequentially does not always work.

          "=>"

          Each breakdown of graph into cycles can be divided into 2 sets of edges, "left-to-right" and "right-to-left". Each node from left and right part has exactly one edge of each type incident to it. Therefore, each of such sets of edges forms a perfect matching.

          "<="

          For a pair of two edge-disjoint perfect matchings we get a set of edges such that each node has exactly two incident edges. Since the degree of each node is even, there exists an euler tour in each connected component. Each connected component has exactly K nodes and K edges, therefor the tour is also hamiltonian. Since each node has at least two edges, each component has > 3 nodes.

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

            A flow solution finds this order: 1 5 3 4 2 6

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

              Ah, I see. So the idea about two perfect matchings is correct, but finding them sequentially does not always work.

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

            The answer exists:

            9 10 3 26 5 2

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

For D1-A, what is the correct answer for this case?

26
a
b
c
...
z

According to this sentence:

But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!

Should the answer be Impossible? Since you cannot do any modification to make them lexicographical...

I think this problem is ambiguous on this case. Could the author clarify?

Edit: well my solution outputs abc...z on this case. However, my friend's outputs Impossible, because he was struggling to resubmit his hacked solution on this multiple times without success, to the point that he thought the wording of this sentence was actually the tricky case.

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

Did somebody made mistake of writing "Impossible" as "impossible"? :P

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

How is Div1 B solved?

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

Thanks a lot for the nice C problem :) It is clear experienced coders must have seen it before but I was happy once I figured out the max flow solution. Then, I ran out of time because I didn't know how to restore the flow, and had to spend some time debugging >.<

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

Very nice problems cgy4ever, thank you :)!

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

Thanks for this round. Though my rating will decrease I learnt a lot . Hope you will be setting problems frequently .

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

Did anyone else wrote randomized algo for Div1 E? (・_・ヾ If my solution pass, I would probably look like (☉_☉')

Edit: It failed (˘_˘٥)

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

What a bloodbath on div1 A! I missed the opportunity of being hacked.

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

My code (codeforces.com/contest/512/submission/9686628) got accepted but it writes "Impossible" with this simple input: 2 a a :))

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

Thank you for such a wonderful contest!!

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

Finally in top 5! Congratulations to winners and big thanks to those who created this nice contest for us.

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

Best contest since I am on codeforces :) Thank you :)

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

Codeforces was working perfectly during last 10 minutes. I've read so many codes, challenged so many people during that time! To help u guess how many, i say that factorial of this number is 1

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

Great contest with good problems,I just didn't know about 'topological sort' before the contest,and learn it during the contest ;)

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

Very nice problems. And finally I can become international grandmaster, really excited!

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

My short sad story:

I had A and B and it was like 15 minutes to the end. I didn't have any good idea for C/D/E so I wrote some simple greedy-random solution to E but I wasn't able to submit it during last 2 minutes. And now my code from contest passed all tests: link to solution

Ofc. AC with this solution would be a bit unfair but still I'm just sad... 155-th place vs. ~24-th place :(

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

Why is this Div 1 B solution failing the system test cases. Please Help. http://codeforces.net/contest/512/submission/9690331

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

    So easy question... Cause answer was wrong :|

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

    Are you sure it's okay to modify the container which you are currently iterating over? I guess that could be the source of the bug.

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

      I used unordered maps. So I guess it shouldn't modify the container which i am currently iterating over.

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

    Iterators are invalidated when you insert into unordered_map: http://en.cppreference.com/w/cpp/container/unordered_map/operator_at. Try to replace by std::map.

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

      My goodness :D ... I chose to use unordered_maps other than maps at the last moment... God has been very kind to me :D ....Thanks anyway for finding the bug :D

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

Won't there be a rating change for this round?

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

My rating increased by ranking 266 ?!?!

Whoa, and here I was regretting not realizing C was a flow problem sooner and complaining about how terrible my performance was...

Though I wasn't fast enough to solve it during the contest, problem C was really nice. A very good contest overall!

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

    Actually your rank was 266 and your rating increased by 90! :P

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

      Exactly. I wasn't expecting that! After the contest finished, I could have sworn I was going back to purple...

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

Слабые тесты в задаче B первого дивизиона! Моя программа, получившая вердикт "Полное решение" даёт неправильный ответ на тесте: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1 числа l[i] сконструированы так : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. Поэтому наименьший набор l[i], имеющий наибольший общий делитель равный 1 содержит все 9 чисел l[i]. Поэтому правильный ответ на данный тест 9. Однако моя программа, зачтённая на codeforces даёт ответ 8 (не та программа, которая прошла претесты во время соревнования, а которая была отслана после окончания соревнования).

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

    Что не так с моим комментарием?

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

      You wrote that comment in Russian, but posted it as English. Many people who use English version of CF see your comment and can't understand.

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

    Weak tests in problem B of Div.1! My program that got AC gives wrong answer on test: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1. Numbers l[i] are constructed so : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. So the least set of l[i], that has gsd equal to 1 contains all 9 l[i]. So the correct answer to the test is 9. But my AC program answers 8. This is my comment.

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

Nice problem set :)

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

DIV 1 C --> Awesomeness!! Thanks cgy4ever!! :D

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

How this contest can be rated since I did not connected to codeforces at least an hour ? Is that just happened to me or everyone ? I can not send my solution to B because of the network problems and now I got -80 :( I WANT MY RATING BACK !!!

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

    Just to you. Codeforces wasn't running so smooth, but rest of people were able to send their codes and get the verdicts.

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

Russian page has no links to editorial nor winners of Div1 / Div2. If anyone can fix it then do it please.

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

    Added them in Russian version, but in English since I don't speak Russian.

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

Take a look at this solution of div.2 D/div.1 B please. Where is bug? (WA on 24th test)

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

    Here. for (int i = 0; i < N; ++i) { cin >> c[i]; dp[l[i]] = c[i]; } Nobody guaruanteed that l[i] is not in map already. You will just lose too much information if l[i] overlaps with another one.

    → Reply