fcspartakm's blog

Codeforces Round #387 (Div. 2)
By fcspartakm, history, 8 years ago, translation, In English

Hello, Codeforces! It's me again=)

I'd like to invite you to Codeforces Round #387 (Div. 2). It'll be held on Monday, December 19 at 05:05 MSK and Div. 1 participants can join out of competition.

This round is held on the tasks of the second day of the municipal stage All-Russian Olympiad of Informatics 2016/2017 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU.

Great thanks to Nikolay Kalinin (KAN) for helping me preparing the contest, to Tatiana Semenova (Tatiana_S) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Vladimir Petrov (vovuh), Alexey Ripinen (Perforator), Mikhail Levshunov (Levshunovma), Mikhail Piklyaev (awoo), Aleksey Slutskiy (pyloolex), Ivan Androsov (BledDest), Oleg Smirnov (Oleg_Smirnov) and Roman Kireev (RoKi) for writing solutions and editorials.

You will be given six problems and two hours to solve them. The scoring distribution will be announced later. Good luck everyone!

UPD The scoring distribution 500-1000-1500-2000-2000-2500

UPD2 Editorial

UPD3 Congratulations to the winners!

  1. 248926

  2. vigoss18

  3. haleyk100198

  4. ouch__casquinha

  5. peijinz

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

Comments Comments (117)
| Write comment?
»
8 years ago, # |
  Vote: I like it +147 Vote: I do not like it

Now this is what I call unusual time :D

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

5:30AM here...

It's cool :D...I'll try to join the contest...

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

    You are lucky, It's 4:00 AM here :D

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

      But I'm gonna stay awake till the contest starts :)

      PN. Of course it's just an excuse, I think I'll watch some movies and when the contest starts, I'll sleep :)

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

Why at this time?

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

    Bocause some people have day at that time.

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

      What people? ;)

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

        Half of the world

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

          What is the number of people from the selected regions are registered on codeforces? I am not trolling or something — I am really curious.

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

            It's hard to tell, Russia and China alone has over 10k users combined, but that also accounts for the western part of the country. (Western China should have much less competitive programmers AFAIK, but I have no idea about Russia)

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

Deleted

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

iam gonna wait whole night for this contest !!! lets hope this contest bring positive rating change to all of us... good luck everyone :)

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

Its 05:11 AM here in India.
I randomly opened codeforces to check editorials and I am surprised by this highly unusual timing.
hope to get + ratings. :D

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

Contest==> 7:35 am to 9:35 am (IST)

Exam==> 10:00 am to 12:00 pm (IST)

But gotta do it, coz cant miss a codeforces round!

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

I think that this is the time, you Europeans and Asians, in which you'll know what people in America suffer. Regular codeforces rounds are at 10:35 here in Mexico, and I always have to skip classes to take them. But not today. Today is at the perfect timing of 20:05

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

Never awake early for college first time only for CF.

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

8:30 PM, on a Sunday night? This has to be the most convenient time for a contest ever for NA people. Can we do this at least once every two months?

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

    Completely support that motion

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

I can't believe that I have just left my pillow and blanket to participate in this Round I haven't done that before, even to watch GOT

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

This round timing reminds me of TopCoder SRMs timing.

Most TopCoder SRMs were hold at time like this and I had to wake up after the mid-night to take it.

But I think it deserves.

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

i hope the round will deserve stay awaking for 4 am

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

Hopefully I can gain ~300 ratings from these two rounds so that I could rush a purple before the year ends.

Just 110 more to go =]

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

    Congratulation！ U achieve it

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

      Thanks! I think this is my first time that I don't fail any system tests, usually I look cool pre-system test then suck hard.

      PURPLE HERE I COMEEEE

      Edit: Woahh, 2000+ rating? That was unexpected!

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

It's 18:35 here. But I think it's a little early?

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

    Sorry, it takes some mistakes...I thought it was #386

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

Can anyone explain how to do D? Is it dp (I was using a 3D dp table but couldn't implement it properly)?

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

    No need of DP, you can do it with a min heap. Store the difference(number of summer days) between two consecutive winter intervals and process them from lowest to highest.

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

      Ah that's a lot simpler than I thought it would be. And it makes sense when I think about it.

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

    No, greedy works. Split the array into segments of negative values. Sort the distances between consecutive all-negative segments in increasing order and just keep using winter tires to join them.

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

    the given test case in D , third one answer shouldn't be 2. If he wants minimum tire changes then he must club summer days with winter , if possible . According to that ans can be reduced to 2.

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

      But then he would have used more than k days which he's allowed for winter tires.

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

    I believe greedy works: on all the negative days you have to use winter tires. Pick the smallest interval (non-empty) that is bounded by two consecutive winter days, and fill use winter tires over that interval. Of course you have to account for the corner cases and whatnot.

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

    Mine was a greedy one. I just kept cancelling any swapping between the two days with negative temperatures and the distance between them is the smallest until I run out of Winter tears. But I am still not sure that this solution is correct. :D

    UPDATE : mine is incorrect :D

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

    Greedy works just as other comments have stated, remember to always consider the final segment of non-negative temperature AT THE VERY LAST. Now I thought it a bit more I just missed a hacking opportunity on someone who sorted the final segment with the others.

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

Nice Contest.

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

Almost no hacking in this contest. There were literally no hacks in my room :o

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

    I'm just gonna hope that means the pretests were decent.

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

      I also think its because the solutions to the test cases were explained clearly. Also most tricky cases seemed to be given there too.

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

My idea around D was something like this:

Let's assign Winter Tyres W to all negative temperatures and Summer Tyres S to others. Let initial answer be the worst case of exchanges required.

Now, if we convert a segment which is of the form: WSSS...SW to WWWW...WW then we reduce 2 exchanges. So, we try to cover the smallest segment first and greedily try to reduce exchanges this way.

My implementation gave segfault on Pretest 3. Dunno if this would work — can someone point out where this could go wrong?

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

    this was my idea too and got ac after contest. just remember to add first exchange and last exchange(which if happens, both will be 1).

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

    If you have the last few days covered by S, consider replacing it with W to save one switch. Since you only save one, which is less than the normal two, check this case at the very end.

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

TFW you know that problem F is a problem about binary search and combinations but you suck hard at combinations... WITH 90 MINS LEFT.

void recursion(struct me, int remainingTime){

if(remaingingTime)

       remainingTime -= 0.1;

}

I thought I was stuck forever.

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

    Can you give an outline of your approach?

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

      Use binary search to find the answer, and count the combinations of non-interesting numbers smaller than var(mid).

      I didn't manage to find the combination formula though.

      Use a vector of decimal based numbers will help during processing.

      Edit: Whoops I was wrong. Seeing the tutorial reminds me that using dp to count the combinations is a common technique which I learnt in other round's tutorial...

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

How to approach E? I made a recursive function but could find no way to optimize it.

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

Greedy... greedy everywhere

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

Bye expert! Just I was some hours blue

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

    Just compete tomorrow and get it back!

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

I hope there will not be another contests at this time again.

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

    I think it is a cool time during semester break. It's morning in eastern Asia so I could join the contest with a fresh brain instead of a tired one on the usual time.

    The amount of people available on this time slot is really low though...

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

      I agree with you about participating with a fresh brain but it's not a semester break for everyone. I'm working on semester projects now and it's 10 days away from the beginning of the semester exams.

      I don't know if it's a good time for many members or not. but I didn't see anybody upset from the usual time.

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

    What time is it now in your country?

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

C failed systest

  • y tho bro?

opens the code after 10 secs

  • aaah, f***, I forgot to ignore the one with insufficient number of servers...
→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Such quick system testing !!!

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

What is problem D test 31? Any ideas?

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

    I think it's some thing like this : 

     8 7
     -1 -1 -1 0 0 -1 -1 0

    Considering segment [4, 5] gives optimal answer even though it's length is greater than segment [8, 8].
    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Wohooo! First place in my room for the first time! ...and I got WA on problem A because of uninitialised variables, how embarrassing :P

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

    A reversed case for me. I saw someone's code could possibility cause RE since it could check out-of-bounds values, but I didn't have the courage to hack that guy.

    He coded something like this:

    int d[4], z = 0;

    while(d[z] == 0)

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

why my source is runtime error in Problem E? http://codeforces.net/contest/747/submission/23126016

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

An unusual timing for the contest, the number of problems, and system checking was so fast! I like this contest

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

Last ACC in the Round :D

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

Is here anybody who solved D with binary search? :D

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

you know it was a greedy contest when nearly 400 solutions fail system test for D.
wasted whole time on D in search for a O(n) dp solution. :(

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

    It's so hard to set a question which denies O(nlogn) while accepting O(n) though.

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

      haleyk100198 you did very great today.
      How did you solved D and E so fast?

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

        For problem D I got a little bit lucky to notice the greedy approach, so I only have to spend some time on refining the code to handle the corner cases.

        For problem E, managing a file tree is a quite common practice problem. (I am surprised that it showed up as a regular round problem E)Whenever I see such a problem I just go straight for stack, and there's no other tricks needed so I got it almost instantly.

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

Good morning! can anyone explain D for me? is it DP? i wanted to do this with 3x dp2D but i can't!

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

    Check the comments above, there is a populated comment above which should guide you how to solve it with greedy.

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

So excited about being a Candidate Master!!!

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

although i solved 2 questions ,_ better than every time_, my rating points decreased ! could anyone explain to me the rating process and why i decreased please ?

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

Can anyone help me why 23126693 got WA?

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

    You made a mistake to consider the final segment of non-negative days with other segments.

    For example:

    10 8

    0 -1 0 0 -1 0 0 0 -1 0

    Your code considers to use the winter tire on segments : [2, 5] and [9, 10] (1-based), as it recognises the last non-negative segment [10] has the best greedy value, but the correct answer should be [2, 9] as using winter tire on [6, 8] further reduces the result.

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

    try this case: 

     8 7
     -1 -1 -1 0 0 -1 -1 0

    Answer should be 2 instead of 3.
    → Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

In problem 747E - Comments, my code receive TLE in maintest 9. However, when I resubmit the same code, it get TLE in test 29.

Here is my code in the contest: 23123300.

And here is my resubmitted code after the contest: 23128262.

You can use compare button to check whether they are same.

I so worry that may people could fail system test because it (not me because I still fail with test 29)

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

    I don't think this should be a concern as your code was very close to TLE on test case 9 in both submissions. It is known that CF running time has a delta of around 30ms, which should not cause problems to most submissions. (As always, you run a risk of submitting non-optimal solutions)

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

http://codeforces.net/contest/747/submission/23124311

Can someone help me find out the mistake i made in problem C .

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

    You should prioritise using the unoccupied machines with smaller ids, instead of the ones who were released earlier.

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

    I think your mistake is that you do this (servs[i].f=(t+(d-1));). If only x (x<k) servers are available, you print -1 but don't reset the ending time of those x servers.

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

I woke up early for the round 386, waited for this round and will wake up early tomorrow again for next round, hopefully there are more often 'daily' rounds

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

why for this input:

10 5

1 1 1

2 1 3

3 2 3

4 1 1

5 2 1

answer is : 1 1 5 4 5, but not 1 1 5 4 7 ?

at second 1, there're 10 unoccupied servers and we need to occupy 1 sever for 1 second , sum -> 1;

at second 2, there're 10 unoccupied servers and we need to occupy 1 server for 3 seconds(sec. 2,3,4), sum -> 1;

at second 3, there're 9 unoccupied servers and we need to occupy 2 server for 3 seconds(sec. 3,4,5), sum -> 2 + 3 -> 5;

at second 4, there're 7 unoccupied servers and we need to occupy 1 server for 1 second, sum -> 4;

at second 5, there're 8 unoccupied servers and we need to occupy 2 servers for 1 second, sum 3 + 4 ??

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

    Notice that you should use server 1 and 4 for the final task.

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

For problem E, I traversed the string once and stored the strings at the index of its level in a vector and later displayed the contents of vector level wise. The total memory taken by the vector will then be equal to the memory taken by the string.

But I am receiving a runtime error on system test 26.

http://codeforces.net/contest/747/submission/23129959

Is there something fundamental I'm missing out? Thanks for any help in advance.

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

    I am not sure about this, but line 105 seems to cause out of bounds problems.

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

    Its due to out of bounds.
    Use this while condition instead- while(i<n && s[i]!=',').
    Here is your AC code with the modification-23130499

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

Hello, I have a small doubt regarding problem E. My submission 23125639. The code for converting string to integer is for(int i=0; i<lol.size(); i++) cnt[(j-1)/2]+=(lol[i]-'0')*(int)pow(10, lol.size()-i-1); This is giving me wrong answer on test 18. But when I replace this with the inbuilt function, atoi(), the code is getting accepted. I'm unable to understand why. Help would be appreciated

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

    The power function returns a double type value which on conversion to an integer might cause some precision issues. Use a custom power function instead.

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

      For powers of 10, I don't think there is any problem with precision. If there is an error, it'll occur in the decimal places and it'll be ignored. Is there any case where a this conversion won't work? Thank you for your reply

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

    pow(int, int) actually calls pow(float,float) (or pow(double,double)). There are two problems:

    1)float can represent correctly (with no error) only integers with less than 6 digits.

    2)int(0.99) is 0 and pow() gives us only estimated value. It might give you 9999.99999 when you ask for pow(10,4). And it will be rounded as 9999.

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

      I forgot that pow can return a number slightly lesser than the number. Thank you for the clarification.

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

    Besides the precision problems, I think you should also learn the stoi (and stoll, stod etc.) functions, that helps a lot with converting string to numerical values. That saves a lot of time for coding a function that does the same thing.

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

thx a lot for these consecutive contests (#387,#386,#385,#384)...it helps our ACM team for ICPC-Tehran Region

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

Doesn't the problem B statement says coordinates to be lie between -1000 and 1000. But the output of the judge is considering the coordinates outside this range.

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

    I assume that you are talking about 749B instead of 748B.

    The range of x, y coordinates is only applied on the input, you can output any legit integers in the output.

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

Hey, can anyone tell how to solve D using DP? It has a DP tag, and I am practicing DP questions, so I would be more than grateful to know about that! :D

→ Reply