ilyakrasnovv's blog

By ilyakrasnovv, 3 years 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__, daubi, 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

| Write comment?
»
3 years 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!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

scoring distribution when

»
3 years 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.

»
3 years ago, # |
  Vote: I like it +96 Vote: I do not like it
NA meme
  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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

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

      yes. always 22:30 in China.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it +23 Vote: I do not like it

        So this unusual time is really friendly to Chinese participants.

        because it is afternoon <3.

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

          not that friendly. dinner time.

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

          Friendly for Chinese students, not so friendly for us working in companies :P

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

          The problems were not friendly at all.

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

      I think the IST is blessed in this case.

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

    Actually it is 13:00 in Russia

»
3 years 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

  • »
    »
    3 years 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.

»
3 years 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.

»
3 years 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!

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Score distribution?

»
3 years 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,

»
3 years 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

  • »
    »
    3 years 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.

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

    Rating will be added of the problem in some time

»
3 years 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?

  • »
    »
    3 years 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!

  • »
    »
    3 years 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

  • »
    »
    3 years 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. :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck and high rating!

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Delay by 5 minutes

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

note 5 minutes delay

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Delay 5 minutes ...

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

unfamiliar time, familiar delay. :(

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it rated?

m1,m2,m3 do not load.

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

SpeeeeeedForces

»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Me wondering what to do after A,B,C

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

The difficulty gap between c and d was huge

»
3 years 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

»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

»
3 years 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?

  • »
    »
    3 years 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.

»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Specialists and pupils after solving A,B,C fast

»
3 years 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 ...

  • »
    »
    3 years 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.

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

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really unbalanced contest, you have my heartfelt downvote.

»
3 years 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)

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

IMO, D has a very nice solution !

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

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

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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.

      • »
        »
        »
        »
        3 years 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?

    • »
      »
      »
      3 years 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://mirror.codeforces.com/contest/1642/submission/147465343

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

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

    • »
      »
      »
      3 years 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

    • »
      »
      »
      3 years 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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve A?

  • »
    »
    3 years 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.

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

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

      • »
        »
        »
        »
        3 years 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;
        
»
3 years 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

  • »
    »
    3 years 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

»
3 years 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 !

»
3 years 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++.

»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

D was next level adhoc.

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

.

»
3 years 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 :((((

»
3 years 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.

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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?

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

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

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

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

      • »
        »
        »
        »
        3 years 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

        • »
          »
          »
          »
          »
          3 years 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.

»
3 years 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

»
3 years 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 ?

  • »
    »
    3 years 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

  • »
    »
    3 years 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)

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Successful SpeedForces round, nothing else to say

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

too standard round

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

poggers sus amogus tokyo ghoul

»
3 years 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 :(

»
3 years 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?

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can we please have the editorial ilyakrasnovv?

»
3 years 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.

  • »
    »
    3 years 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.

»
3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.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?

»
3 years 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 >_>

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

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

    • »
      »
      »
      3 years 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.

      • »
        »
        »
        »
        3 years 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.

  • »
    »
    3 years 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?

»
3 years 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.

»
3 years 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?

»
3 years 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.

»
3 years 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.

  • »
    »
    3 years 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...

  • »
    »
    3 years 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!

»
3 years 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.

»
3 years 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.

  • »
    »
    2 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Tle on div2 B

»
3 years 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.

  • »
    »
    3 years 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.

»
3 years ago, # |
  Vote: I like it +1089 Vote: I do not like it

.. The pretests ....

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

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

      Idk why I laughed so Hard my brother was sleeping. Damn its too Funny Man

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

    404 — your rating not found

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

    Do you know why did you get TLE for tc 10 on div1 A? I am not able to find what's the problem with your code.

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

      I do the greedy solution from small to big , and create many useless values in the map . It can be $$$O(n\log^2n)$$$ in the worst case.

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

trash pretest QAQ

»
3 years 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 :(.

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
3 years 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://mirror.codeforces.com/problemset/problem/1285/F

  • »
    »
    3 years 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.

»
3 years 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

»
3 years 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.

»
3 years 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 !!

  • »
    »
    3 years 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

»
3 years 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.

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

A GOOD FST ROUND

»
3 years 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.

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Pretty fast systests!

»
3 years ago, # |
  Vote: I like it +84 Vote: I do not like it

Why are submissions still hidden ?

»
3 years 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://mirror.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)
»
3 years 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

»
3 years 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.

  • »
    »
    3 years 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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years 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

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

      NOTHING HERE

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

        But i am initialising a new map for each testcase!

        • »
          »
          »
          »
          »
          3 years 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

          • »
            »
            »
            »
            »
            »
            3 years 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;
            }
            
            • »
              »
              »
              »
              »
              »
              »
              3 years 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

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years 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!

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years 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.

            • »
              »
              »
              »
              »
              »
              »
              3 years 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.

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

                thank you for teaching a lot :-)

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

              Just use a multiset and save yourself some trouble.

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

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

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

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

»
3 years 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.

»
3 years 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!

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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.

    • »
      »
      »
      3 years 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.

»
3 years 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?

  • »
    »
    3 years 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.

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

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

»
3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2D/div1B ?

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

    UPD:

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

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

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

When will the rating of Div.2 be updated?

»
3 years 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how do you miss such an important pretest on C bruh

»
3 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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

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

.

»
3 years 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!

»
3 years 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?

»
3 years 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? :)

»
3 years 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?

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

May I know how to solve Div1C?

  • »
    »
    3 years 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.

    • »
      »
      »
      3 years 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?

      • »
        »
        »
        »
        3 years 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.

  • »
    »
    3 years 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

»
3 years 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());
  • »
    »
    3 years 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.

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

      https://mirror.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?

      • »
        »
        »
        »
        3 years 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.

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

          oww understood thnx. got astoundingly saved today.

        • »
          »
          »
          »
          »
          3 years 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...

        • »
          »
          »
          »
          »
          3 years 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)

        • »
          »
          »
          »
          »
          3 years 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.

          • »
            »
            »
            »
            »
            »
            3 years 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://mirror.codeforces.com/blog/entry/100208?#comment-889480

            • »
              »
              »
              »
              »
              »
              »
              3 years 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://mirror.codeforces.com/blog/entry/57646

    • »
      »
      »
      3 years 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

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve Div1C?

»
3 years ago, # |
Rev. 5   Vote: I like it -155 Vote: I do not like it

[Deleted ...]

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

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

  • »
    »
    3 years 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 ?!

»
3 years 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...

»
3 years 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.

  • »
    »
    3 years 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 ?

    • »
      »
      »
      3 years 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).

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
3 years 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://mirror.codeforces.com/contest/1641/submission/147497119

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

Good contest, finally I became Pupil. Thank you so much people!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was Problem A more difficult than usual problem A of div 2? I was got 1 WA and solved after solving b c.

»
3 years ago, # |
Rev. 4   Vote: I like it +21 Vote: I do not like it

I'm a bit sad for ilyakrasnovv who gets a -94 negative contribution because of this post ....

Upd : Now -70 -> -66 (Upd 1) -> +80 (Upd 2)

Now I'm not sad !

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

    Yeah, I am not really sure why? Doesn't seem to me like there were any issues with this round?

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

      Apparently some complained about the image for problem A(it took a long time to load ); the difficulty gap between C and D, which lead to a fastforces for those who didn't solve D; and finally the order of difficulty of problems (many thought C<B<A)

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -25 Vote: I do not like it

        No mercy for people without #define int long long in their templates. tnowak learn your lesson

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

          I'm pretty new at codeforces, but doesn't long long take memory pretty much ? Correct me if I'm wrong ...

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

            It does. But I much rather fix MLE over WA.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder Why do only few number of programmers gave this contest and why does this post has huge number dislikes ?any specific reason;-;

»
3 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Why don't we have the an editorial yet?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The pretests are awful.It's to easy to FST.

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

    Different verdicts on main tests and pretests do be quite annoying, but you see, passing pretests does not always indicate that your solutions are absolutely correct. One may pay attention to details and boundary conditions and code more precisely, so that your program is strong enough and able to get rid of sticky FSTs.

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

Problem D and E is super great!

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

Even though I still can't get an accepted submission on div2 E/ div1 C, I really enjoyed the problem! Thanks setters!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

147529502 question C , why is it giving TLE?

»
3 years ago, # |
Rev. 2   Vote: I like it -30 Vote: I do not like it

l

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

147428133 This is my submission from yesterday's educational round, here I have used unordered sets and it gave TLE on test case 6 but if I used a set in place of unordered it gets accepted. But since only insertion is executed how can it give TLE as far as I know, unordered sets have O(1) complexity while set uses O(log N) complexity.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

codeforces? speedforces!