fchirica's blog

Codeforces Round #225
By fchirica, 11 years ago, In English

Hello everyone!

We invite you to participate at Codeforces Round #225, scheduled Monday, 20th January at 7:30 PM MSK. This is the third round I coauthor, along with Codeforces Round 198 (Div. 1) (and of course Div. 2 version of contest) and Codeforces Round 191 (Div. 2).

If you recall my old rounds, you'll see that main character is Iahub. The other writer of this round is... Iahub... the real person corresponding to "Iahub" character. Let me introduce you to Rares Buhai (rares.buhai). He's the author of Div. 2 C / Div. 1 A, Div. 1 D and Div. 1 E. You can expect those problems to be interesting, coming from a 2 times IOI gold medalist (being allowed to participate 2 more times). All other problems are created by me. I like them, but I wouldn't be objective if I said that they're interesting. Let's see if someone will think so after the contest :)

Like last time, I'll give you a little spoiler about the tasks. We tried to make the problem set as varied as possible. In order to get a good rank, one needs to be good at "ad hoc" problems as well as have good algorithmic knowledge.

As always, thanks to MikeMirzayanov for Codeforces platform, to Delinur for translating tasks, to Gerald for helping us prepare the round and to DamianS and ll931110 for testing it.

We wish everyone high rating and to have fun!

UPD Score distribution:

Division 1: 500 — 1500 — 1500 — 2000 — 2500

Division 2: 500 — 1000 — 1500 — 2500 — 2500

UPD Contest is over! Thanks for everyone who participated! I need to say we're impressed of your creative and totally unexpected solutions for Division 1 D.

Div. 1 winners:

  1. yeputons
  2. Arcueid
  3. Dmitry_Egorov
  4. ACMonster
  5. scott_wu

Div. 2 winners:

  1. Sick_coder
  2. akaring
  3. c0d3junki3
  4. raihatneloy
  5. sky0917

UPD Editorial

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

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

is the score distribution going to be dynamic ?

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

Hm, what is an "ad hoc" problem?

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

    It means that the problem has a unique, uncommon or unusual solution.

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

    Problem that depend only on observation , doesn't need a special algorithm to be solved with

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

    problems which are not based on any particular algorithm, and usually based on observations and deduction of patterns.

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

    Ad hoc problems are those whose algorithms do not fall into standard categories with well-studied solutions. Each ad hoc problem is different; no specific or general techniques exist to solve them.

    Of course, this makes the problems the fun ones, since each one presents a new challenge. The solutions might require a novel data structure or an unusual set of loops or conditionals. Sometimes they require special combinations that are rare or at least rarely encountered.

    Ad hoc problems usually require careful reading and usually yield to an attack that revolves around carefully sequencing the instructions given in the problem.

    Ad hoc problems can still require reasonable optimizations and at least a degree of analysis that enables one to avoid loops nested five deep, for example.

    I took this definition from USACO Training Pages. I recommend it strongly if you want to improve your level of problem solving.

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

It' s my first Div.1 contest, looking forward to it. And thanks to the authors, we can have another contest in a few days:)

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

Another round which is not during weekend :(.

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

    But its at night (in India) so doesn't matter to me!

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

    If you're from the US, it's Martin Luther King Day, so there's no work or school.

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

Cool! Another round with Romanian problem setters. I can't wait to participate. Will Iahub also be the main character this time, too? :) Or will you also have a Sufle character? :) [ the reverse of elfus ]

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

    Thank you for the hint! It's just now when I realize what Iahub means (the reverse of Buhai).

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

Good Luck to everyone!

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

Seems that it is going to be a very interesting round. Good luck to everyone..

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

Div1 500, 1500, 1500 ?!

I was aiming at solving A & B now I have to reconsider this :D :D :D

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

    * insert a Courage Wolf picture *

    solve A, B and C instead

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

A round with a very interesting score distribution... It seems that I'll back to Div2 again :)

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

Do you wish good luck to everyone?

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

where is the link for problems ofRound#225

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

Finally, a round where we can see the score distribution earlier than expected....

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

GL & HF!))

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

I hadn't found any broken solution. Maybe pretests are too strong?

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

NO HACKS for div2! :o

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

    Actually there are. I suppose most of the solutions of div1 B/div2 D will fail.

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

Problem C was interesting. Same for D where the answer was only 2n — 2 or -1. B was too boring a problem to waste time though.

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

    I believe Answer is not always 2n-2 or -1

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

was it a very hard contest for you or just me??

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

    I think it was good contest for me.

    I actually got quite much time to think on problem C which isn't usual for me in the contests.

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

    this is how a contest should be. neither too easy nor too hard. well done fchirica.

    PS: next time, try to improve the gradient of difficulty of the problems. that was the only thing lacking today. :)

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

Division 2B, it is intended that you can simply print every single pair?

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

    yaa..

    more like printing optimized bubble sort steps will do it within the limits of pairs allowed.

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

what a terrible system test fail rate on Div 1 B...

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

div 2 — A is too basic

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

    it always is! those problems is designed so that every participant can get it accepted, even if he/she does it after one or two wrong submissions. :D

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

Very nice contest :)! The problems were very interesting and fun to solve!

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

This round taught me it's more important to think more than code faster!
I could have much more time and points if I had thought some minutes more!
Thanks for good problemset ;)

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

Wow, system test for div 2 D was powerful!

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

    The whole system test was powerful :) I've amazed the speed. Maybe need some sleep to be more interesting :)

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

What's the point of additional constraints in div1E? It can be done in O(2K + N) regardless of how long are given strings. My solution passes in 280 ms.

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

    Cool! Can you share your solution?

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

      Suppose we have an array a of length 2K. We want to construct array b so that bi = . Partite a into two arrays a' = a[0..2K - 1) and a" = a[2K - 1..2K) and solve the problem recursively for them, obtain arrays b' and b". bi = b'i if i < 2K - 1 and bi = b'i - 2K - 1 + b"i - 2K - 1 otherwise. This is clearly a linear solution. Actually, this is a O(K2K) solution, my bad.

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

        As I can see, it is k*2^k solution as we have k levels with O(2^k) merge for each of them. I have exactly the same soltuion but I do it in non-recursive way. 5753388

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

    Well, the "easy" solution I guess was O(N+2^K*K^3) — by precomputing the amount of words with all possible combinations of 1, 2 or 3 letters and then solving each query with inclusion-exclusion formula, but I managed to optimize it to O(N+2^K*K^2) by using some previous results and that was enough. But this solution heavily uses that the length is up to 3, so that we can stop inclusion-exclusion formula when there are more than 3 bits on.

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

I've solved the Div1-C with heavy-light decomposition. This is the first time when I use this in contest :) . Is there any simpler solution?

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

    I use heavy-light decomposition too.

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

    It is enough to decompose the tree in such a way that every subtree is represented by continuous interval. You can use a simple pre-order DFS and build a standard segment tree on top of the resulting sequence (or Fenwick tree).

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

    I converted the tree to linear brackets sequence. For each node, record the smallest begin time and largest the finish time of all the nodes with odd depth of the subtree. Also Record the even part.

    After that, just use segment tree to implement the add operation and the query operation.

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

There is NO Accepted Solution for B in my room (16) ! I haven't seen any problem like this before!

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

Really weak pretests for problem B Div1!

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

    actually, i dont think the pretests were weak. it's just that the system tests were really strong!

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

    There is no weak pretests for problem B div1, there is just a lot of weak solutions :)

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

How exactly does -50 on wrong pretests work ? Will it only get reduced from that problem if we actually submit an answer for that problem otherwise not ?

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

    Only if you pass the system tests on that problem. And the hacks on it should always count.

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

    Each wrong answer on pretests gives you -50 score for that problem , but you will only get the penalty if you actually manage to solve the problem correctly, otherwise your score for that problem is 0.

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

    You will get the penalty only if you get AC on that same problem later.

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

I was stuck in B, and didn't take a look at D until there's half an hour left. This taught me to read all the problems before thinking.

It's the first time I solve D :)

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

    I took an unnecessarily long time on C — I could solve it quickly, but silly mistakes appeared. After I solved C, I solved D in about 20 minutes.

    D and B should've been swapped. The idea isn't really hard, but it's prone to mistakes.

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

There is 150 test cases for B! But All of the failures are on tests less than 13!! :)) I think 13 test cases were enough!

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

thank you for great contest, but pretest was a bit weak on problem B div 1.

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

Hello.. I just want to ask something.. why my code got Wrong Answer on Problem A?? When I compile it from my laptop, it gives me the right answer.. And when I submit another for practice and just delete some STL include but my main code is still the same, it keeps get Wrong Answer and the Wrong Answer's test case is not the same.. First it is on Case 8, then second on case 7, the third one on Case 9.. What is going on???

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

    you are trying to use element with indicies -1 and n in your array, Besides, you are using data in that array that was never initialized

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

    I modified your code and got AC 5759068. Hope this help you understand.

    If i == 0 then you don't need to check peta[i-1][j], the same is for j. And since you fill the blank from small ij's, you don't have to check peta[i+1][j] and peta[i][j+1] either.

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

      Oh, now I understand.. Thanks, jonathan79717.. :-)

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

what was the tricky case for problem D div 2 ?!

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

    for me it was this case

    ......
#.....
......
.#####
......
......

    i have to go left at some point which is not a valid move

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

      hmm i don't think it was the fail case to my code since i used STL set container , hmm i would like to know what was the tricky for test 13 :'(

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

      lol i see why i fail ;-; , thanks!

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

    Something like this

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

will there be any editorials for the problems? and when will be the ratings updated?

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

I got WA on pretest 2 problem B div2 and I lost 50 point :( . I am sure I saw this happened before for some participant and they didn't lose points for WA on given cases !!

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

    There is no penalty only for pretest 1.

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

    You don't lose points only if you'v got WA on the first sample. not all samples.

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

    that participant probably received WA#1 or RE#1. submissions that fail on the first pretest do not receive a penalty.

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

Sad to get green again...T_T

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

    you are going to lose atmost 90 rating points xD , the same happened to me in the last contest

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

Thank you for the contest, and, specifically, for the Div 1/D task.

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

    For me, D was the least interesting xD

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

      Considering that the reason I found it beautiful was because of how well the simple solution is hidden in the task, I do understand your point of view that if you haven't solved it, you might find it the least interesting problem of the lot.

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

        Let's not jump to conclusions here :) I began solving it 10 minutes before the end of the contest and finished it 1 minute after the end. So yeah, not interesting.

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

          OK, sorry, I thought that I had looked at upsolving results and somehow failed.

          Anyway, yeah, I most likely enjoyed it was because I didn't stumble upon that idea immediately. If one manages to immediately get to it out, I can even more see how it would be not interesting at all.

          Or maybe I just liked the problem so much with no logical reasoning behind it.

          And by the way, congratulations with the new colour!

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

I tried to hack this solution generating the worst case for bubble sort, in which it should TLE, at least in my opinion. Am I wrong ?

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

Nice contest. Good joob elfus&iahub.

mlc

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

Does anyone has an idea why my program output for the first example test case in the problem B (Div 2) fails?

http://mirror.codeforces.com/contest/384/submission/5758977

It looks like as if it was correct..

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    initial state :
1 3 2 5 4
1 4 3 2 5
step 1 (pair 2 3):
1 2 3 5 4
1 3 4 2 5
step 2 (pair 2 4):
1 2 3 5 4 ( 5 > 2 no swap)
1 2 4 3 5
step 3 (pair 4 5):
1 2 3 4 5 (sorted)
1 2 4 3 5 ( 5 > 3 no swap)

the second array is not sorted at the end !
    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    for first index in output, your array becomes

    1 2 3 5 4 1 3 4 2 5

    for next index in output, your array becomes

    1 2 3 5 4 1 2 4 3 5

    for last index in output, your array becomes

    1 2 3 4 5 1 2 4 3 5

    Now see, second array is not sorted in ascending order. So it's wrong...

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

I didn't like Div2-B. But, C was an awesome problem.

And the pretests of A,B,C was strong enough. Technically The system test of Div2-D was the strongest I have ever seen!!!

Thanks to the authors for a nice contest. :)

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

    Div2-B is funny :)

    Show my solution: 5752434

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

      Yes! With the restriction of output, you can easily realize that bubble-sort will always satisfy it. And generating the code in just a few minutes, like mine. -> 5754578

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

I just study C about 3 months so I feel very worst :(( . Can you share code of Div 2 for me ? My email: nhtrung13clc@gmail.com. Tks all :)

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

    you can see anybody's solution ,just click the submission id :p

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

ratings are not updated yet :(

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

Who's the lucker here???)))

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

Yes! 266 Points added! Any way, I still think that Div2-D is too tricky to solve. And I feel lucky that I solved Problem E first. :)

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

nice contest !!!!

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

What a good luck! One Codeforces round that I didn't [have time to] participate in, and exactly in this one, most of my div 2 friends got >= +100!

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

O(sqrt(N)*N) get accepted for div1 C! 5762148

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

    Oh, if only you knew how many problems on trees I've solved in ...

    It's nothing rare, if the time limits aren't tight. Solutions in often have large constants, caused by the use of segment trees or some more complex operations. Simpler decompositions have worse complexity, but small constants, so they aren't much slower.

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

Where is the Tutorial?

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

Thanks

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

can someone explain a simple solution that everyone writes :) in Div2-C !

→ Reply