Educational Codeforces Round 146 [Rated for Div. 2]
By awoo, history, 13 months ago, translation, In English

Hello Codeforces!

On Apr/06/2023 17:35 (Moscow time) Educational Codeforces Round 146 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space

Hey, Codeforces!

Once again, it is time for another exciting scholarship opportunity from Harbour.Space!

We are looking for talented individuals who want to launch their careers in Cyber Security with a 50% scholarship to study in Barcelona.

If you love technology and looking for an exciting career, then Cyber Security might be for you!

But don't just take our word for it — as a member of the Codeforces community, you know the value of continuous learning and growth. The Cyber Security master’s programme at Harbour.Space responds to a growing market need, driven by increasing threats of global cyberwarfare, for cyber professionals with advanced training in both defensive cybersecurity and offensive cyber actions. The programme is designed to provide the knowledge, skills, and abilities required to perform critical cybersecurity tasks successfully.

Requirements:

  • Bachelor’s Degree
  • Professional fluency in English
  • Your CV in English

What you will learn:

  • Applied Threat Intelligence
  • Threat Hunting
  • Reverse Engineering and Malware Analysis
  • Digital Forensics and Incident Response
  • Pentesting and Ethical Hacking
  • Hardware Conception of Processing Modules for the IoT
  • Networks and Protocols
  • Crisis Management and Communications
  • BlockChain and IAM
  • Soft Skills: Team Building, Presentation Skills and Meeting Facilitation
  • And more

Make sure to apply before April 30th, 2023, to be eligible for the scholarship and reduced application fee.

APPLY NOW →

Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to evidence student life, events, and success stories from students.

We are always happy to see Codeforces members join the Harbour.Space family.

Apply now to learn from the best in the field and take your career to the next level!

Good luck on your round, and see you next time!

Harbour.Space University

UPD: The contest is unrated. We apologize for the inconvenience.

UPD: Editorial is out

  • Vote: I like it
  • -247
  • Vote: I do not like it

Comments Comments (226)
| Write comment?
»
13 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Good luck to all! Happy decisions! Hope everyone enjoys this round! Thanks: adedalic, BledDest, Neon for the assignments and MikeMirzayanov for system Codeforces!

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

    Worst round testing I have ever seen!..

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

    The second worst contest of the year. The first was still the one in which the problem setter used an older cf problem still, It was rated.

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

awoo ORZ!

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

Good luck everyone!

→ Reply
»
13 months ago, # |
  Vote: I like it -24 Vote: I do not like it

This is where I first became interested in hacking a solution. And why do we need such hacks? Won't this spoil the evening for someone whose solution was hacked?

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

    Ratings indeed matter. But improvements matter more.

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

      Hi Nathan my friend haha

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

      how can rating drop when you are levelling up?

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

        He's talking about hacking, which means that ur original correct submission becomes WA.

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

hope to be specialist again.

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

Hope to get a positive delta

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

Hoping for the round to go well

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

Can I have more points if I hacked other people's solutions?

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

Spartans!!! it's time to conquer CYAN.

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

How did people see their expected delta changes? I can only see the status of the problems in the standings.

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

    Most people downloaded a Chrome extension called "Carrot", which shows you the expected delta changes.

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

I seem to getting logged out and am getting timed out errors while trying to access codeforces , is it just me?

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

I smell unrated round.

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

Site is not working properly please look into the matter.

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

Slowforces

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

Thanks for making the contest unrated

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

site couldn't be reached for around 15minutes :')

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

The contests have been crashing for several rounds. please fix this and make last contest unrated.

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

Having crashed for 30 minutes, it should be unrated!

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

Extension? This has to be unrated right.

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

nice joke

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

"Problem D is under investigation." What's that mean?

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

why these days the rounds are too much unbalanced? MikeMirzayanov

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

Bro just dropped worst contest in CF history and thought we wouldn't notice :skull:

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

Server problem and investigation? Should be unrated.

→ Reply
»
13 months ago, # |
  Vote: I like it -16 Vote: I do not like it

unratedforces :(

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

Question B was a joke for some and some were joke for question b

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

Educational round should be tested!!!!!!!!!

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

Ladies and gentleman, I present to you, the REAL april fools contest :D

→ Reply
»
13 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Very poor unexpected!!!!

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

First time I cannot solve problem B in an Educational Codeforces round. Too hard!

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

Me having a good contest :)

CF- Let's make it unrated

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

    Me having my worst contest :(

    CF — Let's make him happy :)

    → Reply
»
13 months ago, # |
  Vote: I like it -33 Vote: I do not like it

Bruh, new contests are in the review queue for around 5-6 months, and yet you fail to find if there's an error in a question. I can't comprehend how bad the "testing" process must be!

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

    Because there is no such process as "testing". Authors are Too cool, why would they even need to test it ?

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

What is happening!!!

I was going to be specialist today...

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

I hate robots.

→ Reply
»
13 months ago, # |
  Vote: I like it +6 Vote: I do not like it
Almost every time:
→ Reply
»
13 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Never been so sad to know the round is unrated when I solve A, B and C in just 30 minutes

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

I'm sure that I'll see blue after this contest and it just...

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

Look at the fact that only 1.6k Accepted solutions of problem B. I have never seen this in an Educational round

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

I thought I could get to Expert but this one is NON-rated now.

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

Those of you downvoting announcement/making snarky remarks in the comments, please stop. I can't believe I have to say this, but don't you think the authors already feel bad enough about the mistake? It's not like issues with the round (besides technical issues) happen often.

Just because you have a right to complain doesn't mean you should.

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

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

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

Looks like its a even odd pattern going on solve counts.

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

Untested EduForces!!

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is the first time I haven't worked out question B(For 2023).

I'm a little nervous.

But I like this feeling!

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

Bon Appetit 2.0

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

This competition had one official technical issue and one technical issue from the organizer... It ruined the first three very interesting questions. I feel very angry.

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it
After 2 rounds I thought I was finally about to get some positive delta. But the round became unrated :[
→ Reply
»
13 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I think MikeMirzayanov should make some Duckworth–Lewis–Stern method on codeforces for such round.

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

Imagine getting DDOS attack but making round unrated for investigation of a problem.

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

have you ever tested this round...?

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

I thought I could become an Expert until I found that this round will be unrated

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

I hate B -_-

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

    I hate unrating-_-

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

    Problems like B make me wonder how I spent 12 years studying algebra in school and still can't do basic math -_-

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

it is a really bad experience.the difficulty order of the questions is unreasonable, Bad server ,and unrated.

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

Unrated because of issues that affected less than 200 people?

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

Are you joking? It's not my mistake!Why should I suffer the consequences? `

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

Now that it is unrated, would you please post the editorial ASAP?

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

No comment starting with as a tester..., maybe this round has no tester?

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

good contest and problems, love from codeforces

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

Any idea on how to solve F?

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

Very nice problem E, satisfying to solve. Such a pity that round got unrated.

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

How to solve $$$D$$$, and what happened with it?

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

[deleted]

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

How to do B? God I've never been stuck at B like this before.

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Suppose you increase your leg to M. It will take ceil(a/M) + ceil(b/M) to get to the point. Why ceil? Well, if a is multiple of M, just move (a/M). If it is not, then there is a remainder (a%M) < M. During the increase process you will surely get at this remainder at one point (because it is less than M and you increase one by one). When you get to it just move towards a by (a%M) then finish the increase processes and move to a (a/M) times.

    The total cost for a given M is then ceil(a/M) + ceil(b/M) + M — 1 For each test case you can just iterate through all M up to 10^5. You don’t need to increase your leg more than that.

    hope I could help

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

      Nice thank you.

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

      I couldn't understand the ceil thing. what if to reach some cell my leg length is 4 and then I have to reach the cell 9,0. Then what you are saying is I will require ceil(9/4) that is 3 steps?? But after 4 there is no number divisible by 9 so it should be impossible to reach 9,0

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

        During the increase processes you will pass by number 9%4=1. Just move 1 towards the 9 then finish the increase and move 2 times 4 = 8.

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

      You don’t need to increase your leg more than ceil(sqrt(1e9)). Why?

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

        Counterexample: a = b = 1e9

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

        This was a rough incorrect approximation, n = 10^5 should work.

        anyway, looking at the larger input a=b=1e9, if you make your leg as big as x=ceil(sqrt(a)) your cost will be ceil(a/x) + ceil(b/x) + x — 1 which is about 3x ~ 96k. If you can get to the furthest point with cost about 96 thousand, you don’t need to ever increase your leg more than that, as the cost of increasing the leg would alone be more that that.

        → Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    You are optimising a/m + b/m + m + O(1) and minimum of (a+b)/m + m is reached in $$$\sqrt{a+b}$$$.

    I just found a minimum ans(m) = m — 1 + a / m + b / m + ((a % m == 0) ? 0 : 1) + ((y % m == 0) ? 0 : 1)

    for m in interval $$$\sqrt{a+b}\pm10$$$ (optimal constant is less then 10, but it's safer to overestimate it)

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

      Ahhhh, I got it. In the contest the formula having a minimum at a single point felt quite unituitive, and therefore I didn't follow that train of thought. I rather tried to minimize it at two points a / factorOfX and b / factorOfY separately, and hence used the factors logic. Just shows how easy it is to get lost in a wrong approach. But thanks a lot.

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

There are issues with problem D in the author's solutions even now. My hack got "Unexpected verdict".

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

    It's wrong now. The solutions gives a wrong answer for 1 8 2 10 20 30 1 1 1 1 1 1 1 1 1 1 1 1 1

    The correct answer is 8 instead of 3.

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

    Hopefully the issues with the hacks for this problem are resolved now.

    If there are still any, please report them as the answer to this comment.

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

I did binary search for B, but got wa. How to solve B?

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

B solution: we know that we would never need to increase more than S = 2 * sqrt(max(a,b)) times. We can now try out each max increase from 1 to S. Each time we go from S and reduce the maximum possible for each a and b. This will be done in log(n) times.

https://codeforces.com/contest/1814/submission/201083355

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

    Can you elaborate it a little more

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 5   Vote: I like it +8 Vote: I do not like it

      yeah let say max(a,b) is 100, i don't see how we would ever need to make m go above 20. Idk how to prove it though. a looser bound would be 2 * sqrt(max(a,b). Let say you are going to increase m to more than sqrt(max(a,b), you would never need to go more than 2 * sqrt(max(a,b) because during that time you could just decrease the whole thing down to 0.

      If you already know the max of m, then you can try out the max of m is from 1 to sqrt(max(a,b)) breaking down a and b is going to be like:

      • decrease some number of times of 1 from a and b
      • decrease some number of times of 2 from a and b
      • decrease some number of times of 3 from a and b
      • ...
      • decrease some number of times of m from a and b
      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        For test with $$$a = 39$$$ and $$$b = 49$$$ you need to set $$$m = 10$$$ to minimize your total number of operations(as far as I can tell). I just found a upper bound for the max values of $$$a$$$ and $$$b$$$ and saw that I could brute force for $$$m$$$ within constraints.

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

          yea edited 2 * sqrt(max(a,b)) is the ceiling

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

        it is 3*sqrt(...) actually.I had myself tried 2*sqrt(...) but that gave me a WA.

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

    algoboi your intuition is wrong,we have to increase till 4 for the testcase a=8,b=4.

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

      i edited the comment. It's 2 * sqrt(). So if its 8,4 then you increase until 5

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

    You need to set S=sqrt(a+b)instead of S=sqrt(max(a,b))

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

      i don't think it's (a+b). a and b is kinda independent. Like you only need to care about the max of (a,b).

      so let say you increase m up to M. then for every 1 to M, you decrease some of that from a and b.

      Btw it's 2 * sqrt()

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        The function for max steps by foot length is f(x) = x — 1 + ceil(a/x) + ceil(b/x) You can approximate this to g(x) = x — 1 + (a+b)/x And then to find the local minimum you take g'(x) = 0 so 1 — (a+b)/x^2 = 0 so x = sqrt(a+b)

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

          can you explain how you got to that equation?

          i got AC'ed with 2 * sqrt(max(a,b)) https://codeforces.com/contest/1814/submission/201083355

          I used 64000 as the max here cuz of 10^9.

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

            Well, it's optimal to first raise your foot length up to some value k before starting to walk towards (a, b). As someone else mentioned above, at some point you will reach the intermediary values a % k and b % k so that you can reach (a, b) exactly and not go over it. So the number of operations for max foot length k is k-1 to raise foot length to k, ceil(a/k) to reach a on the vertical axis, and ceil(b/k) to reach b on the horizontal axis. That's how you get the formula I mentioned. You can get AC by checking k from [sqrt(a+b)-25, sqrt(a+b)+25] https://codeforces.com/contest/1814/submission/201106352

            It's not wrong to check all values of k up to 64000, you're just checking a lot of stuff that is not necessary to check. I'm just saying that the optimal k is around sqrt(a+b).

            → Reply
»
13 months ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

D solution: We know that we can always get a result at LCM(f1, f2, ..., fn) and the difference will be 0, and we would have to change all of di in this case. If we decide not to change all of di then at least one of them will be fixed. This can be tested by iterating at each ith and pretending we are fixing ith and try out every other di as at either the lower end or the upper end, Then compute the minimum number of changes fro every other positions. Complexity: f * k

→ Reply
»
13 months ago, # |
← Rev. 4   Vote: I like it +34 Vote: I do not like it

A: If k is even, we can pay only even rubles. Otherwise, we can pay even rubles or all prices >=k.

B: Unbalanced problem. If the length of leg is increased t times, we need ceil(x/(t+1)) steps for moving along x-axis, and ceil(y/(t+1)) steps for moving along y-axis, so answer is t+ceil(x/(t+1))+ceil(y/(t+1)). If there's no ceil function, by the basic inequality (a+b>=2*sqrt(a*b)) the answer is sqrt(x+y)-1 and optimal t is around sqrt(x+y). So I passed this problem by brute force for t in range [sqrt(a+b)-1000, sqrt(a+b)+1000]. Also we can use sqrt-decomposition to solve in O(sqrt(a)+sqrt(b)).

C: The cost for first robot is s1, 2*s1, ..., k*s1 for each position, and for second robot is s2, 2*s2, ..., (n-k)*s2. To choose k we can let k=n first, and reduce k by 1 while (k*s1) > (n-k+1)*s2. After decide k we can arrange r[i] by the reverse order of the cost of positions.

D: No idea.

E: By some small test cases we can guess that we need to fill the path by some blocks of size 1 or 2, and the size of blanks between each pair of adjacent blocks is 1 (that's because we need to make something like (i, i+1) --> (i+1, i) or (i, i+1, i+2) --> (i+1, i+2, i)), and the answer is 2*(sum of weight of edges in these blocks). If from each range [l, r] we set siz=r-l+1, start=a[l], end=a[r], ans[i][j]=the answer of problem on range [l+i, r-j] (here 0<=i<=2, 0<=j<=2), we can solve the problem by segment tree.

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

    for D : either change all element, or bruteforce on any one non changed element, and then use 2 pointers.

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

    For B, can you explain why it requires ceil(x /(t + 1)) steps to move for 0 to x ?

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

      Because we increase length by t times, the maximum step is t+1, so we need at least ceil(x/(t+1)) steps along x-axis. If x is multiple of (t+1), we can take (x/(t+1)) moves directly, and if x%(t+1)==k (k>=1), we can take a move when the length is k and do other moves after length become t+1, so we need at most ceil(x/(t+1)) steps.

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

    My idea for B was to make sqrt n blocks of size sqrt n, then find the block with the minimum cost. Then I checked that block and its left and right adjacent blocks. Does this capture the idea of sqrt decomposition? This is the first problem I've tried it on.

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

    Hey For problem B: how can I prove that, I need to increase length maximum one time. I mean, I can cover 'a' distance with some length and then I can increase length for covering 'b' distance. Why is this never an optimal choice?

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

      just forget that it is like you are fixing it and finding minimum among all m

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

        But this is not necessarily what question asks, my doubt is why this solution always gives the optimal answer. Because the other choice I mentioned is a valid move (may not be optimal) move according to question. So, there must be some proof that shows its always better or equivalent to consider this choice.

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

    Hi. I just wanted to ask if you exploited the fact anywhere in your algorithm that the blocks are of size 1 or 2 only (because the editorial's solution has not)?

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

      Any block of size n (n>=3) can be changed into 1 and n-2.

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

        Yes. I agree with that. I'm asking if you exploited this observation anywhere in your solution. The editorial solution doesn't use this observation anywhere.

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

          I exploited that. But actually we don't need this observation when implement solution with segment tree.

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

As a !tester, I'm proud to !be one.

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

How to solve F? I tried offline dynamic connectivity but don't know how to update the accessibility of vertices.

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

    We can create a directed graph representing the components in the dynamic connectivity. Whenever two components merge, we create a new vertex representing the new component, and it gets two arcs into the vertices representing the components we merged.

    We also mark each component that contains the vertex $$$1$$$; it can be done at the end of each call of the dynamic connectivity function (just before we roll back all the changes made in that call).

    Then, the vertex $$$x$$$ (of the original graph) belongs to the answer if the vertex representing the component containing only the vertex $$$x$$$ is reachable from any of the marked vertices. All we need to do to check that is to run DFS from all marked vertices in this directed graph.

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

    If you mean how to apply the method explained in this blog to this problem.

    Spoiler
    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do anyone know how to solve B? I didn't participate, but just looked at it, and it seemed interesting. My first thought was that if you can, you always want to increase the leg length up til its sqrt the distance you have to walk. So you look at the biggest square less or equal to x, and same for y. Then you subtract those two squares from x any y. Then you do the same process, all the way down. Keeping track of these squares you know when you have to move, and when you have to increase legs. Is this correct?

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

Problem B wa3 because I break when answer is greater than last answer.

Wrong Code

Then I printed all answer, and found that although the answer curve "looks like" go down and go up, but sometimes $$$ans(i) = ans(i-1) + 1$$$ while the curve is "going down"!

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

    In this problem, the answer is $$$\min \limits_t t - 1 + \lceil \cfrac{a}{t} \rceil + \lceil \cfrac{b}{t} \rceil$$$.

    Because $$$t - 1, \cfrac{a}{t}, \cfrac{b}{t}$$$ all have the slope increasing, so $$$t - 1 + \cfrac{a}{t} + \cfrac{b}{t}$$$ have the slope increasing, and $$$t - 1 + \lceil \cfrac{a}{t} \rceil + \lceil \cfrac{b}{t} \rceil$$$ have the slope almost increasing. However $$$\lceil \cfrac{a}{t} \rceil$$$ obviously don't have the slope increasing, so it doesn't truly have the slope increasing.

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

It is really sad to see my verdict of D changed from Accepted to Wrong Answer. Althougt my solution is actually wrong.

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

Task E was very cute

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

First time to become orange. But unrated.

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

I think it's funny my first sqrt decomposition solution was for a problem B. Not sure if it's correct though or testcases are just weak. The problems were interesting, maybe just a little unbalanced. Shame this round had so many technical difficulties.

→ Reply
»
13 months ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

One solution for B:

Given the final leg length $$$m$$$, the result is $$$ceil(\frac{a}{m}) + ceil(\frac{b}{m}) + m - 1$$$. How to find $$$m$$$? Intuitively we want to search around $$$\sqrt{a+b}$$$, but the ceiling makes things complicated. Using the relationship $$$ceil(\frac{a}{m}) + ceil(\frac{b}{m}) \in [\frac{a+b}{m}, \frac{a+b}{m} + 2)$$$, we find $$$m$$$ such that $$$\frac{a+b}{m} + m - 1 < 2\sqrt{a+b} + 1$$$, so the safe search range for $$$m$$$ is $$$(\sqrt{a+b} + 1 - \sqrt{1 + 2 \sqrt{a + b}}, \sqrt{a+b} + 1 + \sqrt{1 + 2 \sqrt{a + b}})$$$, so time complexity is $$$O((a+b)^{1/4})$$$. solution.

Additionally, we can use sqrt decomposition to reduce this to $$$O((a+b)^{1/8})$$$. The execution time is actually slower because of more operations. solution.

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

    We can search all natural numbers i, until i becomes > current answer. The complexity of this can be proven to be sqrt(max(a,b)).

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

      That's probably the fastest way to come up in contest! I was stuck on this for such a long time.

      → Reply
»
13 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Expectation: +delta Reality: unrated Action: Nothing to do except Down vote xD

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

My Solution for Problem B

Check the cost for each strength from 1 to 50k

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

    Can i apply ternary search (as this is a unimodal function) in this problem...?

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

      No. This is not unimodal function. For example, if a = 100 and b = 50, you can notice that after the function reaches its minimum it doesn't increase strictly.

      → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

I made a cubic solution in problem D and got AC (2870 ms) submission

Someone can hack me ? :)

Upd: I did it!

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

can someone tell me how the case "5 3" has 5 as the answer on problem B? edit: NVM

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

Perfomance 2700 drop to 2350 (D hacked)TAT Fine unrated whatever

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it
Sad noise intensifies
→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with D? WA on one test in case 4. Couldn't figure out the problem.

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

    In your "state" vector, you are considering two values per element. But there can be a third value, which leads to a better solution.

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

      Appreciate the help! But this is a bit counterintuitive for me. Say the target is 10. And fj is 3, isn’t testing 9 and 12 sufficient?

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

      Figured out. Thank you!

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

    Take a look at Ticket 16814 from CF Stress for a counter example.

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

i dont understand why full bruteforce works in B. it is 100*(2e9) operations in the worst case, isn't it? where am i wrong? https://codeforces.com/contest/1814/submission/201061363

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

    It's not full brute force, ans is getting minimized. As you can see this comment the graph has a lower minima, so once the value of ans is minimised the condition for loop is also changed, so the value of m will be around 5e4 at max, SEE the variable name.

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

      But there is no break condition on that

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

        The thing is value of ans at first is 1e9, but once the loop is started, the value of ans is reduced, ans is NOT constant, it changes in the loop. See the variable names

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

    ans variable in the for loop is not a constant..

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

    FR. Same question, but why mine didn't pass then it has the same complexity. link

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

      i iterate from 1 to 1e18 and it still passes..

      upd: nvm im dumb

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

        LOL. But guys in the comments above helped me out to understand. The range of the loop is ans, which decreases over time inside the loop, it makes sqrt complexity.

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

Why does not Um_nik's solution for B TLE? link to his sol

it seems that he brute forces a + b numbers for each test case. Wouldn't it be $$$10^4 * 2 * 10^9$$$ operations in the worst case?

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

awoo ,Please upload the editorial.. IT will be helpfull for us.

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

For question B - its always better to first increase the value of m and then going on x and y. for finding the optimal value of m we have f(m)=m-1+ceil(x/m)+ceil(y/m) for finding the minimum value we can differentiate this function and should put it's value =0,so by putting d/dm(f(m))=0 we have 1-x/m*m-y/m*m=0 ,by this we can get m=sqrt(x+y),as it is a ceil value so to be on the safer side we should check for sqrt(x+y)-100<=m<=sqrt(x+y)+100

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

Probably my best performance in a contest just for it to get unrated (╥_╥)

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

I'm a little disappointed that my O(N^2 log N) solution for Problem D timed out when using std::set<>, but passed when using a pair of std::priority_queue<>'s... I feel like the input constraints should allow bouth (3000 × 3000 × 2log(3000) = ~100,000,000, which seems okay for 3 seconds).

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

    Priority queue is 3-10 times faster, than set. Also, unordered_set is 1-2 times faster than set, but has less applications.

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

      You're right that priority_queue<> is faster than set<>, which makes sense because it doesn't maintain a complete ordering of elements, but it's less than 2x faster on this problem by my measurements, so I would expect the constraints to allow both or neither solution to pass.

      std::unordered_set<> is a different story altogether: it's typically backed by a hash table, which makes it asymptotically faster than std::set<> (O(1) vs O(log N), average case) but it doesn't support extracting the minimum element, which is the operation I need for this problem, so it's not really helpful here.

      edit: On second thought, I could still use a std::unordered_multimap<> since when removing elements, the keys (power levels) are known, just not the values!

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

    i also had a my n^2logn solution fail and had to constant optimize it to get passed (my log was from a std::sort).

    I dont get the point of keeping such a low k (yes i know n^2 + nk exists but its easy to get n^2 logn from there) and making TL tight for n^2 logn tbh.

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

    Can you explain your solution?

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

      Sure! The central idea is to assume that there is one power level P[i] that doesn't change. Then, we have to consider possible ranges of [P[i]-K, P[i]], [P[i]-K+1, P[i]+1], ..., [P[i], P[i]+K]: all other power levels must fall in one of those ranges. It's easy to check for a range [P_lo, P_hi] whether the other values already are or can be changed to fall into that range, but that naive approach would create an O(N × K × N) solution which is too slow. The solution is instead to start with the earliest range and updated it incrementally (a sliding window algorithm).

      I think the priority_queue<> version is easiest to understand: in_range contains a list of all power levels (pair with their index) that either already were or could be changed to become between P_lo and P_hi, and num_changed counts the number of changes that were necessary. If a power level couldn't be changed to a value in range (since P[j] must remain a multiple of F[j]), the smallest possible value greater than P_hi is stored in over_range instead. Now we can tell whether a range is valid (whenever over_range is empty), and it's easy to update a range from [P_lo:P_hi] to [P_lo+1:P_hi+1] by removing the guns with power level P_lo from in_range and adding guns with power levels P_hi from over_range.

      For complexity (but not correctness) it's important that when changing the power level to be in range, we pick the largest possible value. An example where performance would be bad if we used the smallest value is K=1000 and P[j]=1: we'd be removing and reinserting the same gun index 1000 times. But by using the highest value we guarantee that each P[j] increases by at least K/2 every time (excluding the 1 time when we use the original value P[j]). This guarantees that the solution takes O(N × N × log N) overall, with log N accounting for the overhead of the data structure.

      → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

C is scary at first peek, but it turns out quite easy to solve. B is completely opposite...

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

Most of the solutions here for problem B involve brute forcing a specific range of values for m, but I passed it with a different technique.

My technique just tries every minimum m that will cause either ceil(a / m) or ceil(b / m) to change, since trying other values will just increase the total moves. Submission

I assume the number is bounded by C * sqrt(max(a, b)) where C is some constant (maybe 4?) because the number of factors for a number n is bounded by 2 * sqrt(n). Can anyone tell me the bound on the distinct number of ms and why? Thanks.

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

    It is indeed sqaure root, google sqrt decomposition.

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

      How is this related to square root decomposition? If I'm not mistaken, isn't that a data structure / strategy for range updates / queries?

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

        Maybe I am messing up terms. So here is a sketch of proof.

        Claim: $$$ceil(a/m)$$$ has $$$O(\sqrt{a})$$$ unique values.

        Note that for $$$m <= \sqrt{a}$$$, there are at most $$$\sqrt{a}$$$ unique values. For $$$m > \sqrt{a}$$$, $$$\frac{a}{m} < \sqrt{a}$$$, so again, at most $$$\sqrt{a}$$$ unique values.

        I cannot find English material on this yet, maybe someone else can point the way. Here is a Chinese OI wiki page: link

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

          Thanks! I get it now. I assume the constant C I mentioned will be equal to 2, which makes the complexity the same as the number of divisors then.

          → Reply
»
13 months ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

201082916 this is my simple solution for problem B ,you can basically see that this is a Brute forces problem as you will find the best minimum solution between all solution ,so i can simplify the problem as you wanna go from point Zero to point M in minimum operations so as an example if you want to go from Zero to 12 you have the following options :-******** make M = 1 so ans will be 12 make M = 2 so ans will be 1 + ceil(12/2) = 7 operations make M = 3 so ans will be 2 + ceil(12/3) = 6 operations make M = 4 so ans will be 3 + ceil(12/4) = 6 operations

and so on if you continue after the root the answer will be get bigger again so the optimized solution will be always increasing M up to root a or b and other key observation here that we will always take ceiling of the divisibility because for example if we want to go from 0 to 12 and M = 3 so ans will be 2 + ceil(10/3) which is 6 so it will go like that we will first move from zero to 1 (operations = 1) and then increase M to 3 (operations = 3) and then we will move from 1 to 10 in 3 other steps (1 -4 — 7 — 10) so totally they will be 6 operations . Thanks for advance and you can check My Submission for details

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

Please anyone to explain B in simpler terms? I m not getting the equations! especially confused about how to know when to add +1 and when to go for multipliers , (how to mix them and how to get the equation for the mixing and how it's optimal )

thank you :(

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

    First, find the optimal value when the maximum jump size is some fixed constant J. In that case, you know you must spend J — 1 seconds increasing the jump size to J. As for the number of jumps, we claim the optimal number is ceil(a / J) + ceil (b / J).

    To prove it must be at least this value, note that J(ceil(a / J) — 1) < a (because ceil(a / J) is the first integer >= a / J) so it is impossible to cover a horizontal distance of a with less than ceil(a / J) jumps if the maximum jump size is J. Similarly, J(ceil(b / J) — 1) < b. This proves we need at least ceil(a / J) + ceil(b / J) jumps.

    And you can in fact do it in ceil(a / J) + ceil(b / J) jumps by jumping horizontally by a % J, vertically by b % J (which one is first is determined by which is smaller), and then repeatedly jumping by J.

    So this proves the answer is J — 1 + ceil(a / J) + ceil(b / J) when the maximum jump size is J. Now we just need to iterate over all values of J that could be optimal. Since a, b <= 10^9, J = 10^4 already gives a time < 10^5, and any J >= 10^5 clearly gives a time at least 10^5, so you only need to check J from 1 to 10^5.

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

      jumping horizontally by a % J, vertically by b % J (which one is first is determined by which is smaller), and then repeatedly jumping by J

      then is it not a%j + b%j + a/j + b/j +j-1

      IDK how J — 1 + ceil(a / J) + ceil(b / J) works, i am unable to understand and visualize it could you help me out with an example

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        Well the a % J and b % J are single jumps. For example, if J = 5, a = 24, b = 12, we should take the following steps.

        1. Raise the jump size to 2 (i.e. 12 % 5)

        2. Jump 1 time vertically

        3. Raise the jump size to 4 (i.e. 24 % 5)

        4. Jump 1 time horizontally

        5. Raise the jump size to 5 (i.e. J)

        6. Jump 2 times vertically

        7. Jump 4 times horizontally

        Total vertical distance: 1*2 + 2*5 = 12

        Number of vertical jumps: 3 (i.e. ceil(12 / 5))

        Total horizontal distance: 1*4 + 4*5 = 24

        Number of horizontal jumps: 5 (i.e. ceil(24 / 5))

        Total time raising jump size: 4 seconds (i.e. J — 1)

        In general the first zero, one, or two jumps should be spent making the remaining horizontal and vertical distances a multiple of J, and then the remaining jumps should all have size J.

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

          Thanks a lot , thats exactly what i needed. it was very helpfull

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

unrated wuwuwuwuwuwuwu

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

what can be the rating of problem B, C?

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

Is there any logic for the step size values to try in B? I was trying ceil(a/step1)+ceil(b/step2)+max(step1,step2)-1, but could not get what step1 and step2 should be.

→ Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Well the round didn't went as planned, but honestly I think the problems were great and indeed educational :)

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

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

→ Reply