GlebsHP's blog

Codeforces Round #342 (Div. 2)
By GlebsHP, history, 10 years ago, In English

Hello, community!

Tomorrow Codeforces Round #342 is going to take place. It will share the problemset with Moscow Olympiads in Informatics for students of grades from 6 to 9. Though, grades from 6 to 9 in Russia usually match the ages from 12 to 15, I guarantee that everyone (even Div. 1 participants) will find some interesting problems to solve. Problems were selected for you by the Moscow jury team: Zlobober, meshanya, romanandreev, Helena Andreeva and me; and prepared by members of our scientific committee: wilwell, Sender, iskhakovt, thefacetakt and feldsherov.

Scoring distribution will be quite unusual: 750-750-1000-2000-3000.

UPD System testing is over. Here are the top 10:

  1. _XuMuk_
  2. pandamonium
  3. latisel
  4. zetamoo
  5. yukariko
  6. I_Love_Ximera
  7. kittylover
  8. shdut
  9. harry.zhao
  10. luke0201

Congratulation! Also, problems seemed to be too tough, we should have probably made Div. 1 round. Anyway, thanks for participating, I hope you enjoyed it and learned something new!

Thanks to romanandreev for nice analysis.

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

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

I am not able to register unofficially for the contest. Please fix this.

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

In the same time as Open Cup 10 stage. It's a pity.

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

Is this contest going to start at the same time of the official contest? Because otherwise it should be unrated, right?

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

    It's not going to start exactly at the same time, but it will start before the statements become public and will end at the same time as the onsite contest (which actually runs for 4 hours).

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

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

GlebsHP you forgot to thank yourself :)

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

Links to any previous contests by the same authors would be very helpful. It'll give a good idea as to what to expect in the contest! Any help?

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

Wish Codeforces a happy Chinese New Year!

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

Nice and short announcement . Kudos to GlebsHP

I guess problem statements will also be short and nice.

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

@ admin whenever i log in into my account(manish_nit) everthing appears in russian, i have to manually right click every time and select translate to english. this creates lot of problem during contests...is there a setting in the codeforces website to do it permanently.

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

Is it national level competition?

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

    Seems to be city level.

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

      Thanks! I expected the problems to be much easier for a 7th grade local competition :). I lost too much time on the first problem, then B and C were probably just about right for a Div 2 contest (750 and 1000 points). Didn't even get to D or E ...

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

why A and B has the same points ?

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

Why not a combined division contest?

Great authors and of course great problems!

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

A contest by new( GlebsHP ) and old( Zlobober ) coordinator.

Hello Zlobober again!

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

Zlobober is backed :))

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

Great contest and perfect timing, do contest before dinner, then watching firework at mid night, happy lunar-new year.

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

Its Sunday morning in my country. Is it bad if I miss church for contest ? I like contest!!!

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

Today in China, it is Spring Festival, which is the most important festival in China, every single of Chinese will have supper with family. I hope in the New Year, Codeforces will be better and better~

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

i will have fun before the Chinese Spring Festival dinner.

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

Luckily I won't miss the Spring Festival Gala at 20:00.

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

hope it will be my last div2 :D

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

happy chinese new year！！！

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

Happy Chinese New Year(the Spring Festival) to everybody and wish Codeforces will become better and better !

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

Happy Chinese New Year~

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

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

What is the hacking test for problem B?

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

C seems so easy then A and B. I think C < B < A Due to overflow with binary search, 6 wrong submissions on A :\ I hope it passes now.

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

how to solve D ?

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

Who is the author of the Problem A? >.< And tester also >_< ?? No mercy, No mercy >_< :'( :'(

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

Now, I know why Russian coders are so good and accurate.

Nice problem-set, especially first problem.

Eagerly waiting for editorial for 4th and 5th question and hoping my solution for 1st three problems pass the system tests.

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

why this work on test

100000 symbols a

a

for 0,2 sec

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

    I tried hacking a solution like this and also failed.

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

    Find returns at the first occurence, so that takes O(1) time. erase can take up to linear, according to specification. But it is probably very optimized and the Codeforces servers are really fast (solutions with 10^9 operations can pass time limits) so it passes. Perhaps erasing the first character is faster than erasing from the middle, as well?

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

This was my solution for 2nd (div2) x = raw_input() y = raw_input() print x.count(y)

It passed the pretests XD, i dont think it will pass the final tests ... will it? EDIT : It passed!

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

I wonder how many A solutions will remain after systests :O. What was hack test for A btw

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

Very interesting problems. I got a lot of fun. Thanks to authors!

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

Ouch, the penalty for wrong submissions really showed through this contest because of the sudden spike in difficulty between C and D. Two wrong answers for A cost me 200 places in standing (from ~200th place to ~400th place).

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

too weak pretests these days :(

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

    With strong prtests, we can't enjoy hacking :(

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

    Actually, it surprised me, as I picked about 10-15 pretests in every problem. But still ,the number of cases seems to be much more than this.

    Many solutions will fail system tests, but this time it was unintentional :)

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

Is System Test gonna take long like in the past school contests? (until the closing ceremony)

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

hack test for problem one is : 2 100 100 50

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

terrible! I fixed some bugs on problem D and failed to sumbit in last several seconds.

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

Still can't go to sleep because I'm terrified of the system tests for A and B :(

→ Reply
»
10 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it 
        String gog = in.next();
        String tel = in.next();
        int ans = 0;
        int k = 0;
        while (k + tel.length() <= gog.length()){
            String s = gog.substring(k, k + tel.length());
            if (s.equals(tel)){
                ans++;
                k = k + tel.length();
            } else {
                k++;
            }
        }
        out.println(ans);

Its B. Will it pass sys tests?

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

everyone who solved 6-th COCI task of yesterday contest must solve the 4-th problem of today easily :D

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

Anyone solved E?

I have that idea: using binary heap (aka priority queue) we sort all possible collisions of frogs by (time_to_collision, id). After that in cycle we pop first frog, kill what she could kill, update her step_size, time_to_collision and put her in the heap again (also doing this for her precessor).

Stop when the next frog in heap can't kill anyone.

Should be NlogN. But I stuck in some range checks and didn't finished the solution.

Is it correct approach?

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

    I was thinking about the same solution, but moreover you have to update time_to_collision of previous frog (I mean the one, which gonna kill actual one).

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

      Yea, I've considered that ("also doing this for her precessor").

      In my implementation I simply put another copy of previous frog in the heap (instead of find-delete-putagain, for performance). It shouldn't affect the result, because its value will be strictly lesser than old one, so old one will be skipped somewhere in the future.

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

    It looks like the correct approach. Analysis will be published in the nearest 2-3 hours.

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

      Information like this should be added in the main post as it is very hard to find this kind of information in the sea of comments.

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

Wow very fast system testing. My rank jumped from 1000 to 500's before/after system testing xD Problem A is the cause :p

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

bad contest :-(

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

Putting "Guest From the Past" as an A problem was a wicked move.
I wish I didn't waste time on it :'(

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

just 699 who can solve a in the contest XD

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

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

    Yea, very tricky A and obviously_correct_solution in C :)

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

    I don't think this round had enough score differentiation. D and E should've been slightly easier, while A and C should've been switched (or C should've been made much harder, as it's unusual for so many people to get it). A wasn't actually hard, but it was pretty easy to make a silly mistake (a lot of people used it for hacks). The concept of C was roughly the same difficulty but the implementation was much easier (no derps).

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

    The eyes... Oh my god, THE EYES!!!

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

What was the solution to D? I thought of some messy solutions but could not find a clean one.

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

Realy A problem is tricky with Time limit and Wrong answer.

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

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

Could someone just tell me how to solve A? It seemed that A wasn't the easiest problem :(

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

    can do it in O(1):

    • if buying and selling a glass one is more expensive than buying a plastic one, only get plastics
    • if not, buy glass bottles until you can't do so anymore, then buy plastics with the rest of the money

    implemented here: http://mirror.codeforces.com/contest/625/submission/15870223

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

      I too thought that it should be O(1) but couldn't solve it, maybe because i freaked out because it took too much time to solve A. It was similar to this problem. I solved that problem by brute force but obviously here brute force won't work. :/ Next time I will try to find a better solution for every problem even if it gets AC.

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

      Is it any formula for O(1)? If the item costs b units and for returning you can get c units, then you can buy (n — b) / (b — c) + 1 items by n units?

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

574 — "A" = 1228 :(

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

Today I've seen a bunch of guys whose solutions failed systests for A but still they hacked everybody in their rooms so they got about 700-1000 points just from hacks. Turns out you don't have to actually solve a problem to get sufficient points for it.

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

    Yea, its pretty usual thing for hackerfests.

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

    I found my A is wrong when i have hacked 7 persons, finally my code is hacked but i still get 750 point..... btw, there is a guy write"cin>>n>>b>>a>>c", for which i got four times unsuccessful hack

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

The task are ok, but very bad for the div 2 contest.

Only the second task was on the level which it should be.

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

Thanks for timing!! Happy Tet Holiday!! <3 <3

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

Why i got WA on b??? this is my code, any help please?? http://www.codeforces.com/contest/625/submission/15862688

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

    ababc abc

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

    If current characters in S and T are different maybe you won't return to the begging of string T.

    I didn't tested your solution, but I think this is hack case for your solution :

    S='bbbc' T='bbc'.

    Correct answer 1.

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

      yes, you're right, didn't see that coming

      thanks lot...

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

A->C, C->A

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

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

I am very interested, whether someone got full score in official, on-site contest ?

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

.

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

for D I came up with an DP solution where dp[i][j][a][b] represents the interval [i, j] can be written as the format required and current i position number is a and j position is b, a, b < 10, the solution will exceed memory limits but I fail to simplify my solution.

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

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

it can take days for GlebsHP to write/translate the editorial (remember round 327). So, let's not wait for editorial and write our solutions ideas here.

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

Wow, outstanding performance: http://mirror.codeforces.com/contests/with/latisel

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

Hmmm what's wrong here? It failed at the aaaaaaa... case, where the answer is the number of a's, but my answered was one less.

codeforces.com/contest/625/submission/15869860

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

please, don't say anything before the contest.

Problem set would be too easy. or Problem set would be too hard.

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

I suspect the test data of problem A is very weak, since 15867499 passed system test. But it should TLE at this case: 1000000000000000000 2 500000000000000001 500000000000000000

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

DO we have editorials for this one ?

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

Can someone help me find the problem with my O(n) B?

http://mirror.codeforces.com/contest/625/submission/15877046

I feel like it's the correct strategy implemented right... but I'm getting off by 1 on test 26.

thanks!

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

    aaab aab

    Ans should be 1. Yours gives zero

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

      Thank you! I see the problem! Cheers. And as the_art_of_war says, the easier way is of course to just go the simple way so you can't run in to tricky edge cases like this.

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

    I think the length of second string is special so small that you can solve it with O(n*m) using two cycles. If you want to make solution with O(n) you should use special algorithms with strings like Z-function or prefix-function.Maybe there is more easier way to get solution with O(n).
    Sorry for my bad english.

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

Can someone give an idea how to solve 4th one ??

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

Three WA on Question 1 give me the way to hack 5 solutions :)

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

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

Happy Chinese new year!Can someone tell me how to solve the A question?I see some answer:they all used (n-b)/(b-c),but I don't know why?

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

Somebody help me! What the problem with that solution? Problem B.

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

Where is the editorial?

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

Author of B sucks: 15924760

→ Reply