okwedook's blog

By okwedook, 4 months 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

»
4 months 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 :)

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

    Oo maa go TURU SPOILER

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

      vai prochondo hastasi ei comment deikkha,A no problem er statement e thik silo na,onek kisu missing silo,pore obosso correcition korse,,,contest suru howar aghe eisob dekhe na ken bujhi na

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

    I will not trust you again.

  • »
    »
    4 months 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 :)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it
    Meme
»
4 months ago, # |
  Vote: I like it +533 Vote: I do not like it

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

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

    Indeed, your plans are beyond someone's imagination

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

    As a tester, nice to see 1-gon as a tester.

  • »
    »
    4 months 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....:)

  • »
    »
    4 months 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.

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

    We want cf round from you :)

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

    Unless...

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

    i am wondering why there is no 0-gon

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

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

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

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

»
4 months ago, # |
  Vote: I like it +253 Vote: I do not like it
Whenever authors recommend reading ALL problems...
»
4 months 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.

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

Chance for master xD

»
4 months 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

»
4 months ago, # |
  Vote: I like it +39 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it -41 Vote: I do not like it

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

I request authors to disclose problems rejected by Anton.

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

    +1

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

    They are just waiting for the coordinator to change and suggest them again;)

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

    I request authors to stop making contest for a while.

»
4 months 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?

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

    What's pfp? And why blue??

    • »
      »
      »
      4 months 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:)

      • »
        »
        »
        »
        4 months 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?

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

          Yeah, you're definitely overthinking;)

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

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

    Even you reposting your memes

    • »
      »
      »
      4 months 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

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

      Howdie! Detective want some real coke?

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

    true :XD

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

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

»
4 months ago, # |
  Vote: I like it -18 Vote: I do not like it
Upvote this comment for Good Luck!

¡Gracias!

»
4 months 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?

»
4 months 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?

  • »
    »
    4 months 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.

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

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

»
4 months 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...:)

  • »
    »
    4 months 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 :(

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

An unrelated question I've already asked a few times before — how long is codeforces going to lie about its Python version?

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

    I don't give a damn if morons are downvoting!

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

I hope I won't choke this round...

»
4 months 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)
»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

antontrygubO_o deserves applause for rejecting so many problems to make the round interesting

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

Problem D: Anton and Rejection

»
4 months 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"

  • »
    »
    4 months 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!

»
4 months 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.

  • »
    »
    4 months 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.

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

All the best guys.

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

C is interactive. Change my mind.

»
4 months 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?

  • »
    »
    4 months 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

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

Hope I get my green shade back this time

»
4 months 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)?

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

note: unusual duration XD

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

When Author tells "Don't forget to read ALL the problems." I think D or E will be easier than B or C. But I find D or E as same difficult as others contest.

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it
Meme
»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Not long left GL everyone HF!

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

I hope you didn't set all math problems

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

@cp1307 time se aajana

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

Why I am not improving !!!?

»
4 months 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!!

»
4 months 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.

»
4 months 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.

  • »
    »
    4 months 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

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

    I asked a genuine doubt related to the contest. You all be upvoting a lame MEME and instead of answering, u guys are downvoting it. Hope u guys are doing fine.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    IF I ask more than 40 queries in problem C1, what error will I get?
    

    Potential verdicts — WA and TLE. It could be either of the two. If you asked just as many, or less queries than the number of them that would fit within the time constraint of the question, then your code would give a verdict WA not TLE. Although if you asked more queries than the number that would have run within the time limit of the problem statement, then it would give you a TLE not a WA. I am providing the links of submissions I made to demonstrate either cases hope it helps.

    WA-107883927, TLE-107883969

    PS Don't bother about the downvotes UwU.

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

      Thank you for such a nice explanation and for the sample submissions.

»
4 months 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.

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

    Dude, respect for you. You at 1600 could solve only A till now, I don't know how noobs like me are exepected to compete in this round.

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

    Even i could solve only A

    I didnt try B because C1 seemed more interesting but dang it was too hard for me and I couldnt crack it

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

    Yeah this is so true...Every problem I tried gave WA...idk this round killed me.

»
4 months 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 :)

»
4 months ago, # |
  Vote: I like it -51 Vote: I do not like it

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

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

Problem D is really interesting. However, My greedy approach failed :(

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

Problem D looks similar to this

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

A& B look like :

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

DifficultForces :(

»
4 months 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.

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

what is pretest 5 for c1?

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

    did you try Input: n = 51

    hidden array = [50,49,48,47...(decrease by 1)...3,2,1,51]

    my code was making more than 40 queries (bcz, for this input, my code was running in the linear fashion instead binary search fashion) so, didn't submitted the code :(

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

Pretest 4 for E?

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

damn, what's test 7 on D?

»
4 months ago, # |
  Vote: I like it -18 Vote: I do not like it

ONCE AGAIN EASY D (1750)

»
4 months 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

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

problem D: how to sort subarray ??

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

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

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

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

»
4 months 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

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

I think the the blue tears in the profile picture of the round setter are shown to tell the participants that you're going to have those tears during the contest. Literally feeling like crying!!

»
4 months 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
  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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 !!

      • »
        »
        »
        »
        4 months 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

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

          ohh , fuck thanks dude !!

          • »
            »
            »
            »
            »
            »
            4 months 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 !!

            • »
              »
              »
              »
              »
              »
              »
              4 months 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

»
4 months 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

»
4 months 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.

  • »
    »
    4 months 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

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

      Lol. We're brute forcing instead of solving it mathematically.

  • »
    »
    4 months 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.

»
4 months 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?

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

    Subarray size can be at least $$$K$$$.

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

    Happened to me too

  • »
    »
    4 months 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
    
»
4 months 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?

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

Solution of B already available on stackoverflow

»
4 months 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

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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

  • »
    »
    4 months 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

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

      Because you can swap only ith to (i+1)th.

    • »
      »
      »
      4 months 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.

    • »
      »
      »
      4 months 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.

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

        Yea, we have to check sum(0...i) >= i*(i-1)/2 for every i from 0 to n-1. I dunno why I couldn't figure this easy logic in the contest

»
4 months 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.

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

Why am I getting idelness limit exceeded? 107863650

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

    try using cout.flush()

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

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

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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

»
4 months 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.

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

B killed me

»
4 months 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.

»
4 months 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?

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

    time limit is 4 seconds . Why it will fail ?

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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 ;)

  • »
    »
    4 months 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?

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

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

»
4 months 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.

  • »
    »
    4 months 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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

  • »
    »
    4 months 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 !!

»
4 months 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.

»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Now I can truly understand why your problems got rejected in the first place

»
4 months 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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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. :-:

    • »
      »
      »
      4 months 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...

»
4 months 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 ?

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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 )

      • »
        »
        »
        »
        4 months 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.

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

      i handled the repeating cases separately

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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..

      • »
        »
        »
        »
        4 months 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

»
4 months 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

  • »
    »
    4 months 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.

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

      Thanks for pointing it out, I misread the question, I taught max median in window size k question, but it's actually max median in window of size at least k. I taught I can solve D

      I have seen about sorted containers, since it's not allowed in most websites(i don't know why), I went with the 2 heap approach. is there any efficient way to remove random elements from the heap? and what is the efficient way to solve this question in python?

  • »
    »
    4 months 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

»
4 months 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.

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

Once again a question directly from Google, problem B!

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

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

Le me after this round -

Spoiler
»
4 months 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 (-_-)

»
4 months 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

  • »
    »
    4 months 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
    
    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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.

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

          Yes I get it. Thanks again!

»
4 months 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$$$).

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

.

»
4 months 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 .

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

Is there any solutions somewhere that I can find?

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

Wow!

What a wonderful contest! It made my day :D

»
4 months 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
»
4 months 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?

»
4 months 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

  • »
    »
    4 months 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.

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

    You are returning from the function without completely reading the input

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

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

»
4 months 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

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

Did someone else also face pretest 3 failing in C2? It has to be quite a good pretest!

»
4 months 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!

  • »
    »
    4 months 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?

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

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

Please release the editorial.

»
4 months 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.

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

can someone pls tell me how to try different testcases of interactive problem in my IDE

»
4 months 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.

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

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

»
4 months 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. :)

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

    It's official now. Can my last rating drop be reverted on compassionate grounds upon submission of the positive covid test result. Just kidding... :)))

»
4 months 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!!

  • »
    »
    4 months 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 :)

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

Thanks for your good problems that help me be the Candidate Master!

»
4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

»
4 months 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

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

Can anyone tell me whether the meaning of strictly increasing suits a sequence with 1 element or not?

»
4 months 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.

  • »
    »
    4 months 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.

»
4 months 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

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

E should be retested.

»
4 months 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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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

»
4 months 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:(

»
4 months 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

»
4 months 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!

»
4 months 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! :)

»
4 months 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

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

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

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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.

  • »
    »
    4 months 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.

»
4 months 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

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

Great question C2 really liked it

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

Problem B statement: Are there any non-2D planes? And "восточная выставка" is "oriental fair" in English. ;)

»
4 months 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.

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

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

»
4 months 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..

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

image

Strange

»
4 months 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

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

Question B Why not consider that a point may have multiple homes?

»
4 months 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...

»
4 months 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

»
4 months 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 ?

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

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

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

      Thank you for the problems okwedook, really nice contest although I solved only one, I enjoyed during the contest and after the contest learning through it.

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

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

»
4 months 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

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

why aren't any difficulty level tags provided for any of the questions which falls under this contest ?

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

can anybody tell me what is wrong in my code for problem D my solution my solution is in python3 it is a brute force approach for problem D. it may give Time Limit exceed but the point, it is giving Wrong Answer in test case 7. i don't know why because i feel the logic is correct. can you find the edgecase (why it is giving wrong answer verdict)

thank you in advance.