dalex's blog

Codeforces Round #222
By dalex, 11 years ago, translation, In English

Hi all!

Authors of today's round are craus and dalex. We just couldn't miss the round with such a beautiful number, so at 19.30 MSK you will solve problems which were invented by Pavel and prepared by me.

We thank Gerald and Delinur for their help in contest preparation and MikeMirzayanov for creating Codeforces.

Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins.

We wish you accepted solutions and successful hacks!

UPD. Contest is over, congratulations to the winners!

Div. 1:
1. Petr
2. tourist
3. Egor

Div. 2:
1. k3e18
2. tongcx1988
3. LeMieux

UPD. 2 Problem analysis is published.

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

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

Does that mean there will be some problems have tricks, and there will be a chance to hack for getting higher scores?:D

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

    That was a great contest! Good problems! New ideas!
    Thank You!

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

"Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins."

lol, I guess the setters are fed up with comments like "Only 10min/5min/30sec left before contest and there is still no updates!!"

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

Best wishes to every one!!

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

Don' t have time to take part, what a pity. Anyway, wish everyone a high rating [By the way, this is the 222ed round, so I guess there will be some prblems about twos. So try to search for some information ~ . Well,just kidding ]:):)

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

Keep in mind that this will be a historic round, because today for the first time I'll become a redcoder :P.

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

You can't wish us accepted solutions and successful hacks! That's a paradox. :D

Or maybe after we get hacked a few times we'll finally reach the good solution / program?

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

    thats always the case with wishing 'high ratings' also as it is designed in such a way that if one gains someone else loses.

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

Please vote "I like it".

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

    Is this the new trend or something? Seems like there is always somebody asking for upvote or downvote in every contest. I am kind of curious now to see how long this will continue :p

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

      I did not read related comments before, therefore I do not know that others ask for up-vote or down-vote. Just do it for fun, nothing more.

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

Yep. Good luck to me and everyone else ~

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

We wish you accepted solutions and successful hacks!

(Y)

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

What's the idea behind putting STRONG pretests?! Hacking is almost impossible!

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

    Well, when hacking is "I know one tricky case, and I'll check if all solutions works on it" It's not very interesting too.

    Pretests aren't strong today BTW at least in Div1.C. My solution is absolutely wrong but passed them.

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

      Well, it's not even like this. Even the extreme cases (big input) were present in the pretests! Some people in div2 got TLE because their algorithms were not to run in time under the problem constraints, I'm amazed that such cases were included in the pretests!

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

    Possible, in Div2 A, there is no test when a = b ;)

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

    Maybe they wanted to make a more classic contest, but Codeforces is neither a classic type of contest nor an ACM type. So there is no point in very strong pretests. Problem C on Div2 could have had some cases not included in the pretests (like the case with all the matrix full, when the DFS should not be called at all).

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

      I didn't use dfs at all, my solution is kLogn + kLogm using segment tree, some people used sqrt segmentation.

      PS: failed sys test

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

It's fun to see a problem about Dota 2 :P

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

the second last codeforces round of this year and nice one..

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

    Just got a popup message there is another round on 30th, which will be rated for both Divisions

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

Incredibly simple A (and impossible to hack as I've seen), simple DFS on C, hard to understand the statement on B (the explained sample though saved the day), not so hard solution (here the intuition on why it works was more important than the proof itself). Nice round for the 2nd last contest of this year. "Authors of today's round are craus and dalex" — keep up the good work.

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

    Three succesful hacks on A. :P

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

      Well, at least in my room, most solutions to A had the case a==b included in them (I tried at least 10 submissions).

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

    I was able to hack on A LOL :D

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

In Div2 B, I forgot to make size of my array which contains merged a and b to 2 * 105. Instead the size was 105. I wonder, will it fail or not? :|

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

    Probably it will fail, but, as all of us know, everything is possible. Tell us if it failed or not.

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

      I tested my code on "custom test". I thought it would get AC or RTE but not WA. As in "custom test" there were no RTE, I gave up resubmitting. And now I got WA 37. :)

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

    FAILED T_T

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

I am interested is problem D Solvable by (Binay Search of Answer)+(Data structure)?

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

    Let's find the amount of days we need to fix bugs with binary search. Now, let's check that k days is enough to do it. First of all sort the bugs. Then iterate through them and for each of them find a student with the minimal c that can fix(b >= a[i]) the bug using set<pair<int,int> >. And he also will fix next k — 1 bugs. If every time we have a student to do it(set is not empty) and the sum of all c is less or equals to s then we can do it. P.S for some reason my solution gets TLE on 9 test :(

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

can't submit in the last 10s ? I submit my solution in the last 10s,but failed to submit

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

Wow! Amazing strong-willed victory by Petr!

Congratulations :)

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

Failed Div2 Problem D because my program output N0 instead of NO ...

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

In Div 2 A all different possible test cases is 6*6 = 36 but there is 38 test cases LOL :)

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

Thank you for the nice contest! I've enjoyed it :). By the way, I got RE on problem B div1. But I've correct output at CF server (and on my local machine), and I can't see why it got RE. Can somebody tell me what I've done?

My submission is here. => http://codeforces.net/contest/377/submission/5561801

(UPD) I've submitted same code at practice, and got AC. http://codeforces.net/contest/377/submission/5562952

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

    It seems to depends on the version of glibc.
    Using glibc with version 2.15, I got RE.

    I hope this information is useful.

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

    Using the GNU C++ library debug mode, I get

    /usr/include/c++/4.8.2/bits/stl_queue.h:483:error: attempt to access an 
    element in an empty container.

Objects involved in the operation:
sequence "this" @ 0x0xffd9f148 {
  type = St14priority_queueISt4pairIiiENSt7__debug6vectorIS1_SaIS1_EEESt7greaterIS1_EE;
}

    on that test, which means that you attempt to access an empty priority queue.

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

    It seems you had undefined behavior as mentioned by andreyv. But New Year will be soon, so it's time for miracles. Usually I do not do it, I rejudged your solution and got OK. Ratings will be updated soon. Happy New Year!

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

    To : numa and andreyv

    Thank you for investigating environments and my code! I'll be careful from now on. I'm glad to know the reasons :).

    To : MikeMirzayanov

    Thanks for the rejudging! It seems that I was very lucky!

    And again, thanks for all whom tried to help me, and craus and dalex for helding a wonderful contest. Happy New Year for all!

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

Very Fast system test. Loved it :)

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

Why am I Expert with rating 1703 !?

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

Thanks :D...I do on ideone without making it private.Have to take care from next time :(

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

    Maybe your solution and another one's solution were same.

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

Div. 1

Div. 2

More info

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

Hi If you visit my profile, KiAsaGibona my rating is 1504. And when I take my mouse at the graph, it says EXPERT , But I am still Pupil . As far I know 1501-1700 is Expert range. But I am 1504 and still Pupil . I want to be blue :( :(

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

    I saw this bug in other profiles too. I think it will be fixed soon.

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

      Its not a bug. Let the system alone it is working hard coloring coders :D

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

      Let's hope so, As I am going to be Blue for first time. Yayyy :)

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

    [1500,1699] is Expert range not [1501,1700] . :)

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

      I have the same problem. My rating has changed BUT the title and color is still NOT updated yet... Hope someone could help? Thanks!

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

I took part in this contest but my rating hasn't changed (I submitted for problem A, div 2). I noticed that the ratings of other Div 2 participants has changed, but mine not. Could someone tell me why this happened?

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

Can someone explain why DFS works for Div2 C?

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

    flood fill s-k cells, that will remain empty. Mark the rest as 'X'.

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

    @dbaluta As given graph is connected & consists of s empty cells, so, Run DFS from any empty cells & mark only (s-k) cells visited. Then, simply print the solution writing empty unmarked cell X . Thats all :)

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

    For any cell, i can delete it if i am sure it won't block the path to any other "not deleted" node.

    So from every cell (x) ,we run dfs to delete cells reachable from (x).

    After deleting them, if i want to delete more cells, then it is safe to delete cell (x).

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

    --> Consider all the blocks where you have '.' as nodes..

    --> Now as you can read in the problem description , all the '.' are initially connected..

    --> So now you have a connected component with you..

    --> You have to now turn K '.' cells into WALL so that the component is still CONNECTED..

    --> Now , the Picture of DFS comes into the mind.. DFS will traverse all the nodes and will backtrack as soon as it reaches 'LEAF' node.. If you turn those leaf nodes into WALL your graph will still be a connected one!!

    Hope it helped!! :-)

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

      Thanks a lot guys! Now is all clear :).

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

    i got wa on test 89 :( I had done bfs and marked levels.Then removed k nodes which have the highest levels.

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

Now tourist really have to be ranked FIRST if he wants to increase his rating :o

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

    Думаю он может подняться со 2, если первым будет rng (судя по тому как считается рейтинг)

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

    if his rank will be 2,and rng_58 rank 1,his rating will increase ;)

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

See these solutions : 5560186 5560332

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

Hey my raiting chnged to 1501 but y i am still graded as pupil?

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

As noone has already done it, I will present solution to Div1 C, because in my opinion it is pretty funny and short.

We just have to completely forget about n-m weakest heros and bruteforce remaining ones in O(2^m * m) using simple dp on masks. Why it is correct?

In short, if we pick — we pick strongest one and if we ban a "bad" hero it doesn't matter which one (from the "bad" ones) we ban. It is obvious that if someone have to pick a hero, the best choice is to pick the strongest hero from remaining ones. So in a fixed moment of the game, if players will have to make k decisions, all picks will be among k actual best heros. Let us call that other heros are bad. Bad heros will never be picked. Since that, there is no point in missing a ban, because we can ban the weakest from remaining heros and that won't affect our solution, because noone will ever want to pick it. So if we consider an optimal sequence S1 of decisions for both players we can create another sequence S2 which will be still optimal for both players and chooses heros only from those m strongest ones. If there occurs missing a ban or banning a hero which can't be banned in S2, we ban the weakest remaining hero in S2 and there is no difference between those 2 choices in future picks, so these two states are equivalent.

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

    Learn Russian, there are lots of comments with discussions of solutions after each round in our language =)

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

If I'm not mistaken E is fairly easy. I will describe a solution with assumption that everything is continuous, not like in the problem statement (it's essentially the same problem, but easier to describe). Think about a whole process in a coordinate system OX — time axis and OY — cookies axis. Firstly sort buildings due to cookies per second (= possible slopes of our cookie graph) and process them in this order. After adding each building we want to maintain a graph of "maximum number of cookies we can achieve in a time t" — this graph consists of consecutive segments of lines with ascending slopes. It can be kept in a vector. When adding a building, we have to find first moment T (by binary search) when we can afford building it and update our graph (that means, finding an intersection of our graph and line passing through (T, 0) with slope corresponding to this building production. Just pop a few last elements of vector and push_back a new one. If we won't process buildings b such that there exists a building c such that c is cheaper and has bigger production, we can achieve O(n) time not O(n log n) by omiting binary search.

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

    This is convex hull optimization right? I didn't do contest because it was too late and I was tired, but I looked at questions and that is what I thought, but I wasn't sure because it was E and I thought it must be more complicated :P

    Edit: Actually I think I was wrong.

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

Can anyone explain me how to solve Div2 C/Div1 A?

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

Can any one tell me about Good Bye — 2013 contest in detail? :)

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

Well , my solution in Div2C is based on BFS , then there has a BFS tree when we run BFS then we can disconect their leaves( this are the nodes more farthest) .

My submission. Code

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

please can any one explain how good bye round will be for both divisions !? and how the rating system will be ?

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

Wow, Zlobober became the new International Grandmaster, Congratulations! :)

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

How do you solve Div 1 Developing Game?

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

I think there is a much simpler Greedy solution to Div 2 C. For each row note the number of empty cells in that row. Now if we have to delete k of the cells then we can completely convert the initial rows to X,such that the no of cells left in the row (which u have just processed ) is more than the number of cells left to convert to X. Now if there are some cells still left to convert ,except the cells which are connected to the row just immediately down u can convert into X. This algo works since when we convert entire intial rows to X the remaining is still connected.

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

In the problem B div 1, can anyone tell me why my JAVA solution got TLE (I do it in O(nlogn^2) : (.

(http://codeforces.net/contest/377/submission/5559914)

After the contest, I tried to rewrite it in C++ and got AC in 156 ms : (

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

    Try to use classes with ints instead of Pairs of Integers and PriorityQueue instead of TreeSet.

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

      Thanks, I tried to use classes with ints instead of Pairs of Integers and got Accepted @_@.

      The objected data is so slow @_@

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

Screencast

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

I think the test data of Div.1 E (Cookie Clicker) is not so strong for a Div.1 E problem. A simple O(n2) solution passes all the tests. In 5604868 I just deleted all the buildings which cannot be used in the optimal answer, using the method mentioned on the top of the editorial, and then used simple O(n2) dynamic programming.

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

    Thank you! It seems that in random tests this condition: if(a[q[qe-1]].v<a[i].v) is false very often.

    You have TL now.

    I've rejudged all accepted solutions that were submitted after the contest. Contest submissions are OK.

    → Reply