ch_egor's blog

By ch_egor, 6 weeks ago, translation, In English,

Hi everybody,

This Sunday there will be a Moscow programming competition for school students of grades from 6 to 9. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594).

Round will be held at Feb/23/2020 12:05 (Moscow time). You will be given 5 problems and 2 hours to solve them. Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.

Problems are prepared by KiKoS, DebNatkh, grphil, Sehnsucht, voidmax, isaf27 under my supervision.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1:

Scoring distribution: 500 — 1000 — (1000 + 1000) — 2000 — 2500

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

UPD2: Winners!

Div. 2:

  1. SARS-CoV-2
  2. kvk1920
  3. Crazy_Diamond
  4. KwanghyunOn
  5. pufanyi

Div. 1 + Div. 2:

  1. amnesiac_dusk
  2. jiangly
  3. SARS-CoV-2
  4. wiwitrifai
  5. cookiedoth

UPD3: Editorial

Tags 622
 
 
 
 
  • Vote: I like it
  • +197
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

Nice!The start time of this contest was very friendly to the Chinese. :-)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    It's hard to see the round at this time.I hope it's easy.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Why are Chinese always ranting about start time smh ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Most rounds start at 9-10 pm in China, which is quite late for some people

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it's very friendly to the Indians as well.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Hope every Chinese who will take part in gets good grades

»
6 weeks ago, # |
Rev. 5   Vote: I like it +29 Vote: I do not like it

I still have questions...

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -46 Vote: I do not like it

    ///786/// maybe it will be the usual Div 2 or, Div 3

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    It can be a new contest format or something like global rounds(div.1+div.2)

»
6 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

Not colorful testers, but good testers.

»
6 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

///786///

hope to see another good round

all the best to all participants :D

»
6 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

is this rated contest?

»
6 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

I just wanna be specialist again, so I hope it will be easy to solve C at least :)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    all the best :)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Keep pushing and Good Luck. You'll be the best. And I wanna becmoe purple too :).

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seems like you have been granted your wish ...

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yep. Becoming a candidate master is the gladdest thing in these days. And good luck && high rated for you in next contest.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    How do you think about (1250+750)? Perhaps solution of Problem C will be short but difficult.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

bonne chance

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

3am for people in North/South/Central America, but I'll surely do a virtual participation when I wake up :). Good luck everyone!

»
6 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

It's been a long time for Chinese to participate in a proper time.:-D

»
6 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

why do some of the rounds listed have div1 while some don't?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    as lots of people can make div.2 problems, but div.1 is something else, much harder and much more important. also if you can make div.1, then you will add two simple problems to it, then it would be div.1 + div.2, but you cant add div.1 E/F that much easily. and its the reason that we dont have too many div.1 only rounds, but we have lots of div.2 + div.1 rounds and more div.2 rounds.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

One year after Codeforces Round #541?? And the same author?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally, a reasonable time for us EST CFers!

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Opencup and round at the same time, not cool man, not cool

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

It's sort of crazy to have two rounds one after another, with an interval of only a couple of hours. I'm so excited! LOL

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    have the same feeling :), what if we participate in this round as a warm up for the next one?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The second round is, however, time-unfriendly to Chinese participants. Rounds like this one are known as "sudden death round" among Chinese OIers since they're in the midnight. I guess my parents won't let me take part in this round. (sad face

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i havent ever seen a cf round that has bad start time for us, love Iran :D, this contest was 12AM, and the normal cf round are about 6PM here

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Damned. We almost always have to burn the midnight oil to take a cf round.

»
6 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

Let's hope this contest has some actually good problems and not some garbage with cows everywhere.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "actually good problems and not some garbage with cows everywhere"

    try creating one on your own, get a pen and a notebook and only look for the information that is actually needed

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Disagreed. Cows aren't making problems garbage. I think they are making them easier to understand.

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Wish to see questions with good learning aspects.

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Nice! The start time is great!

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

All the best everybody.

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Lol, score distribution can be really useful for on-site participiantes, You know

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Please let me add 5 points

»
6 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

The start time is so nice to Chinese! Hope to be a Master or a Candidate Master!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah <3 I am ready and exiting to join the contest !

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No Legendary registered!!!

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks for the Round, but I left when I failed to solve pretests for problem-A , and didnt even understood problem-B in first 30 mins :(

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    That's goodbye rating for you my dear son.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      How come...??? Why would I make a submission if I haven't solved for the pretests.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        it's too early to give up. your rating doesn't make any sense if you give up like this.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hmmm, i guess old age has gotten the better of me.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's so demotivating when I give up the contest so early... :'(

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Question plz! Why is this contest Div.2 instead of the first five problems of Div.1+Div.2?

»
6 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

B is very nice. It should've been C though.

»
6 weeks ago, # |
  Vote: I like it +177 Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +68 Vote: I do not like it

D̶i̶v̶ ̶2̶ ❌

Div1/1.5 ✔️

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    haha :D

    I cant solve B for 2 hours ;-; How stupid I am for a math problem

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      nah me too

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

      dude i couldnt solve problem B, look at my rating, so that i gave up writing the segment tree on C2 and left the conest :(, the gravity is pulling my rating to newbie

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Are you going to drop the rank like I am now ? ;-;

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I know B is not always easier than C but I still try all of formula I can think to solve B first and I failed ;-;

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        New experience for me: Change problem if you think you cant approach furthur although you tried your best for an hour ;-; What a math problem ;-;

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I hope we will rank up the next contest :D Good luck <3

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          thx dude, no hard-feeling, its just a contest which wasnt good for us, maybe next round well get +300 rating(shotor dar khaab binad panbe dane)

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            Good luck ! Hope I can solve A-B-C and get +50 too

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              And I solved A-B-C <3, how about you

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              But I didn't feel too good, since it took me 40 minutes to understand B, and I submited wrong code for C because I was hurry ;-; If I have more time, I hope I can still solve D <3

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C2???

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

B is a very nice problem :)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    No, it is a horrible index fiddling with absolutly nothing to learn. You might be happy if you solve it, but that does not make it nice.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not the solution. I meant the idea of the problem is nice. I agree. There is nothing to learn from it.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

is the solution of C2 segtree+binary search.got tle with that

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    instead of seg tree do sparse table

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    For each position i you should calculate the total size of increasing buildings ending at that position.

    Which is equvalent to the Next smaller element problem.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    My solution is O(n), you can count all values using stack

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Simply segment tree will do

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain the Segment Tree approach for C2?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for each element , we need the closese element on the left of it and on the right of it that has value less than equal to it.So maintain a minimum seg tree and for left and right both elements for each index, do it seperately. For elements in between ,they contribute value equal to element value to its answer. For the rest of elements,answer is already found before. Say for left partition, ansL[i] = ansL[left] + arr[left] + (i-1-left)*arr[i].Same is done for right partition. And then ans[i] = ansL[i] + ansR[i] + arr[i].

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. It is sth like lineral dp + non-decreasing stack. The time complexity is O(n). Plus, I think n=500000 is aimed at preventing some O(nlogn) solution.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used a different approach.

    I built the cartesian tree of the array in O(n). Basically, each subtree represents a contiguous sub-array. And the root of a subtree is the index of the minimum element of the subarray. It's left and right childs are respectively the sub-array to the left, and to the right of the min.

    Once I have that, I compute the solution for each subtree. Noticing that the buildings size must be constant either on the left subtree, or the right subtree. So I can calculate the answer in O(n) for all subtrees.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    You can do binary search on the segtree and use logn time instead of log^2n. You can check my submission https://codeforces.com/contest/1313/submission/71698666

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can be done using a stack. First, we calculate the maximum score we can make from the left side (all buildings in non-decreasing heights) and the right side (all buildings in non -increasing heights). We can do this by maintaining a stack with increasing values. Then taking maximum among all index for left[index-1] + right[index].

    Link

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve c1 ? i got wrong answer on pretest 3 my code: 71682077

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try putting each element as peak element and the left part forms a increasing segment and the right part a decreasing segment, compute maximum answer for all peaks, and then take the maximum one.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Form min place let $$$lx = min(n-x-1, y - 1), ly = min(n - y - 1, x - 1)$$$. $$$Ans_{mn} = max( y-1-lx, x - 1- ly) + 1$$$. For max place $$$lx = min(n-x, y - 1), ly = min(n - y, x - 1)$$$. $$$Ans_{mx} = max( y-1-lx, x - 1- ly) + lx + ly + 1$$$. Maybe its too complicated, but I came with only this solution

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow! Thanks.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      @kun4ik I did similar to this, can you tell where I went wrong, here is my submission: my submission

      @kun4ik why dont you consider the additional min(n-x-sg1, n-y-sg2) which is there in my code which denotes pairing of those whose performance is worse in both contests? similarly for max?

      Finally found the answer : I didnt check if some terms went negative, so they needed to be 0 capped.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow nice <3

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It will not work for a==n and b == n

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve B? It took me over an hour to even come close to a submission. My logic was to casework on N, and the sum of A & B, but I'm pretty sure this isn't correct. This is what I came up with.

if (N == 1) {
    cout << 1 << " " << 1 << endl;
    return;
}    

else if (N == 2) {
    if (min(A, B) == 1 && max(A, B) == 2)   
        cout << 1 << " " << 1 << endl;
    else if (A == 1 && A == B)
        cout << 1 << " " << 1 << endl;
    else
        cout << 2 << " " << 2 << endl;

    return;
}

if (N >= (A + B))
    cout << 1 << " " << (A + B - 1) << endl;
else {
    cout << ((A + B + 1 - N)) << " " << N << endl;
}
»
6 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

cool contest but not a good contest problem C idea were really cool but problem B....

»
6 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

difficulty balance be like :

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 8 in C1 be like ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    int overflow

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just a guess, maybe something like this:

    9
    0 5 5 5 5 5 0 6 0 0
    
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also get WA in test 8.

    I use the maximum number to construct answer, which is totally wrong. The flaw of my solution is that it can't detect the nearby situation and went wrong, like:

    10 5 64 62 62 14 84 59 13 1 15

    64 should be the summit of the answer, but I got 84.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anoyne else solved c1 but couldn't A??

»
6 weeks ago, # |
Rev. 3   Vote: I like it -102 Vote: I do not like it

i got WA on some testcase in problem A.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is what I was about to go for, then made triplets using sruct lolol

»
6 weeks ago, # |
Rev. 3   Vote: I like it +113 Vote: I do not like it

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Quite tough as a Prob.B :(

    I got stuck with that for 40min, with three Wrong Answers.

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

      lol i definitely don't deserve to be CM

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And I also dont deserve to be a specialist.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i have the same feeling dude ;(, after doing nothing on B, there's no reason for me to stay violet

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is intended sol for D dp[index][mask] which means we use chosen segments, corresponding to mask, covering point of coordinate index? My code is a mess, I need to transform mask for each transition, there has to be a simpler solution.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would you transition to a new index?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Find the intervals that cover both points, shift mask the appropriate amount

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I pretty much got the same, including the mess and the fail at pretest 2 (and couldn't correct in time)

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      BTW, I fixed pretest2 WA by fixing test:

      1 3 1

      2 2

      Might help you :)

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    You can preprocess the intervals in order and map each interval to one of the available bits:

    whichBit.resize(n,-1);
    vector<bool> used(8,false);
    for(int i=0;i<at.size();++i){
    	for(auto interval:out[i])
    		used[whichBit[interval]]=false;
    	for(auto interval:in[i]){
    		int bit=find(used.begin(),used.end(),false)-used.begin();
    		whichBit[interval]=bit;
    		used[bit]=true;
    	}
    }
    

    If you want to set / unset an interval, you should use (1<<whichBit[interval]).

»
6 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

Problem B gave me atcoder vibes.

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Was D something like $$$dp[pos][mask]$$$ denoting max happy children for current position and the mask of the intervals taken?

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

System test will run after 30 minutes? Or right now?

Reason —

"Due to the official competition source codes of other participants will not be available for an hour after the end of the round."

»
6 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

Once editorial is published, I'm going to learn much useful stuff

and you know, problem B, I won't let you discourage me!

»
6 weeks ago, # |
  Vote: I like it +125 Vote: I do not like it

Thanks for this contest. I know my real rating now. I can't solve a Div.2 B for an hour.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Haha :D

    Me too ;-; I thought that B is always easier than C so I tried my best to solve it, and failed ;-;

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually I spent almost 40 minutes on Problem A after I solved B & C. I did not see the condition that at most one portion is allowed, and was completely stuck.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh, and I can only solve the max position of B in first 10 minutes but 1h50 minutes left I cant solve the min position ;-;

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hope you will solve A, B, C in 45 mins in the next contest :D

»
6 weeks ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

Does anyone have any ideas about div2-D/E?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    D, can you explain sample test?

    "In this case all children will be happy except the third." The third kid gets 3 candies, which is odd, so it should be happy. Kids 2 and 4 get two candies, should be unhappy. ???

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Only 1-3 and 3-5 are chosen, so 1,2,4,5 will have one candy and thus be happy, while 3 has two candies and is unhappy.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a hunch that solution of C2 could be related to dilworth theorem?Is it true?

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

For the problem B

The worst position is min(n,x+y-1) Reason: we can always arrange (first k natural)(we have this set 2 times) numbers with minumum sum k+1.

eg. k=5 we have set1 = 1,2,3,4,5 and set2= 1,2,3,4,5 so to get the minumum sum we can arrange 1+5, 2+4, 3+3 (=6)

so if x+y is 6 we can have at most 5 players ahead of Nikolay. in general we can have at most x+y-1 players ahead of Nilolay.

The best position is 1 if x+y<=n by the logic mentioned above

else (when x+y>n) we will try to find the number of pairs of a and b such that a+b>x+y

to do this efficiently lets have a target=min(n+n,x+y+1)

to reach the target set a=n so b=target-a

thus b is the best position achievable.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    What's wrong with the following code?

    ll n,x,y; cin >> n >> x >> y;
        ll best,worst;
        if (x+y<=n) cout << 1 << " ";
        else
        {
            best=min(n,1+x+y-n);
            cout << best << " ";
        }
        if (x+y<=2) cout << 1;
        else
        {
            worst=min(n,1+x+y-2);
            cout << worst;
        }
    
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is copied, not linked.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not able to understand why have you written worst = min(n,1+x+y-2);

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It just ended up like that while i was coming up with the idea, it's equivalent to x+y-1 anyway so it doesn't really matter, what does matter is why it's giving WA on test 3.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          You have done the same thing... what I did.

          Don't know why WA on test3.

          Just a matter of some kind of bad luck :(

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for giving it a thought, i'm really puzzled with this :/

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it +2 Vote: I do not like it

              you forgot cout<<endl; lol consider having 5 tests you need to do cout<<endl;

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                Omfg you are right i can't believe this ever happening

»
6 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

Coronavirus wins!!!!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C2 anyone?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    linear dp + non-decreasing stack

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    The final array of the answer can of these 3 forms :

    1). Non-decreasing order
    2). Non-increasing order
    3). Non-decreasing order upto some index i, then non-increasing order from i+1 to n.
    

    Part 1 and 2 is straight forward. For 3rd part we will do some preprocessing. Let's construct two arrays Pre, Post.


    Pre[i] will contain the number of floors we can make if the array is in non-decreasing order starting from 1 to i. Post[i] will contain the number of floors we can make if the array is in non-increasing order starting from i to n.

    let's calculate array Pre.

    Consider 1 based indexing.
    Pre[i] for a particular index will be (i - j) * arr[i] + Pre[j]. Here j is **largest** index of element which is smaller than arr[i] to the left of it. If no such j exists then j = 0. More formally, arr[j] < arr[i] and j < i. Index j can be calculated using stack.
    

    Similarly Post array can be calculated. And the array will be splitted at the point where pre[i] + post[i+1] is maximum. See this for stack method.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      that's what i was going to write, but i was about to use segment tree instead of the idea to move over indexes. thx for the solution

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I too used Sparse table + binary search for such type of problems until i read the editorial of this problem from Codeforces.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank u so much. Nice explanation.

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Will we get to see testcases used?

»
6 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

I couldn't find a O(1) math solution for first integer in B,so i just used binary search to find it :) (nice C btw)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    haha, nice bro <3

    ;-; Sad for me trying all the O(1) formula I can think with no result

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you message your code erkam plz the submission are not available yet.

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Div.2 $$$\times$$$
Div 1.414 $$$\surd$$$
Difficulty:A<C1<B<C2<<D<E

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can you solve B ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well...I found the formula by the samples

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        ... My code can output as the samples but not for my own created tests ;-; Every formula I try is still fail 1 ~ 3 tests ;-;

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          That't too bad...

          My formulas are min(max(0,x+y-n)+1,n) and min(x+y-1,n)

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            How did you arrive at this solution? Can you please provide some mathematical proof

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          i guess you may solve B/C in next round if you stop wasting your time(like what i do right now) and start upsolving(like what i will do) :)

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            why down voting, iam just leading him to a better rate

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one tell the approach of A I just list out cases for it. Any other method?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I used greedy method

        /// Sort a > b > c
        if (a < b) swap(a, b);
        if (a < c) swap(a, c);
        if (b < c) swap(b, c);
     
        int res = 0;
    
        /// Take 1 disk
        if (c) res++, c--;
        if (b) res++, b--;
        if (a) res++, a--;
        /// Take 2 disks
        if (a && b) res++, a--, b--;
        if (a && c) res++, a--, c--;
        if (b && c) res++, b--, c--;
        /// Take 3 disks
        if (a && b && c) res++, a--, b--, c--;
    
        cout << res << endl;
    
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I have also used the same approach.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I even did same ,why you arrange them like? 1 . if (a && b) res++, a--, b--; 2. if (a && c) res++, a--, c--; 3. if (b && c) res++, b--, c--;

      it might be 1. then 2. then 3. or 1. then 3. then 2. or............so on.

      3! arrangements

      and where you see it is greedy?????

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that you should take (a-b) and (a-c) before take (b-c) else you will get WA

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

When will be the rating change?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My code for C1 gave an incorrect answer on the 9th pretest. Any idea what's wrong with it? 71676960

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry but your code cant be read now :v

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    probably you should use long long instead of int

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had incorrect answer on 9th pretest cause int overflow

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, it was int overflow for me too.

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Why fake123_loves_me just disappeared in the standing? He was first, but he disappeared and everyone else's standing get one step upper.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think because he is unofficial participants. You can see him if you tick on the [] show unofficial on the top right.

    Correct me if I am wrong

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Yes, but he did not have star before

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        But I thought that join with >1900 rating will be unofficial participant ? (he is 2044)

»
6 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

B is very hard

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide the solution for C1? Thanks in advance!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    int n;
    cin>>n;
    
    int a[n];
    for(int &i:a)cin>>i;
    
    int ans[n];
    
                int sum3=0;
                int index=0;
    
                for(int ind=0;ind<n;ind++)
                {
                    int tsum=0;
                    int temp[n];
                    tsum+=a[ind];
                    temp[ind]=a[ind];
    
                    for(int i=ind-1;i>=0;i--)
                    {
                        temp[i]=min(temp[i+1],a[i]);
                        tsum+=min(temp[i+1],a[i]);
                    }
                    for(int i=ind+1;i<n;i++)
                    {
                        temp[i]=min(temp[i-1],a[i]);
                        tsum+=min(temp[i-1],a[i]);
                    }
    
                    if(tsum>sum3)
                    {
                        index=ind;
                        sum3=tsum;
                    }
                    //cout<<tsum<<endl;
    
    
                }
              //  cout<<index<<endl;
    
                  ans[index]=a[index];
                    for(int i=index-1;i>=0;i--)
                {
                    ans[i]=min(ans[i+1],a[i]);
    
                }
                for(int i=index+1;i<n;i++)
                {
                    ans[i]=min(ans[i-1],a[i]);
    
                }
                for(int i:ans)cout<<i<<" ";
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sharing code is not appreciated here. Better share links if you really have to; even better share your approach!

»
6 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I think B may change position with C1

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How can you solve B ? That is nice <3

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 3   Vote: I like it +9 Vote: I do not like it

      Suppose in the first round we took x-th place and in the second round — y-th place

      First we consider the max: We can let the person who took (x-1)-th place in the first round took the (y+1)-th place in the second round. Then the total score of this participant is (x+y) which can contribute to the answer .Similarly, with this strategy we can know that the ans is min(n,x-1+y-1+1)

      Then we consider the min: We can let the person who took (x-1)-th place in the first round took the (y+1+1)-th place in the second round. At this moment , the total score of this participant is (x+y+1) which is strictly larger than we. By doing this,now1=max(0,n-(y+1)) of the first (x-1) people's final scores are strictly larger than B.The same is true for the dimension y and the number is now2. So the number of people who may not strictly larger than we is (a-1-now1+b-1-now2+1(myself)), but this is not the optimal answer, We can make pair X and Y smaller than me in pairs and make the ans to {a-1-now1+b-1-now2-min(a-1-now1,b-1-now2)+1}

      My Submission : 71671193

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        {a-1-now1+b-1-now2-min(a-1-now1,b-1-now2)+1}

        what is "a b" means ? please

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      worst pos is min(n, x + y — 1) best pos is (x + y >= n ? min(n, x + y — n + 1) : 1)

      proof is left as an exercise to the reader

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem E be solved using suffix array?

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Without samples, I couldn't solve B

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Typical maths problem XD

    I solve it in 1hr40min QAQ

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Finally Master. Hope I can stay a bit longer.

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

I cant see the code of others (it is almost 2hrs)

»
6 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

I THINK I VE COME UP WITH THE ULTIMATE GENIUS 35182798 IQ THINKING PROCESS FOR SOLVING B.

First you reduce the problem to a matching problem 71692875. I copypasted preflow pushes but it doesnt really matter!!! You could use ford-fulkerson or any other algorithm.

Then you notice a pattern and write this 71692875. Then you submit it and do not lose 5512571829 rating.

I think I am a fucking genius right guys?

Proof by AC is the way to go smart people told me this!!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    actually i wonder how many of those who got an ac actually know why their solution works

    i dont

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You didnt even submit your super solution. In both of ur submission you got AC using the same 1 line of code.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        okay man thanks for telling me something i didn't know

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My code for C2 (here got the wrong answer. But when I changed at line 118 from '<' to "<=", it got accepted. I tried that to handle the case of all zeros (even though it is outside the constraints). Is their test case 20 outside of constraints or am I missing something?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have the similar situation?

The System says I may write a code very similar to other's.

But this is problem A.

I think it's because the code is too simple so that it's easy to be very similar.

What should I do?

My Submission:71656145

What the system has sent to me:

Attention!

Your solution 71656145 for the problem 1313A significantly coincides with solutions Acranker/71656145, hnust_zhouzisheng/71662017. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Why do i keep getting runtime error on test 5 in D? Here's the link to my code

EDIT: Got the mistake

»
6 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

When will the system tests be visible, I want to know why my C2 failed!!!!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    maybe i can help you with the problem, u can pm me if u wish

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

tfw you're purple but can't solve div2 B...

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

When will submission be visible? It's nearly 3hrs instead of so-called "1hr"! And I'm anxious to see why my C2 failed!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When can I watch other's code?