okwedook's blog

Codeforces Round #703 (Div. 2)
By okwedook, 3 years ago, In English

Hi, Codeforces!

I finally get to return something to this great community, so I am glad to invite you to take part in Codeforces Round #703 (Div. 2), which will take place on Feb/18/2021 17:35 (Moscow time). The round will be rated for the participants with rating lower than 2100. Participants from the first division are also welcomed to take part out of competition.

You will be given 2 hours 15 minutes to solve 6 problems. All the problems were created and prepared by me. One of the problems is interactive, please read the guide of interactive problems before the contest.

I would also like to thank:

Scoring: $$$500-1000-(750+750)-1750-2250-3000$$$.

Don't forget to read ALL the problems. I wish you good luck and high ratings!

I tried my best to create some good problems and clear statements, so I hope you'll enjoy the round:)

Story

UPD: Editorial

UPD: Winners and First to solve

Div1 + Div2

Place Participant
1 renascencepjw0510
2 dlalswp25
3 Bohun
4 kmjp
5 theodor.moroianu

Div2

Place Participant
1 renascencepjw0510
2 Quirrel
3 YuuKoito
4 _Nyusha_
5 JackF

First to solve

Task Participant
A king_of_tt
B IgorI
C1 dlalswp25
C2 dlalswp25
D Omer223
E lulzz
F JackF
  • Vote: I like it
  • +908
  • Vote: I do not like it

Comments Comments (260)
| Write comment?
»
3 years ago, # |
  Vote: I like it +93 Vote: I do not like it

As a tester, I must say problems are really interesting !! Good luck to all :)

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

    Oo maa go TURU SPOILER

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

    I will not trust you again.

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

    Problems were interesting (that idk) but till now I don't have any proof of solution of problem B!! I was submitting all the different possibilities and one of them passed :)

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

My plan succeeded! Now I will always be the lexicographically first tester!

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

    Indeed, your plans are beyond someone's imagination

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

    As a tester, nice to see Monogon as a tester.

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

    Hmm.. I'm sure that after you have posted this, at some point of time a user will make his/her name "1-" thus foiling your plans.It seems unlikely that such a scenario will ever occur, but let's wait....:)

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

    we love to see your name in the first place.

    Here is some suggestion that you should choose as lesser ASCII value as possible like this one -is-this-fft- can challenge you for first place. Just saying.

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

    We want cf round from you :)

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

    Unless...

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

    i am wondering why there is no 0-gon

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

Did he really thank Anton w/o any jokes? :upside_down_face:

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

As a tester, good luck. You would need it.

→ Reply
»
3 years ago, # |
  Vote: I like it +253 Vote: I do not like it
Whenever authors recommend reading ALL problems...
→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Looking forward to go gray in this round. This green is off-putting.

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

Chance for master xD

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

As a fellow victim of antontrygub I wish you a speedy recovery after the round

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

As a

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

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

I request authors to disclose problems rejected by Anton.

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

okwedook Is it blue tears in ur pfp after rejection of 29 problems by Anton?

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

    What's pfp? And why blue??

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

      OMG, I've googled it. It's a nice assumption, but the photo was taken before any rejects:)

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

        And there is some intention behind having that blue tear :P or I am just overthinking by seeing it?

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

          Yeah, you're definitely overthinking;)

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

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

    Even you reposting your memes

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

      I just saw this picture and felt it fits it more and it's not a problem to repost 1 year old meme so many could not have seen it and that's not the first time I repost a meme

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

      Howdie! Detective want some real coke?

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

    true :XD

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

The KING of Ad-hoc is back again as a coordinator!

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

OMG 29 problems were rejected !! Can you share some of them after contest?

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

Scoring shows 7 questions but you said there will be 6 questions.

What is correct?

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

    I think Problem C will have both an easy and a hard version.

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

      So they are counted as one question? Okay, got it

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

"My first message from message from MikeMirzayanov was more than a year ago!"

Shouldn't that be "My first message from MikeMirzayanov was more than a year ago!"?

Or is it a message from a message...:)

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

    I never get to figure out why some comments receives upvotes beyond imagination, while mine are always downvoted :(

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

    I read the same statement twice but couldn't figure out "message from" was written twice. I uncounciously skipped the duplication

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

If Anton would have been rejecting 29 problems in 135 minutes of the contest time that would make "a speed of rejection" almost about a problem every single 5 minutes 

(4.6551724137931... to be exact)
→ Reply
»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Problem D: Anton and Rejection

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

    This will also get rejected! xD!

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

    answer may be very large, so compute the answer modulo 1e9+7

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

please tell how to solve "C" after contest:) Update::first tell how to solve "B"

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

    sometimes i feel like how life would be if i donot get downvotes!

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

Please notice the unusual Score distribution. i.e. it seems that C1 will be easier than B.

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

    I wouldn’t infer that. It could be true, but I find it more likely that the problem as a whole is 1500, and if you can only solve it on reduced constraints you get half marks.

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

C is interactive. Change my mind.

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

I have some questions:

1- Can the rejected problem be modified and proposed again?

2- If not, can we have rejected problems in Gym added by setters?

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

    As you know, if the problem was rejected, then it is not prepared, because why

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

Hope I get my green shade back this time

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

Score for problem C is 750 so it means it will be easier than the problem B (having score 1000)?

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

note: unusual duration XD

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

...

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

I hope you didn't set all math problems

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

Why I am not improving !!!?

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

Getting you have submitted the same code, but I haven't made any submission!!

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

    Got same problem. And now i am sure that i just banged my head by giving this contest.

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

I'm not sure what' happening. I can't seem to send a solution for A. It always says I have sent this solution before, but when I look in my submissions I don't see it. I don't see anything. I have tried putting random stuff in it, I have tried from another browser. Nothing.

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

IF I ask more than 40 queries in problem C1, what error will I get? I am getting TLE. I want to know if its due to asking > 40 queries.

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

    You can't it will be a wrong answer you are supposed to find it in 40 or less

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

I really appreciate the efforts behind setting these problems. Everybody knows it was interesting. However all the problems starting from A were of a slightly higher level than usual. I understand the need to set interesting problems. But div2 is literally the most frequent round that is held, which means it needs to be catering to most ratings atleast for the first 3 problems. In that aspect, I am forced to think this round was a failure. I might be just another noob but I have only solved the first problem. But I know for a fact that the rest weren't the same level as other div2 rounds.

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

Its time to leave earth (after seeing problems). Bye guys! Anyway problems were interesting :)

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

I wonder why antontrygubO_o didn't reject all of your problems :(

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

Problem D looks similar to this

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

A& B look like :

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

DifficultForces :(

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

After seeing the problems I am sure why @antontrygubO_o rejected all your questions last time (that was really a nice story). Ok but as you told the questions were really interesting. "! But you should be in between the difficulty level of div2 !" Very first time I am seeing that the contest blog page upvotes are decreasing after and during the contest.

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

    +1

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

    This particular comment didn't age really well:) Just practice more and you'll get to solve more problems

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

what is pretest 5 for c1?

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

Pretest 4 for E?

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

damn, what's test 7 on D?

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

ONCE AGAIN EASY D (1750)

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

as a youtuber, here is the video solution to problem C2: https://youtu.be/TvosdMg9GXE
submission link: https://codeforces.com/contest/1486/submission/107881420

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

![ ](Screenshot-from-2021-02-18-22-19-46)

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

I bet all of my life on E, farewell everyone here!

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

Well, I learned that an array of 1 elements is in increasing order the hard way

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

Please help why i am getting compilation error in C1,C2 ? i think my code is fine , help needed ?

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

    Correct me if i'm wrong but isn't that comment in // fflush(stdout); } including the brackets?

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

      No dude it only comments fflush not the brackets !! what is my mistake can u tell me ? it is showing compilation error u can go to my profile and check the whole code !!

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

        There isn't a ; after int res = -1 edit: there is also no main function

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

          ohh , fuck thanks dude !!

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

            no dude , it did not resolve the problem again it is showing the compilation error !!

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

              Try to read your code carefully, you need to add the main function

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

Will binary search on BIT work in problem D ? Gave wrong answer on test 4

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

How to solve B?

I thought iterating $$$x$$$ in $$$[median(X_i) - 100, median(X_i) + 100]$$$ and $$$y$$$ in $$$[median(Y_i) - 100, median(Y_i) + 100]$$$ would suffice the solution.

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

    Exactly my thought too, tho instead of median, i did average, and from -5 to +5

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

    an easy hack against your solution, n=2 points at (0,0) and (1000,1000) the whole square is solution.

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

Reading the problem D: Aha! A similar problem, just use the sliding window medium

Few moments later: Why I always failed at pretest 7?

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

    Happened to me too

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

    Same, also fall into that trap. For those who want to use a dynamic size sliding window, you can try this test case

    9 3
3 3 3 1 1 1 4 4 4
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Damn I was just able to solve E theoretically with like 2 minutes left :((

Can someone tell me if this is the solution? You build a graph with V_even and V_odd. You run Dijkstra, but instead of updating the the distance of V_odd, you simply add all the options of parents to it, together with the weight of the edge and the weight of the last edge. Then when it's Vodd's turn, you go over all it's neighbors and choose the best combo of path + (edge1 + edge2)^2. The problem — it runs in m^2. The solution — w_i <= 50 so you don't have to save all the options, just the best option for every 1<=w<=50! then you iterate over all the neighbors at most 50 times

Is this the correct solution?

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

holly shit I got WA on pretest 2 on A don't know why then I jumped to B and didn't know how it could be solved then jumped to C and got TLE on pretest 4
I wish my meme is true cause I will lose 170 rating ugh that hurts

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

    you can check for this test case: 5

    4 2 5 1 3 this will be taking more than 40 queries for larger n

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

      damn I didn't have the time to think about this cause i submitted in the last minute

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

    Holy shit, feel you bro. Can't still understand why sum>=n*(n-1)/2 ? "YES" : "NO" will give the wrong answer on test case 2

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

      Consider the array 0 0 6. The sum is >= 6 but because we cannot move blocks leftwards, we cannot make it strictly increasing.

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

      Your code will fail on the following test case: n=5 1 1 0 3 5 You should check sum>=i*(i-1)/2 on every index or try a different approach.

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

For problem D, this was helpful https://codeforces.com/blog/entry/21103

If you are need a test case that break your solution, these may help

7 4
5 5 4 4 4 5 5

11 6
5 5 5 4 4 4 4 4 5 5 5

And I foresee problem D will become yet another coding interview question.

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

Why am I getting idelness limit exceeded? 107863650

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

    try using cout.flush()

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

      But I flushed the output several times and also used endl...

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

    Sorry for bumping but I can't really get the problem that the solution gives idelness limit exceeded

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

      I guess it's because endl has a flush effect. try #define endl '\n' on the top of the code

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

People like me, who had seen Cf Edu Binary Search step 4, can easily get the intuition for D. Loved the problemset. D was savior.

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

B killed me

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

Problem D is exactly the same as this one

For problem F, you can copy this code (statement: calculate how many pairs of paths intersect with each other) and 1336F - Journey then subtract the answer from the previous one.

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

Implemented some simple brute force in E which passed in ~800ms, now assume systest will make it fail. How to correctly solve E?

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

    time limit is 4 seconds . Why it will fail ?

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

      I am basically iterating all paths of len=2 and build a second graph from that. That feels to simple to be the right solution.

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

        It should ideally fail, consider any star graph, that will give you $$$O(n^2)$$$ edges in the new graph.

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

          Yes. Funfact, it passed the systests, so I got the nice plus delta, then later was hacked ;)

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

    Your first solution to E was skipped on main tests. What is it why does it happen?

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

    It didn't failed ;) . Was that due to to weak tests ?

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

How to solve B?

I know it's lame to ask... but please, any short solution would work.

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

    Try plotting some random points on Desmos or some other tool and brute force the answers. You'd see the pattern.

    I tried proving the solution for an hour, gave up and this seemed the only option left. :p

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

    I can give you a hint if you want. Ia a rush rn.

    It's related to median. For both x and y coordinates.

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

      Yes, I know that relation, but wondering how wd that be useful here.

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

    Problem B is a 2D problem which can be broken down into two independent 1D problems. First, minimize the sum of |xi-x| and then do the same for |yi-y|. The median of an array comes into play here.

    For array ai .... an, you have to choose a value k such that summation of |ai-k| is minimized. This can be done using median. You can apply it to the above 1D problem.

    It is a very vague explanation but hope this helps !!

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

C was a really nice use of binary search. Hope pretests were strong enough.

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

Someone please tell me why my solution is wrong and the other solution is correct. http://codeforces.com/contest/1486/submission/107798098 http://codeforces.com/contest/1486/submission/107782432

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

    In your submission, you do:

    else {
    f = 1;
    break;
}

    so you break early before you finish reading all of the input. Because there are multiple test cases, the input then spills over to the next test case, and everything gets messed up.

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

      Thanks a lot, Finally understood my mess after submitting it almost 4-5 wrong submission. :-:

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

      Your handle is also "smax", are you the author of Problem C1 and Problem C2? hhh...

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

For B question .. why does the count from avg-1,avg,avg+1 fails ?

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

    Average is not a correct answer to get minimum distance. For example, if we look only on X-axis and points at 0, at 4 and at 4 again, the average of them will be 8/3~2.66, but the best point to get minimum distance will be 4

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

      sorry but i forget to mention .. for cases with distinct nos like x[]=1,2,5,10,100; any intuitive/ mathematical proof ( generalized )

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

        In any case we need to use median instead of average. Lets imagine, that we have array of N different points and N = K*2 + 1 (just to make the explanation easier).

        Lets then pick median of this array as point P and calculate total distance to all points, it will be some number D. We may notice, that K points are to the left of P and K points are to the right of P. Denote distance to points to the left of P as D_left and distance to points to the right of P as D_right. So D = D_left + D_right

        Then look at neighbour point P - 1 and calculate total distance: 

        New distance = D_left - K * 1 (because we reduced distance to K points by 1) + 
1 (we increased distance to initial point P by 1) + 
D_right + K * 1 (we reduced distance to K points by 1) 
=
D_left + D_right + 1

        So by picking any other point then P we will increase total distance.

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

      i handled the repeating cases separately

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

    Take this array as example [2, 2, 11]. The avg is 5 which results in a total distance of 12. But if you use median instead of the avg, you definitely would get a better result. In this case when you choose 2 (which is the array's median) instead of 5 the total distance will be 9, which is better than 12.

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

      sorry but i forget to mention .. for cases with distinct nos like x[]=1,2,5,10,100; any intuitive/ mathematical proof ( generalized )

      i handled the repeating cases separately..

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

        [2, 3, 1000]

        your ans: 1330
        correct ans: 998

        The median is an optimal choice, because if x is smaller than the median, the sum becomes smaller by increasing x, and if x is larger then the median, the sum becomes smaller by decreasing x. — CP handbook

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

This is the first-ever time I got an idea on how to solve Problem D, to know the median in constant time we can use two heap approach, I made the window as two heap's and each time I move the window I insert an element into heap O(log K) time, but I don't know how to remove a random element from the heap in the logarithmic time since while sliding the window we need to pop the 1st element of the window each time. so I went by removing elements in O(K) time, but went with TLE in Test case 7. can someone help me on how to remove random elements from the heap with less complexity or any other better approach to solve the D problem?

Attaching my Python Solution. MY solution in Python Using Two Heap

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

    If codeforce were kind enough to accept sortedcontainers you could use SortedList. Also I think your solution would only return the maximum median of subarray of size exactly k and not at least k. so on n=5 k=2 a=2 1 2 1 2 your algorithm would answer 1 instead of 2 if it considers subarray of size 3.

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

    I once wrote a simple class to maintain a median, where you can add and remove values in O(logN). see this submission

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

Memory limit exceeded for using map in problem B. Anyone, any trick to modify this code to avoid MLE. I used map for storing the visited points in a recursive function.

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

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

Le me after this round -

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

Poor me created 5 cpp files for the contest and I only solved A (-_-)

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

What is the failing case for this submission? https://codeforces.com/contest/1486/submission/107861220

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

    Test with array $$$[1, 2, 3]$$$:

    INPUT    OUTPUT
              3
? 1 3
              2
? 1 2
              1
! 2
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yikes! I did try [1 2 3 4 5] during the contest, smh. Thanks!

      Edit — The one I submitted before this didn't have this problem. Can you think of some case for this one too? https://codeforces.com/contest/1486/submission/107847201. I tried to come up with something by myself but couldn't.

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

        With array $$$[8, 9, 6, 7, 4, 5, 2, 3, 1, 10]$$$, you get the following:

        INPUT      OUTPUT
               10
? 1 10
                2
? 1 2
                1
? 3 10
                4
? 3 4
                3
? 5 10
                6
? 5 6
                5
? 7 10
                8
? 7 8
                7
? 9 10
                9
! 10

        Can you see the pattern? If I use a larger array with the same pattern, you will definitely exceed the query limit.

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

          Yes I get it. Thanks again!

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

Before realising the intended solution to E, I was thinking about using Convex Hull Trick to optimize dijkstra in the following way. If I am at some vertex $$$u$$$, for every edge $$$(u, v)$$$ I insert into the convex hull data structure (initially empty) the line $$$mx + c$$$ where $$$m = 2 * w(u, v), c = dist[v] + w(u, v) * w(u, v)$$$. After inserting all of them, then for each vertex v I do $$$dist[v] = min(dist[v], w(u, v) * w(u, v) + query(w(u, v)))$$$, where query is the usual query for the convex hull trick data structure (returns the minimum function value) and $$$dist$$$ is an array containing the answer for all the vertices. I think implementing this directly in dijkstra won't work for a variety of reasons. I wanted to ask if there is any way in which we can use this trick to solve this problem for arbitrarily large edge weights (say $$$1 \le w \le 10^9$$$).

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

.

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

In problem B "sum of distance" instead of "summary distance" would have saved time of both setters and participants .

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

Wow!

What a wonderful contest! It made my day :D

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

Can D be solved using ordered multiset and considering the subarrays of size k only? like this,

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

Impressive, Qzy___ solves B on 0:11 (107793144) and D on 0:12 (107794288). How do you guys do it with such difference in the code style? Do you keep two different templates for some reason?

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

107793970

Where does my solution fail in A. Can anyone help

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

    Your early return causes issues since you still need to read all $$$n$$$ integers.

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

why the brute-force is passing problem E????

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

Answer for problem F is the number of path pairs that intersect at least one edge minus the number of path pairs that intersect at least one vertex

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

Can someone tell me whats wrong with this solution for problem A: https://codeforces.com/contest/1486/submission/107836476

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

The pretests for A were that good, that there was no test where submissions without long long would not pass. Good job!

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

    How do you check how many solutions FSTed? Is it through the status tab?

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

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

Please release the editorial.

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

Which was the point of E? It was just an easy and classic Dijkstra.

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

The official can tell me why my code was skipped for C1 question, I didn’t give anyone my code.

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

    Your submition skips when you submit another one that passes pretests.

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

Today I learned a lesson — don't participate in a contest while sick with (probably) COVID-19. :)

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

For the first time, in my room no solution failed system tests!! Thanks for strong pretests!!

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

    Well, it's easy to make it appear like there are strong pretests when systests are absolutely garbage :)

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

Deleted

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

c1 should have larger amount of queries, my code was right but i did not bother to do a simple optimization on queries as there was already a c2 with less queries.

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

    Your mistakes should be fixed by you, not by problems setters.

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

      Yes, sorry i agree that it was my mistake, but c2 with less queries just messed that thing in my mind.

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

How can a $$$O(n \times m)$$$ solution pass the system testing (or even the pretests) on problem E?

This is the submission. Clearly two for loops.

107866037

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

I think Problem C1 and C2 are just like one problem? I can't feel the gap between them.

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

    In C1 you can perform two queries in each iteration of binary search which gives a simpler solution than that for C2.

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

OK. As it seems someone really tried to make weak pretests. There was so obvious error in my code. And I got pretests passed. What's the point of giving feedback, if obviously wrong solutions pass pretests? just look what have I written: "if(ans==ind)r=mid,l=mid;" and it passed pretests. I will worry about my rating, but it's funny

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

E should be retested.

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

Can anyone tell me what does the Error in this solution means https://codeforces.com/contest/1486/submission/107864397

, And can someone give me one TC on which this solution fails. Helping in even one would be highly appreciated . Thanks in Advance

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

    With array $$$[1, 2, 3, 5, 4]$$$:

    INPUT    OUTPUT
              5
? 1 5
              5
? 1 5
              5
? 5 5

    The last query shown above is invalid, since the subarray needs to have at least size 2.

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

      Is this the Error that the CF judge has also mentioned BTW Thanks for your help

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

I made a stupid mistake and used k+1 instead of k in D, passed pretests, but failed in system testing:(

And I went all the way from Rank 3 to Rank 23:(

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

E should be retested. There are codes that solves E by making a M^2 edges Graph

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

The problems were really interesting!

Kudos to the authors, and the coordinators involved! :)

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

okwedook MikeMirzayanov I would like to request a rejudge of E because the judge behaviour is inconsistent: 107850881 is TLE and 107877393 is AC but both are the same code (you can check with Compare)

UPD: of course, the algorithm itself is not randomized in any way

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

    This comment might be able to explain the mentioned judge behaviour.

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

      I understand why this may happen, but I think that it is not my problem if the CF server was a bit slower in one of the runs. The behaviour should be consistent because, if I understand the situation correctly, I passed the pretest during the contest and failed the same pretest afterwards. This is clearly unfair because I was lured into the fake sense of security by 25! strong pretests, and (based on the "passed pretests" verdict) decided not to optimize my solution further during the contest not to lose points.

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

        You passed pretests with 3992ms. And then decided to not optimize further? Sorry, but that is known to be no good idea.

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

          When I see such execution times on a high number of pretests, I think "oh, they must be quite strong". Regardless of what I think, CF cannot implicitly assume that I should optimize my code whenever I see high execution times on pretests because I may fail the same test later.

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

    Ok, after a bit of thinking I came to the conclusion that rejudge is not a good solution in a long run, and my best idea so far is not to re-run the pretests during the system testing. This way my argument about inconsistent behaviour will not be as legitimate.

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

wrong answer Integer parameter [name=query_r] equals to 27671, violates the range [27672, 99999]

Could anyone please tell me what this means? I got this for C1

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

    I too had the same error , it means that in a query , your l and r are equal

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

Great question C2 really liked it

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

what a great set of problems. thank you and thanks to the coordinator for rejecting the other problems.

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

very weak test cases in C2, E....

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

I am getting runtime error on testcase 6 for the E problem , here is the link of my submission , can some one please check it!!, What I have done is kept n*51 states and edge of weight 0 between (u,0) & (v,w) , edge of weight (a+w)^2 between (u,a) & (v,w) , for the edge u,v with weight w given in question, I applied dijkstras on transformed graph..

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

image

Strange

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

i whink DE is a bit too easy for its position, D ia a sinple binary search and E's dijkstra solution is O(m log 50m)

maybe better if put them in CD and get a harder problem for E

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

For problem E, O(NM) passed system tests. The hack cases can be generated easily with a simple source. It's amazing that the system tests didn't had any hack cases for the O(NM) solutions...

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

Can someone help me to find what's wrong with my solution for Problem A ? 107831213

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

the approach discussed in Question B can be extend to 3D plane also ?

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

    Yes, any number of dimensions. They'll all be independent.

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

Can someone elaborate how you all are creating graph before applying Dijkstra?

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

I am observing about a 2x difference between the runtimes of two solutions, by just changing the way I am indexing the array. I understand that this is because of different localities of reference between the solutions.

Yet, I am not able to figure out why one of these has a higher locality of reference. If someone can help me figure out the same, it will be greatly appreciated.

These are the two submissions: 108047029 108047388

→ Reply