komendart's blog

Codeforces Round #353 (Div. 2)
By komendart, history, 9 years ago, translation, In English

Hello, everyone!

Codeforces Round #353 (Div. 2) will take place tomorrow on the 16th of May at 19:35 MSK. I tried to make interesting problems, hope you enjoy them.

I'd like to thank GlebsHP for his help in preparing problems and MikeMirzayanov for Codeforces and Polygon.

Good luck!

UPD Scoring 500-1000-1500-2000-2500

UPD Editorial

UPD Congratulations to winners!

Div. 2

  1. mimirrow

  2. Salvare008

  3. orzchimo

  4. student_hh

  5. Pain_Konan

Div. 1

  1. ksun48

  2. sugim48

  3. KrK

  4. cgy4ever

  5. nfssdq

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

Comments Comments (139)
| Write comment?
»
9 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Good luck and have fun

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

Is it rated?


First!!!

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

    My congratulations!

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

    finally ,there he is

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

    مبروك

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

    What does rated mean? Excuse me but I'm new to this website.

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

      Welcome the CodeForces!

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

      It means that you get positive or negative points depending upon your performance in the contest and your rank changes to Newbie, Pupil, Master, Grand Master ... etc

      Currently you're unrated, when you participate for the first time your score is assumed to be 1500, and the points you earn will be added to it

      Later contests will add to your actual score

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

wow. short and good description. hope to see some interesting problems :)

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

The least words with the most clarity is the best form of expression.

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

komendart and his short announcements

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

Will Codeforces Round 366 (Div 2) be yours?)

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

    Stop downvoting! I don't want to have negative contribution.

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

      You don't want, but you will have.

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

.

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

    What is misleading about his response?

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

      .

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

        deleted

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

        He said that for a valid solution, there has to be at least one nut. This means that if there is no nut, there is no solution. It doesn't mean it is guaranteed that there is at least one nut. His response was clear, so you should blame yourself for misunderstanding what he said. :)

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

    "Please note, that if Bob doesn't make any breaks, all the bar will form one piece and it still has to have exactly one nut."

    I don't find it misleading. This sentence means that it's invalid way if we don't make any breaks and bar hasn't nuts. And this sentence would be excess if it was guaranteed that bar has at least one nut.

    Everyone who asked similar question got this sentence as response. By the way, it can be with the same probability my or GlebsHP's response.

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

    I also failed system tests because I was mislead by the exact same answer you got. I'm still not quite sure what I think about it, it would've been easy enough to just answer yes or no to the question, since people were confused and asking directly, but I guess I just also learnt from it, and from now on will always include an if statement for special case like that if I'm in doubt whether it's in the test cases or not.

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

Best Wishes to All World Final teams. Hope this contest will be warm-up contest for Them.

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

Simple and clean description :)

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

I really enjoyed your last contest! Thanks for setting this contest.

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

Hope for doing much better.

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

my first time here , hope to see some interesting problems

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

Give me Downvote.........

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

Hope to pass Div2/C for first time :)

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

I don't have internet connection and electricity in my house, had to travel to another city 3 hours away because of contest. Hope the problems are really interesting please.

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

    You must be really excited about Codeforces :)

    It's only a minor contest for most people

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

      If it's minor contest for you, keep it to yourself. Do not discourage others by posting such illiterate statements. It's major contest for all Div 2 contestants who have a chance to increase their rating and eventually end up in Div one one fine day after performing well. !

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

      Well, I'm sorry you feel this way. But codeforces is more than a minor contest. It is a community of dedicated and hard working programmers some of which work for some of the best companies in the world.

      Before joining codeforces, I had did not know about many concepts in programming but thanks to codeforces I now do and am learning and improving daily.

      I made a lot of cool friends here on codeforces and have even been contacted a recruiter through due to my blogging about codeforces.

      So no its not just a minor contest for me. It is a chance to train with different programmers from all around the world and enjoy doing it at the same time.

      Thank you.

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

      šupak(azzhole)

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

What is the most important of it? "Interesting!" I hope I can enjoy it with my friends then, though I am a green hand.

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

Nice and short announcement....fine. :-)

Hope , closing ceremony time will also be as short as the announcement ...... plz

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

We will rise !

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

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

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

My first contest. Feeling Exticed

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

I think one of the problems is about shortest statement :D Have a nice contest ;)

→ Reply
»
9 years ago, # |
  Vote: I like it -22 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
9 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Scoring should be 500-1000-25000-500-2500 :)

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

    500 — 1000 — 2500 — 1500 — 2500

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

    I think it depends on perspective. I took 18 minutes to solve C, but 50 minutes to solve D. Mainly due to my inexperience with STL. While the idea for C is a bit less intuitive than D, the implementation is relatively more simple.

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

How to solve problem C ?

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

    Let us note by T[i] the transfer from i to i + 1 in some solution. Then the following equations must be satisfied:

    A[i] + T[i - 1] - T[i] = 0.

    for i = 0, 1, ..., n - 1. Suppose that we know T[0] = x then T[i] = A[i] + A[i - 1] + ... + A[1] + x.

    We can manipulate x and we want the maximum possible number of T[i] to be 0. The best choice for x is the opossite of the most frequent number in the pref_sum table.

    So the answer is n - k where k is the frequency of the most frequent number in the sequence A[1], A[1] + A[2], ..., A[1] + A[2] + ... + A[n].

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

      Wow! Nice solution!

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

      what do you mean by A[n], I think you meant A[0] since you started indexing from 0.

      Anyway, thanks for the neat explanation!

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

How to solve C? I was finding maximum consecutive zeros(taking circular queue in consideration) and then subtracting it from n — 1. It gave WA on pretest 5.

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

    incorect:

    9
    0 0 0 0 1 -1 0 1 -1

    correct ans: 2
    your ans: 4

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

      i looked for consecutive zeroes that have the same prefix sum and got the best score from: n — number of zeroes with that prefix — number of consecutive intervals. Didn't work, but it does work on this test :(.

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

    test:

    1 -1 0 0 1 -1 0 0 0

    answer is 2

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

    Did you see that it was a circular array? :)

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

    Well, I passed pretest, though I don't know if my answer is correct or not. Here, at first we take cumulative sum in another array, say, cum[i], where cum[i]=summation of initial array from 1 to i. Then, we check for the number which has maximum occurence in the cumulative array.Let the number of times it has occured be max. The answer is n-max.

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

    same here!

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

what is 4th input in E?

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

I'm wondering if there is something very simple we can do for C, or if it was truly as hard as it seemed. Harder than D anyway.

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

My heart was broken.

Unsuccessful hacking attempt -50

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

    Welcome to Codeforces, land of the trolls.

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

Very nice problem set!!

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

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

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

Wow system testing started just after the contest finished! so fast! wonderful! :)

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

why I am always forgetting to use long long :'(

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

    You maybe are so excited that you have found the solution, that you don't think about tricky test cases. You just go strait into the code. It's a common mistake. Just make sure you spend 10 seconds thinking about data types that you are going to use in your code when you solve a problem. Spending very little time double-checking your solution is worth getting wrong answer, specially in CF that tricky test cases are not usually included in pretests.

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

I'm curious, as to what your strategies were for C. D seemed more straightforward but C was so interesting I couldn't leave! Mine assumed that there are four optimal starting positions, and I just looped manually. Most likely my assumption is false; anyway what were your ideas?

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

I am getting Time limit exceeded on Pretest 6 on Problem D although my approach is nlogn: http://codeforces.net/submissions/Ishan.nitj

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

Very nice contest, the problems were great, especially problem D. I don't know if I have the right solution though (I didn't send a source :( ), I have a solution involving Segment Trees with Lazy Propagation. What was your solution to D?

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

Hacked 3 times in Div2 A by the same guy... really? Link

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

How to solve D at all? Treap? How to build BST in O(N)? Or some kind of completely another solution?

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

    No treap

    make map of intervals (l; r) -> value at parent list. Initial (0 10^9 + 1) -> -1; 1) read num a;
    2) find interval (l; r) -> ans for which: l < a < r;
    3) if ans > 0 print ans;
    4) add interval (l; a) -> a and (a; r) -> a

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

    Suppose you're adding x. Find a = smallest number bigger than x, b = biggest number smaller than x (between numbers added until now). Now the answer is the one (of a and b) that was added more recently. You can find a and b with a set.

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

System testing was very fast !!!

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

Time complexity for 10^9 passed in codeforces judge when I tried to hack the solution in problem A by giving a=1,b=1000000000,c=1 his code was if(c>0){ while(a<b)a=a+c; if(a==b)cout<<"YES"; else cout<<"NO"; return 0; } But when I provided the test case a=-1000000000,b=1000000000,c=1 I got successful hacking attempt.

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

    on servers 10^9 fast operations go for ~0.8 seconds

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

    I also hacked a solution for TLE, but before doing so I used the Custom Test Tab and saw, that 1 1000000000 1 gives Used: 561 ms, 2036 KB, whereas -1000000000 1000000000 1 gives Used: 1123 ms, 2036 KB and since time limit was 1 second, just the larger test case is valid for a hack.

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

Problem C looks very similar to SRM683 Div1 Easy, O(n) Solution for that problem can be found here. The solution for this problem is also similar

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

Problem D was minor change from a recent HackerRank contest problem, which in turn also appeared in India IOITC 2015 Test 1, and also in some iteration of the COCI(saw it on PEG Judge, not sure which olympiad).

EDIT:

COCI, not CCC, my bad.

  1. HackerRank version

  2. COCI08 #3 BST

  3. India IOITC version

  4. Also on SPOJ, wow

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

Is the contest unrated or we just have to wait some time for the system to update?

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

Why does this code doesn't give RE on 10 10 0?

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

    Division by zero (temp % c)

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

    Maybe after seeing that temp is zero (temp%c), the rest is ignored, in the same way while(!q.empty() && q.front()==0) doesn't give RTE because if q.empty() is true, the check q.front()==0 is ignored :)

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

      But it doesn't give RE on test 0 1 0 also!

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

    You may not write ( number % zero )

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

Is the contest rated or unrated

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

    It is rated. I think they are finding the cheaters, my rank just decreased by 2.

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

My hacking attempt on http://codeforces.net/contest/675/submission/17938245 failed for testcase 1 1000000000 1 because the solution produced correct answer in 826ms. So close but yet so far.

-1000000000 1000000000 1 took 1450ms. Should have tried the largest testcase.

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

When do colors change?

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

Hi Friends I am sure this a trivial question, but it would be really nice if someone could look into this. I gave these two submissions 17956219 and 17953624 for problem B div 2. Both are identical except using long long and long data type. But the solution with long gave wrong answer for 

100000 2 2 2 2
Output
1410065408
Answer
10000000000

What could be the reason for this?

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

    long = from -2 147 483 648 to 2 147 483 647 long long = from -9 223 372 036 854 775 808 to 9 223 372 036 854 775 807 I made one hack using this

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

    Overflow is the reason. The answer may be 10**10 if sum=10*5 and the number of number that can be used is 10*5. Long data type stores 4 bytes of data whereas long long data type stores 8 bytes of data and 10**10 doesnt lie in the range of long data type. Thus an overflow occured and thus your answer was wrong.

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

    the variable is long long ，but you define int.

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

What a TLE!

I used the generic upper_bound instead of the class specific 17957229 vs 17957298

To have into account in future implementations.

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

    Generic upper_bound on non sorted random access containers takes O(n) time. Protip: google C++ upper_bound.

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

      Yes. In fact I found that reason after google a little bit, then I corrected it. I wasn't aware of that.

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

why in the result table some cells have a color background? http://prntscr.com/b4vv80

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

    and others are red http://prntscr.com/b4vw4r

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

      Because. You was be in the same room with them and you looked their solutions to hack. So green color shows that you look this solution and maybe red color means that it is the last solution you check for hacking.

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

        Yes, I check and they are both at the same room with me. Looks like you're right, thanks!

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

Thanks a lot for your efforts and interesting problems :)

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

Why ALL my AC code was skipped?The solution gets accepted after resubmitting! Since I didn't use other accounts to submit the same solution or copy others code, how can I ask to retest my code.

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

https://community.topcoder.com/stat?c=problem_statement&pm=14174&rd=16653

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

Great DP in Problem E. It makes proper use of Greedy Algorithm!

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

A splendid round!!!But why not have some weekend round like before?It's really difficult for those students in other regions to get up after 12 during workdays.All in all,just suggestions.

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

Can someone tell me why using array to build BST causes Runtime Error?

I feel a little confused,and my submission was here

I watch others code which use the similar way and find that they also got RE in

test4

input:

10 991309218 517452607 870021923 978357992 136426010 10601767 302627526 883615372 163475700 600546765

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

    Eh, I have not studied BST nicely(one more reason to concentrate in classes :P) but I think you are trying to make a tree using array which will require 2^n space(here n<=100000).

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

The use of unordered_map in problem C leads to a TLE . Why is that ?

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

    Hashmaps have the worst case runtime of O(n) when elements get hashed to the same value multiple times.

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

Please post the Editorial.

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

WTF why is Problem D statement not available in English?

→ Reply