ilyakrasnovv's blog

By ilyakrasnovv, 6 months ago, translation, In English

Hello, Codeforces!

We are glad to invite everyone to participate in Codeforces Round #773 (Div. 1) and Codeforces Round #773 (Div. 2), which will be held on Feb/23/2022 13:10 (Moscow time). Notice the unusual time! The round will be rated for both divisions. Each division will have 6 problems, and you will have 2 hours to solve them. We recommend you read all the problems!

Tasks are based on RocketOlymp, and were written and prepared by __silaedr__, Allvik06, alegsandyr, ilyakrasnovv, and isaf27.

We are very thankful to

Olympiad's participants cannot participate in codeforces rounds simultaneously.

Good luck and have fun!

UPD — Scoring distribution:

div2: $$$500 - 750 - 1250 - 2000 - 2000 - 2500$$$

div1: $$$500 - 1250 - 1250 - 1750 - 2250 - 3000$$$

UPDEditorial

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

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

Notice the unusual time (returns back)

All the best everyone, may the force of positive delta be with you!

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

scoring distribution when

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

The unusual time strikes back. For once, I can skip my classes with an actually good reason for it.

»
6 months ago, # |
  Vote: I like it +96 Vote: I do not like it
NA meme
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    In many countries, people usually participate in codeforces round late at night or early in the morning.

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

      Usually I get to participate in 11:35PM (UTC+9)

      The good thing is that one participation can count as two days of streak, if I solve at least 1 problem both before and after midnight

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

      yes. always 22:30 in China.

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

      I think the IST is blessed in this case.

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

    Actually it is 13:00 in Russia

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

As someone in the PST timezone, I cannot wait for this new experience of writing a contest at 2AM in the morning :D

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

    Update:

    Using a sample size of the last two contests, I conclude that I perform better at 2-4AM compared to 6:30-8:30AM.

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

today's codechef round is at the normal time of cf, so we have two rounds today.

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

By the way, this round is amazingly friendly for Japanese. Not only the round starts at 19:05 for Japanese but also Feb.23 is one of our national holiday! Thanks!

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

Score distribution?

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

Yay, waking up at 2 am on the West Coast will be so fun,

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

    I think everyone except school kids have this habit of remaining awake till 2 AM in every part of the world ,there might be some exceptions but very little.

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

unsual time with unsual rating change

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

Can anyone tell me the what would be the rating of Yesterday's Edu C contest — Inc. Subarray sum ?? I want to practice such type of prblms

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

    I don't have much idea about the rating of that problem but I suppose you may get better results if you ask on the respective contest's announcement/editorial blog.

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

    Rating will be added of the problem in some time

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

After the last round, I think I have a chance to get into Div. 1. But since the ratings haven't been updated yet, I can't register for Div. 1. Only an hour and a half left, do I just sit tight and wait? What happens if I register for Div. 2 now and then get promoted right before the contest starts?

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

    If you register for Div. 2 and get promoted to Div. 1, your registration will be transferred to Div. 1 automatically. Best of luck for today's contest!

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

    I have the same problem but the reverse of it XD.

    I am going to return expert but since the ratings haven't been updated, I am forced to register for Div.1 it's not a bad idea for me but I don't know what will happen if the rating get changed later

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

    Yay, I got my rating change and the passage to Div. 1! Thank you to the Codeforces team! The color didn't get updated though, so I guess I'm gonna be a blue spy in Div. 1. :D

    Edit: it got updated while I was writing. :)

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

Good luck and high rating!

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

Delay by 5 minutes

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

note 5 minutes delay

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

delayed by 5 minutes

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

okeeeey lets go +5 min

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

Delay 5 minutes ...

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
authors İlluminati confirmed (visible in dark mode)
»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

unfamiliar time, familiar delay. :(

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

Is it rated?

m1,m2,m3 do not load.

»
6 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Shitty speedforces

»
6 months ago, # |
Rev. 2   Vote: I like it -44 Vote: I do not like it

SpeeeeeedForces

»
6 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Me wondering what to do after A,B,C

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

I would gladly give starters.

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

The difficulty gap between c and d was huge

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

Speedforces for sure

The gap between C and D is tremendous

»
6 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Borforces.(Boring contest)

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

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

Is it just me or some of the statements were kind of difficult to interpret?

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

    We could guess how much thousend of partitipants left because of bad statement in A.

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

    No its not only you. Cont me too in your team

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

      the A's statement was so terrible that I had to guess the solution......

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

why C<B<A<<<D ??

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

Specialists and pupils after solving A,B,C fast

»
6 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Me after solving A-B-C in the first 20 minutes and not knowing what to do for the rest of the round ...

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

    That's unfortunate, anyways for future rounds keep in mind that after solving A, B, C you should try problem D.

»
6 months ago, # |
  Vote: I like it -11 Vote: I do not like it

This contest ruined my day

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

Figures in A are very huge , hope to be moderate next rounds

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

Really unbalanced contest, you have my heartfelt downvote.

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

E should be "cost" more. Its much harded than D (according to standings)

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

IMO, D has a very nice solution !

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

    Indeed. Just one observation and it's a nice constructive problem.

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

    I wasn't able to solve D, But I think the solution is like in this direction. 1) If any elements occur odd times then the answer is simply -1. 2) We will choose the first segment where ar[end]=ar[start], initially start=0, We can this make segment good(or whatever they say) by doing at most segmentLength-2 operation. these operations may add extra segmentLength-2 elements, but we can handle these elements in the next segment. I think we need to repeat this step till we have no remaining elements.

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

      Correct. The most important realization is that the extra added elements will ALWAYS be possible to pair them in later iterations.

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

        I think it's easy to prove that the extra elements+ rest of the array will not contain any odd element and hence we can make the remaining segment good also.

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

        Wow! I was thinking in the wrong direction probably: I thought of making array such that a2i-1 = a2i, for this we can swap elements until it matches with the same number.
        Swapping can be done as follows:
        Let's say we have to swap x and y in the sequence, then [x,y] -> [x,y,x,x] -> [x,y,x,y,y,x]. If you observe carefully first 4 numbers sequence is good (tandem repeat), and we are left with [y,x].
        Maybe some more thinking/observations need to be done in this method. Has anyone solved D using the same/similar idea?

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

      I did, but the program made an error in the second test https://codeforces.com/contest/1642/submission/147465343

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

      I got this observation but could not handle the implementation part.

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

      You can also "reverse" a segment. For example going from abcd -> abcdabcddcba. The junk part added is a valid subsegment. So just sort the array using this

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

      I passed the problem. The previous error is because I didn't increase the offset under special circumstances. I just added one line to the code in the contest. :-(

      Wrong answer Accepted

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

how to solve A?

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

    The answer would always be 0 if no side is parallel to the x axis. If a side is parallel to x axis , and the third point of the triangle that doesn't lie on that side is BELOW the parallel side , the answer would be the length of that side parallel to x axis.

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

      I did the same. Could you pls share your solution?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        pair<int, int> p[3];
        	for (int i = 0; i < 3; i++) {
        		cin >> p[i].first >> p[i].second;
        	}
        	if (p[0].second == p[1].second && p[0].second != 0 && p[2].second < p[0].second) {
        		cout << abs(p[1].first - p[0].first);
        	}
        	else if (p[1].second == p[2].second && p[1].second != 0 && p[0].second < p[1].second) {
        		cout << abs(p[1].first - p[2].first);
        	}
        	else if (p[0].second == p[2].second && p[0].second != 0 && p[1].second < p[0].second) {
        		cout << abs(p[0].first - p[2].first);
        	}
        	else {
        		cout << 0;
        	}
        	cout << line;
        
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Here's mine
      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Basic Idea for A :

        1. Line [between P1 & P2] Parallel to X-Axis
        2. Third Point Should be Lower than Current Line. [P3 Point's Y Co-ordinate should be Less than Line's Y Co-ordinate].
        Code [C++] [Div 2 A]
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Damn only able to solve Problem B...this contest is really unbalanced btw does anyone feels like problem A > problem B

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

    No. For me it was just a basic geo problem . But this time A has less solve idk why

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

Took me two minutes and a half to see the image of problem A !

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

Man the questions were very confusing at first. Nevertheless another fun round!!

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

Time limits in B and C. It was the last contest for me on Python. I'll go to learn c++.

»
6 months ago, # |
  Vote: I like it -14 Vote: I do not like it

D was next level adhoc.

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

.

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

What is the intended complexity of Div1D? I did N2^Mlog(2e9) and its TLEing :((((

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

    $$$O(n 2^m \log n)$$$ passed in 2950 ms :)

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

I turned on the setting "show only trusted participants by default" in this round. It seems that for div2 this setting really removes a lot of suspicious participations.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it -25 Vote: I do not like it

    rating update should be with accordance of number of registration and rank. Not in accordance of number of submission and ranks.

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

      exactly

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

      If a user registers and doesn't participate then his rating is not affected at all then why should his registration affect the ratings of other people?

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

        If what OP suggests is implemented, then the rating of the users who register and do not participate would also be affected, like it's done on atcoder.

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

      yeah.

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

    thanks a lot! i hope you do this every round.

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

    Can someone please explain who fall in to this "trusted participants" category?

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

      This happens in div3 rounds, check This post for example.

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

        But I still didn't understand what's the point of removing them from the official standings if their rating is anyway going to change

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

          In order to stop them from affecting your rating, so if hundreds of new un-trusted accounts made by div1 users took part in the contest and solved more problems than you, they won't affect your rating.. they will get rating changes but they won't be part of rating changes calculation for the rest of the participants. (you will get better rating)

          that's what i understood. If someone thinks that I'm wrong, correct me please.

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

I though that Div1 doesn't have cheaters, but it does: sol1 sol2

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

in DIV2C ,is there any need to sort the array or check whether a[I]%x==0 or not before finding a[I]*x in our map ?

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

    You do need to sort it or use something like a set. But why would you check a[I]%x==0

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

    i got WA for not sorting, because you can get arrays like 4 1, when (1, 4) should pass but without sorting it mistook with this result (4, 16) (1, 4)

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

    i solved using map

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

    I didn't sort the array, just stored it in a map. And removed y*x for each y in the map.

    Unfortunately my code TLED, just because I used mp[y*x]=0 instead of just removing y*x from the map(mp.erase(y*x)).

    Tled code

    Accepted code

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

Successful SpeedForces round, nothing else to say

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

too standard round

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

poggers sus amogus tokyo ghoul

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

Why is time limit for D1D so tight? My solution is $$$O(n2^m)$$$ but it runs for 1500ms even after optimizations, but some people's $$$O(n^2/w)$$$ solution runs under 500ms.


Another fun fact: I gave a problem using exactly the same idea as E in a Chinese OJ contest in Feburary 18th. However I lacked time so I didn't pass E :(

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

I wonder why someone would put 3 pictures with a total of 1.45M in Div2 A?

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

Can we please have the editorial ilyakrasnovv?

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

why many programmer pullout of contest without submitting any solution if first and second questions are tough or not easy to understand.

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

    I think for many programmers and for me also 1st questions is a special problem it should be kept easy. Not to complicate its statement like this

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

    It is not about tough, it is about high probability of getting the problem statement wrong.

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

A and B weren't too interesting. I don't think A should be in div1 contest, B was not bad though.

C was similar to APIO 2012 Guard but not too much, I liked it. I wasted lots of time trying to find the similar problem tho :(.

D reminds me of USACO 2018 Cowpatibility, but I haven't thought much about it yet, solution is definitely very different.

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

https://codeforces.com/contest/1641/submission/147415490 Can someone explain why this solution for Div2C/Div1A got a TLE? Is there some quirk with unordered_map I don't know of?

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

Why are the TLs so tight? I wrote a $$$\mathcal{O}(n \log^2 n)$$$ parallel binary search solution to problem C, and it TLE'd. Had to use Van Embe Boas tree instead (147441626) to pass >_>

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

    i think because solution is O(n log n).

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

      Yes. And the only thing you should use is Segment Tree with $$$O(log{n})$$$ descent instead of binary search.

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

        I used nothing but std::set. Definitely not tight TL for such sol.

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

    Can you explain what is Van Embe Boas Tree? Or some material to learn it?

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

I know how to solve problem D,but it's not easy to finish the code.

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

In problem B, at first I use vector to insert two integers, then I got TLE on 4. After I replaced vector by an array, I passed. Why can't you just enlarge the Time Limit so that those who use vector instead of array could pass?

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

The huge pictures in 2A slow down the loading of the page. The coordinates and sizes of the example triangles are not that large and there are extra space that could have been cropped out.

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

I'm almost certain this is unintended but I have a $$$O(\frac{N^2}{64}+N\sqrt{N})$$$ solution to d1D that passes pretests in under 500ms.

We just sort the arrays by $$$w$$$ then for each element, we just store a bitset of which arrays are incompatible with it.

Of course, storing $$$nm$$$ bitsets is too much memory, so let's only store it for elements which occur more than $$$\sqrt{N}$$$ times. So we need to add another $$$N\sqrt{N}$$$ to complexity to handle elements that occur small number of times, but it's fast.

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

    Meanwhile, my $$$N 2^M \log N$$$ solution required extensive constant optimization in order to pass...

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

    Thanks for your great solution! I learn a lot from it. It is a wonderful idea!

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

I think Div.1 B shouldn't put at this place. It should be dressed with more confusing skins, added more strange limits, made impossible to code, and placed at Div.1 F. It is a great idea of mass destruction, Div.1 B is a waste of such a great idea.

»
6 months ago, # |
  Vote: I like it -44 Vote: I do not like it

Maybe this question is very strange. Why $$$n \leq 3 \times 10^5$$$ in question B but $$$n \leq 2 \times 10^5$$$ in question C? Different upper limits make me RE.

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

    How it could be!You just copy the limit before.It's ugly.Reflect your behaviour before blaming the problems.

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

Why Tle on div2 B

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

Maybe there is a too big gap between problem div1.B and div1.C. But I think it's very good to make some challenges.

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

    Oh, I made a mistake. I mean that the gap is between div1.A and div1.B.

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

.. The pretests ....

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

trash pretest QAQ

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

I got TLE on both B and C for using unordered map while it got accepted when I replaced it with map :(.

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

Wow , You have strong pretest in Div2 C / Div1 A

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

I think the main idea of div1-D is similar to this problem(except parallel binary search): https://codeforces.com/problemset/problem/1285/F

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

    I applied the exact same idea and passed, I don't think parallel binary search is needed.

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

DIdn't solve D cause of one line of code. I want to kill myself lol

»
6 months ago, # |
Rev. 8   Vote: I like it +33 Vote: I do not like it

This round is typically speedforces with weak pretests. (Div 2A is confusing and makes a lot of people quit, that's why so few contestants in div2)

When the difficulty gap between two problems are very large (like C and D in div2), then the ranking of contestant will depend on the speed that solve these easy problems. If you get stuck on one "easy" problem for a long time or make wrong submission, or failed the system test (the pretest of problem div2C is so weak), and you cannot solve hard problem, you will be finished.

Personally I don't like this kind of contest.

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

Hello guys ! Can someone explain to me why is that a normal set is faster than an unordered_set , the only operation i used on them is inserting elements and getting the size !!

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

    due to hash collisions, the time complexity of unordered_set per operations can be up to O(n), you can read about it here

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

I request all contest writers here that guys please make some strong pretests.You will get nothing by trolling participants.

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

ou yeah, another trash round, bad pretests C + no balance

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

A GOOD FST ROUND

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

Can someone suggest any test case where this gives WA (pretest aren't visible). Logic: For k = 1, answer is number of distinct power ups. The if minimum frequency element currently is 1 then it answer is same as for k-1.

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

    Test:
    1
    4
    1 1 2 2
    Right answer:
    2 2 3 4
    Your answer:
    2 3 3 4

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

      Thanks, got it. Giving all unique to one doesn't works. Can you share how you approach this kind of questions basically GREEDY?

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

Pretty fast systests!

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

Why are submissions still hidden ?

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

Good contest guys but I think you had weak tests for C. My submission https://codeforces.com/contest/1642/submission/147435078 is AC. I used a multiset with count. And I found out that count is actually really slow in multisets. So it shouldn't AC for the following example input. It should TLE.

1
200000
1 (100000 times) 2 (100000 times)
»
6 months ago, # |
Rev. 3   Vote: I like it +69 Vote: I do not like it

I solve Div1D with such a randomize:

for every element x we determine f(x) as a random number in 0...19

then for every i=1...n we will compute mask of the f of elements in the a_i

mask[i]=or(1<<f(x),x in a[i])

then we solve problem (find two non-intersected masks with minimal sum of weights) with subset DP

we repeat it 35 times,and take minimal of the answers

link:

https://pastebin.com/z03e8wU1

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

Has the system testing system changed?

It looked like it was rejudged several times even when it got TLE.

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

    I watched 300iq and found his div1D rejudged several times even during the system test

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

https://codeforces.com/contest/1642/submission/147449848 Can someone please explain why my submission exceeded the memory limit on test 10 for div2C/div1A ?

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

    do not clear the map during each testcase, and set up a new map

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it -14 Vote: I do not like it

      NOTHING HERE

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

        But i am initialising a new map for each testcase!

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

          So could you plz paste your code here? I can't view your code now

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it
            void solve(){
                ll n,x;
                cin>>n>>x;
                vl a(n);
                take(a);
                sort(all(a));
                map<ll,ll> mp;
                fr(i,n){
                    mp[a[i]]++;
                }
                ll ans=0;
                for(auto it : mp){
                    ll val = it.ff*x;
                    if(mp[val]){
                        ll mn = min(mp[val],it.ss);
                        mp[val]-=mn;
                        ll num = val/x;
                        mp[num]-=mn;
                    }
                }
                trav(e,mp){
                    ans+=e.ss;
                }
                cout<<ans;
            }
            
            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              uh

              when you process mp[val]-=mn; when val=it.ff*x, it will change the elements in mp, which hasn't been traverse currently

              and this may cause the order of the map changed(you know, the elements in the map are sorted from small to big), and that will cause something wrong?

              Just my guess, I am not sure

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

                Guess i got it. Should'nt have traversed in the map lol. Thanks for helping out!

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

                Modifying values in a map while iterating over it is ok. Even inserting new keys is ok, insertion doesn't invalidate any iterators.

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

              If val is not in mp, if (mp[val]) will add it to the map with value 0. So if ll could store huge values, the loop would never terminate, and in practice it can take a very long time.

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

                thank you for teaching a lot :-)

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

                that's why i got tle in my code......hope i knew that earlier :-<...thanks for explaining....i think map.find() will give the correct answer

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

              Just use a multiset and save yourself some trouble.

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

        mp.size() gives 0 after mp.clear(). so what about that?

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

        This is false, clear erases the nodes and deallocates used memory.

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

 Did anyone faced this problem too?The image was cropped for 8-10 mins in chrome.I changed to brave it was fine there.

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

147472401 why I got tle on B using unordered_map? please explain anyone

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

Hi there. I don't know where to ask general questions about solutions so I post them here. Pls tell me if it's a wrong place.

For both B & C I passed all the pretest cases, and failed with TLEs in the system tests. The original compiler I was using in the competition was C++17. After the competition I submitted the exactly same solutions with another compiler (C++14) and both of them passed all the tests.

Spoiler

It's my first time to encounter such a situation. It'd be very helpful if someone could tell me some general ideas to cope with this, like which compiler I shall choose by default during the contest. Since the pretests are all passed, it seemed impossible to see the difference during the contest.

Thanks in advance!

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

    If an unordered_map fails with TLE it is most likely that there is some test with special numbers, so that the unordered_map degenerated to O(n) instead of O(logn) behaviour.

    This is well known, and the short solution is to just not use unordered_map, else use your own hashing functions.

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

      unordered_map degenerates straight to O(N) per query. I also should say, that tests are incredibly weak. For C, there was no simple 200000 2 all 1s test, and everyone, who used multiset::count, passed on systests(!!), when they shouldn't have.

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

      Thanks! Costed me both B and C today! Will keep in mind for the later contests.

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

      Thanks for the answer! Will never do this for a second time haha.

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

why did my submission of div2/c 147429231 got TLEd? It's overall complexity is O(nlogn).

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

A slight modification for problem div2C/div1A —

If x is not known and we need to print both optimal x and minimum no of elements to add in array ,

What will be the best approach for this, ie with minimum time complexity?

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

    I wasted a whole lot of my time thinking about this problem because I did not notice that x is given :( What a pity for me.

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

bro wai C no have a[i]*x limit pretest

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it
Wrong Code for B

Can Anyone tell if my logic for Div2 B is correct or not .. Editorial and other solutions are not visible yet. Sorry for inconvenience.

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

How to solve div2D/div1B ?

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

    UPD:

    Implementation with comments
»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

problems rating be like(1000 , 900 , 800 , 2200)

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

When will the rating of Div.2 be updated?

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

I would suggest organizers use compressed images for problem statements. Heavy images increase problem statement download latency.

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

i just start codeforces not long time, and i think problems are hard for me :(

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

how do you miss such an important pretest on C bruh

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

tourist is one contest away to 4000 for the second time.

»
6 months ago, # |
Rev. 5   Vote: I like it -38 Vote: I do not like it

.

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

my solution give tle when i submitted it c++17 but when i submit the same code in c++14 it got accepted

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

Problem C: Can any one please give me a testcase where not sorting the array gives wrong ans!

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

    1 10 3 15 15 15 45 45 5 5 5 135 135 Try this

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

    Try this n= 4 and k=2, and ar=[8,16,4,32]. Ans should be 0.

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

    It's easy to prove why sorting is needed.

    Let's say you have an array [x, x2, x3, x4]. Optimally it's easy to see that all pairs will be used but let's say you decided to pair x2 and x3 together. Now x and x4 can't be paired together so you lost one pair.

    You can create such test cases easily. One such example is [4, 2, 1, 8, 2, 16]

»
6 months ago, # |
Rev. 2   Vote: I like it -39 Vote: I do not like it

I think there is something wrong about rating in this contest, or because of the number of participants?

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

No editorial yet and submissions not yet public, are we preparing to repeat the contest? :)

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

plz open the solution seeing mode of other

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

During contest when I made submission for problem A, I got wrong answer. But when I submitted the same code after contest (link) with fixed and setprecision(12) before printing double I got it accepted. For the problem A, the answer would always be an integer. So why would it be incorrect when not using precision and fixed?

»
6 months ago, # |
  Vote: I like it -68 Vote: I do not like it

include <bits/stdc++.h>

using namespace std;

define ll long long

define ld long double

const ll MOD = 1e9 + 7; const ll INF = 1e9; const ld EPS = 1e-9;

void solve() { int n; cin >> n; int x; unordered_set mp; for (int i = 0; i < n; i++) { cin >> x; mp.insert(x); } int sz = mp.size(); for (int k = 1; k < sz; k++) cout << sz << " "; for (int k = sz; k <= n; k++) cout << k << " "; cout << "\n"; }

int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; cin >> tc; for (int t = 1; t <= tc; t++) { // cout << "Case #" << t << ": "; solve(); } }

Can someone tell why this is giving TLE for problem B ?

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

May I know how to solve Div1C?

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

    q * log(n)^2 solution:
    Maintain set of positions P that can be ill. For x = 0 queries you need to erase positions from P from l to r. If pos is not in set P answer is NO, otherwise answer is YES if there is some segment [l, r] with x = 1 with L < l <= pos <= r < R (L is maximal position < pos in P, R is minimal position > pos in P). You can solve this with maintaining set in segment tree vertices.

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

      You can solve this with maintaining set in segment tree vertices.
      Can you elaborate more?

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

        For segments with $$$x=1$$$ insert $$$r_i$$$ into position $$$l_i$$$ in segment tree path to leaf, when checking query $$$[L + 1, pos]$$$ if there exists segment with $$$pos \leq r_i \leq R - 1$$$. Because set is sorted you can binary search to check it.

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

    You can just maintain a set of non intersecting segment of guaranteed 0, and set of segments with value 1 but without one segment entirly containing anouther, then to check if there is 1 in given position we can check if ther is a segement containing 1 and this point is the only non-zero one

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

Why solution of problem E is giving wrong answer on TC 3

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

I thought my code can pass problem C with time complexity O(nlogn), however, it exceeds time limits just at test3. Is there anyone who can help check my program? Thanks a lot.

multiset<long long> seq, del;
seq.clear(), del.clear();
for (int i = 0; i < n; i++) {
	long long a;
	scanf("%lld", &a);
	seq.insert(a);
}

for (multiset<long long>::iterator i = seq.begin(); i != seq.end(); i++) if (vis(*i)) {
	if (vis(*i * x)) {
		del.insert(*i);
		del.insert(*i * x);
	}
}
printf("%d\n", seq.size() - del.size());
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    multiset::count(x) works in $$$O(log(n) + cnt(x))$$$, where $$$n$$$ is the multiset size and $$$cnt(x)$$$ is total number of occurrences of x in the multiset. Therefore, it could be very slow (if there are multiple occurrences of x and you search it many times). You should use map<value, count> or something else to pass.

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

      I see. Thanks a lot!

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

      https://codeforces.com/contest/1642/submission/147442302

      Sorry to ask. But can u tell why my code passes with multiset count. Or are the tests just weak?

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

        It seems astounding. Looks like the compiler optimizes if (multiset.count(x) to if (multiset.find(x) != multiset.end()).

        I resubmitted your code with slight changes (if (s.count(d*x)) -> int count = s.count(d*x); if (count > 0)) and TLEd.

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

          oww understood thnx. got astoundingly saved today.

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

          Honestly, I had no idea this is a thing in even as low as C++14 on cf. Spent so many points this round resubmitting my code and trying to hack...

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

          Any guesses on why the compiler optimises in this case? In a previous contests I have a submission that TLEs with multiset.count but gets AC with multiset.find() (I think there are many more examples though)

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

          We did a bit more digging into this. if(std::distance(s.lower_bound(d*x), s.upper_bound(d*x))) is the underlying operation that is magically optimized 147514900. It seems like it is optimized to if(s.lower_bound(d*x) != s.upper_bound(d*x))

          I resubmitted your code with slight changes (if (s.count(d*x)) -> int count = s.count(d*x); if (count > 0)) and TLEd.

          Casting to int makes it TLE 147515554, but casting to long long makes it AC 147515787. So that TLE happens just because casting 64 bit unsigned to 32 bit signed messes with the boolean optimization.

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

            How do you control those optimisations? I have tried with multisets and counts locally with custom data and didn't get any optimisation. My code (with multiset count) took a long time. Way longer than the one with just find. See https://codeforces.com/blog/entry/100208?#comment-889480

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

              Dug a bit more it seems like the part which turns off compiler optimisations is -fsanitize=address. This is my full build command that was getting executed g++ --std=c++17 -Wall -fstack-protector-all -fsanitize=address -fno-omit-frame-pointer -O2 great_sequence2.cpp -o C2

              Though it seems a bit dangerous to use count with multiset. I am certainly never using it again for finding values.

              See https://codeforces.com/blog/entry/57646

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

      You also can solve problem C with multiset: 147440170

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

      multiset::count(x) works in $$$O(log(n)+cnt(x))$$$??? Wtf??? I also got miraculously saved by compiler optimization, would never expect such counterintuitive inefficiency

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

How to solve Div1C?

»
6 months ago, # |
Rev. 4   Vote: I like it -155 Vote: I do not like it

I think it will be the worst contest this year.

The statement is not clear and difficult to understand.

This is just a simple example of bad review !

minimise !?
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    If I'm not wrong minimise is correct in British English

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

    Im sorry but what...? Even if minimise is wrong, did it really affect your understanding of the problem that much ?!

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

I'll admit it's quite careless of me not to realize C could overflow but one still would expect the pretests to have a case for that...

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

It's interesting for me to read that many people solved Div1D in $$$O(n 2^m \log)$$$ as both me and my friends found a solution with seemingly different complexities.

I choose a number $$$C$$$ (probably sth between 10 and 20 depending on the implementation) and randomly map each number to sth from the interval [0, C). If two sets of size m are disjoint then there is a positive probability that they will be mapped to disjoint sets as well (and if they are not disjoint, then they will be mapped to non-disjoint sets too). That prob is sth like $$$ \ge (\frac{C-m}{C})^m$$$, so if we repeat that, say, $$$8(\frac{C}{C-m})^m$$$ times then we have a good success probability. If all our numbers are from interval [0, C) then we can easily solve our problem in either $$$O(4^C)$$$ or $$$O(3^C)$$$ or $$$O(2^C \cdot C)$$$ time, what gives $$$O(8(\frac{C}{C-m})^m (n + 2^C \cdot C))$$$ solution. $$$C=2m$$$ kinda gives quite similar complexity, but setting C to 20 instead of 10 gives rather a better one.

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

    If all our numbers are from interval [0, C) then we can easily solve our problem in either O(4^C) or O(3^C) or O(2^C⋅C) time Can you please detail a bit about this ?

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

      You think of each set as a bitmask, there are only $$$2^C$$$ of them. For each mask you store the cheapest row that corresponded to it. By bruteforcing all pairs you get $$$O(4^C)$$$. However there are only $$$3^C$$$ pairs of masks that are disjoint and you are only interested in these and you can get such complexity by cleverly iterating through them. For $$$2^C \cdot C$$$ you compute a simple dp of form dp[x] = cheapest mask that is a submask of x in $$$2^C \cdot C$$$ and then if you have a mask $$$x$$$ you check it with $$$dp[(1 < < C)-1-x]$$$ (i.e. cheapest mask that is a submask of the complement of x).

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

In Codeforces Round #773 (Div. 2), problem 'B. Power Walking', my submission got TLE while submitting in G++17. But it got accepted in G++14. Why?

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

Đề như đb <3(trans: nice problem pro, keep it up <3)

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

My solution for prob A passes 136 test cases on Test 2 and fails the 137th. But I really have no idea why!

https://codeforces.com/contest/1641/submission/147497119