okwedook's blog

By okwedook, 9 days 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

»
9 days 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 :)

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

    Oo maa go TURU SPOILER

    • »
      »
      »
      7 days 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

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

    I will not trust you again.

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

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

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

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

    Indeed, your plans are beyond someone's imagination

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

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

  • »
    »
    8 days 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....:)

  • »
    »
    8 days 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.

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

    We want cf round from you :)

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

    Unless...

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

    i am wondering why there is no 0-gon

»
9 days ago, # |
  Vote: I like it +72 Vote: I do not like it

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

»
9 days ago, # |
  Vote: I like it +111 Vote: I do not like it

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

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

»
8 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Chance for master xD

»
8 days 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

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

»
8 days ago, # |
  Vote: I like it +93 Vote: I do not like it

I request authors to disclose problems rejected by Anton.

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

    +1

  • »
    »
    8 days 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;)

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

    I request authors to stop making contest for a while.

»
8 days 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?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's pfp? And why blue??

    • »
      »
      »
      8 days 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:)

      • »
        »
        »
        »
        8 days 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?

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

          Yeah, you're definitely overthinking;)

»
8 days ago, # |
  Vote: I like it +235 Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

¡Gracias!

»
8 days 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?

»
8 days 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?

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
8 days 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...:)

  • »
    »
    8 days 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 :(

»
8 days 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?

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

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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 days 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)
»
8 days 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

»
8 days ago, # |
  Vote: I like it +32 Vote: I do not like it

Problem D: Anton and Rejection

»
8 days 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"

  • »
    »
    8 days 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!

»
8 days 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.

  • »
    »
    8 days 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.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

All the best guys.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C is interactive. Change my mind.

»
8 days 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?

  • »
    »
    8 days 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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I get my green shade back this time

»
8 days 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)?

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

note: unusual duration XD

»
7 days 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.

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

Not long left GL everyone HF!

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope you didn't set all math problems

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

@cp1307 time se aajana

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Why I am not improving !!!?

»
7 days 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!!

»
7 days 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.

»
7 days 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.

  • »
    »
    7 days 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

  • »
    »
    7 days 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.

  • »
    »
    7 days 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.

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

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

»
7 days 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.

  • »
    »
    7 days 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.

  • »
    »
    7 days 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

  • »
    »
    7 days 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.

»
7 days 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 :)

»
7 days ago, # |
  Vote: I like it -51 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D looks similar to this

»
7 days ago, # |
  Vote: I like it +42 Vote: I do not like it

A& B look like :

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

DifficultForces :(

»
7 days 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.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

what is pretest 5 for c1?

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretest 4 for E?

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

damn, what's test 7 on D?

»
7 days ago, # |
  Vote: I like it -18 Vote: I do not like it

ONCE AGAIN EASY D (1750)

»
7 days 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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D: how to sort subarray ??

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

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

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 days 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

»
7 days 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!!

»
7 days 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
  • »
    »
    7 days 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?

    • »
      »
      »
      7 days 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 !!

      • »
        »
        »
        »
        7 days 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

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

          ohh , fuck thanks dude !!

          • »
            »
            »
            »
            »
            »
            7 days 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 !!

            • »
              »
              »
              »
              »
              »
              »
              7 days 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

»
7 days 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

»
7 days 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.

  • »
    »
    7 days 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

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

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

  • »
    »
    7 days 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.

»
7 days 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?

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

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

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

    Happened to me too

  • »
    »
    6 days 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
    
»
7 days 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?

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

Solution of B already available on stackoverflow

»
7 days 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

  • »
    »
    7 days 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

    • »
      »
      »
      7 days 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

  • »
    »
    7 days 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

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

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

    • »
      »
      »
      7 days 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.

    • »
      »
      »
      7 days 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.

      • »
        »
        »
        »
        7 days 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

»
7 days 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.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I getting idelness limit exceeded? 107863650

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

    try using cout.flush()

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

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

  • »
    »
    7 days 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

    • »
      »
      »
      7 days 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

»
7 days 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.

»
7 days ago, # |
  Vote: I like it +5 Vote: I do not like it

B killed me

»
7 days 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.

»
7 days 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?

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

    time limit is 4 seconds . Why it will fail ?

    • »
      »
      »
      7 days 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.

      • »
        »
        »
        »
        7 days 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.

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

  • »
    »
    7 days 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?

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

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

»
7 days 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.

  • »
    »
    7 days 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

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days 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.

  • »
    »
    7 days 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 !!

»
7 days 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.

»
7 days 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

»
7 days 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

  • »
    »
    7 days 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.

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

    • »
      »
      »
      7 days 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...

»
7 days 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 ?

  • »
    »
    7 days 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

    • »
      »
      »
      7 days 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 )

      • »
        »
        »
        »
        7 days 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.

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

      i handled the repeating cases separately

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days 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..

      • »
        »
        »
        »
        7 days 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

»
7 days 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

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days 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?

  • »
    »
    7 days 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

»
7 days 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.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Once again a question directly from Google, problem B!

»
7 days ago, # |
  Vote: I like it +44 Vote: I do not like it

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Le me after this round -

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

»
7 days 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

  • »
    »
    7 days 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
    
    • »
      »
      »
      7 days 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.

      • »
        »
        »
        »
        7 days 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.

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

»
7 days ago, # |
  Vote: I like it -13 Vote: I do not like it

antontrygubO_o should have also rejected your B too;(

»
7 days 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 .

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any solutions somewhere that I can find?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow!

What a wonderful contest! It made my day :D

»
7 days 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
»
7 days 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?

»
7 days 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

  • »
    »
    7 days 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.

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

    You are returning from the function without completely reading the input

»
7 days ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
7 days 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

»
7 days 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!

»
7 days 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!

  • »
    »
    7 days 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?

»
7 days ago, # |
  Vote: I like it +38 Vote: I do not like it

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please release the editorial.

»
7 days 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.

»
7 days 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

»
7 days 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.

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

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

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

  • »
    »
    6 days 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... :)))

»
7 days 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!!

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days 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.

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days 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.

»
7 days 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

»
7 days 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?

»
7 days 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.

  • »
    »
    7 days 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.

»
7 days 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

»
7 days ago, # |
  Vote: I like it +30 Vote: I do not like it

E should be retested.

»
7 days 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

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days 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

»
7 days 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:(

»
7 days 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

»
7 days 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!

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

»
7 days 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

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

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

    • »
      »
      »
      7 days 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.

      • »
        »
        »
        »
        7 days 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.

        • »
          »
          »
          »
          »
          7 days 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.

  • »
    »
    7 days 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.

»
7 days 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

»
7 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Great question C2 really liked it

»
7 days 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. ;)

»
7 days 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.

»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
7 days 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..

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

image

Strange

»
7 days 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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days 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...

»
7 days 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

»
7 days 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 ?

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

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

    • »
      »
      »
      6 days 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.

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

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

»
5 days 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

»
5 days 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 days 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.