Блог пользователя Stepavly

Автор Stepavly, 3 года назад, перевод, По-английски

Unfortunately, due to Internet provider network issues, we have to postpone the round. The current plan, that the round is postponed by 24 hours, will start on May/05/2021 17:35 (Moscow time).

Hello, Codeforces!

<almost-copy-pasted-part>

Hello! Codeforces Round #719 (Div. 3) will start at May/05/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems for this round were invented by MikeMirzayanov, Supermagzzz, Stepavly and Aris.

Thanks to Gassa, BledDest, Programmer, bugdone, ruban, RedAnt, songsinger and Gornak40 for help with testing the round.

Thanks to MikeMirzayanov for platforms and coordination of our work. Good luck!

</almost-copy-pasted-part>

Editorial is ready!

  • Проголосовать: нравится
  • +275
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -71 Проголосовать: не нравится

Most awaited round of the month.

»
3 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

My first rated contest pretty excited :)

»
3 года назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Sorry but I don't really understand the trusted rules :( Does that mean I can't use clones?

»
3 года назад, # |
  Проголосовать: нравится -46 Проголосовать: не нравится

Div. 4 when?

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится -41 Проголосовать: не нравится

    What is div 4 ?

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

      Does a contest always mean solving hard problems :)? Even a div. 4 contest with easy/tricky problems can be fun at times.
      What I think is, coding is not always about solving hard problems, let there be fun.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        I can't disagree, but what's the point of solving easy problems if they don't bring you any benefit, just a waste of time? is not it ?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

          I think solving easier problems(which we can solve faster), can be a really good warm-up.
          Sometime when I feel dull, or like I am unable to perform well, I go for solving some easier problems. That really helps in gaining pace.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            yes, agreed but most of the people asking for div 4 are generally doing it just in hope of positive rating.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      nice argument

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Funny calling him noob when he has a rating higher than you.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Really excited for my second contest , hoping i would cross 1000 this time. Any tips are welcomed. TIA

»
3 года назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

how to become red coder in 1 month???? any tips and tricks???

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Hmmm, why aren't we seeing vovuh as a problem setter in recent div.3 contests?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Stepavly contests are like the old DIV 3.5, Vovuh DIV 3's were, indeed, a bit tricky especially the latter problems.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to see a cool problemset. Best of luck, All.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    As a tester I can assure you the problem set is cool :)

    Also be sure to read all the problems. Setters often write this, but in Div2 I think most of the time the last problems are really hard. But for Div3 I think it's really worth doing it (at least reading the first N-1 problems in a N problem set).

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      why doesn't this comment has the number of upvotes it deserves.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Hmm note that testers are usually part of conspiracies. So the N'th problem could be the easiest, we should try to solve that first.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

One more new author of div 3 *o*
Hope I become pupil again

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

I still remember the time when vovuh was a coordinator of Div3, it has been so long.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -31 Проголосовать: не нравится

    *has, try improving your grammar. Would really go a long way in interview preparation.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

      try not correcting others' grammar errors. would really go a long way in your interview process if interviewer's grammar isnt that great:)

»
3 года назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

please schedule the contest 1 hr earlier as it perfectly ends before dinner and good discussion time before going to sleep

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

...

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    Again, that's impossible. If you have good delta you have bad delta. If you have extremely good delta, you have extremely bad delta.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I can leave a message again Yea~

»
3 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

can i say that div 3 is the best training contest for who is less than 1600 rating and will be better if problem standard

»
3 года назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

It seems that the queue is really long......Can this round hold on time?

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Verdict: In queue

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

There is a problem with submission, it shows the "In Queue" verdict. Wish this will not happen in today's contest.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is anyone else also getting some 504 Gateway Time-out error or is it my network problem?

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Anyone else getting Bad Gateway errors lately?

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Notice unusual change in schedule.. :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I think it's better to have a postponed rated round than an unrated round
    (it doesn't matter to you as it is already unrated for you :D)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why was the contest postponed for a day?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Delayforces!!! :(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's been an hour since I submitted a problem. Still in queue :(

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

um so how many registrations will this round have now?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The least they can do is to reset the participants so that there won't be another 30k contest and it becomes unrated, seems like no one cares about div.3 contests.

»
3 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

It's my first time to see a 24-hour delay here.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nooo :((

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Peeporiot ;-;

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Better delay than unrated :(

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

So,30k+ participants this time?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

round is postponed, I was waiting and refreshing every 1 minute to see how much time left. sad life.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Since the contest was postponed, can you please open the registration again?

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Div 3 — Let's rock today.

(postponed :{ )-

Let's practice today :}

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

«К сожалению» — это вводное слово, и оно обособляется запятыми.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

due to Internet × wait until the registered participants over 30k √

»
3 года назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

I finished my talk over phone with bae just 5 mins before the contest only to know this... (Cry Emoji)

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

All this time.. i was refreshing my browser..thinking issue on my side.

»
3 года назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

The round has been postponed- NO WORRIES

IPL has been postponed- CRY, CRY, CRY :(

»
3 года назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

postponed for 24 hours! I will never participate in a CF contest if this contest has been postponed again!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Stepavly please enable the register button so that the people who have not registered and are the official trusted participants can register !! ** Thanks in advance ** !!

UPD : THANKS !! I have successfully registered now !

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

when I finish my dinner fast for the contest...

Unfortunately, due to Internet provider network issues, we have to postpone the round

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

.
Pics-Art-05-04-08-18-05

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Verdict: No Color! :(

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Cf: Hmm you're mad because we delay the round for 5 min sometimes WEll How About 24 hours !! Muahaha

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Really excited for the contest , hoping I would cross 1100 this time. Any tips are welcomed. TIA

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Good luck to everyone!

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

gM0ZCR.png when you heard the round was delayed

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This will be my second contest. I participated in last global round and I still don't know how the score works perfectly. In that contest I think they gave me less points for a problem with previous wrong submissions. Here when it says there's a 10 minutes penalty for wrong submission, is it saying that I will lose 10 minutes from the total 2 hours of the contest for every wrong answer?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    You are judged by number of solved problems, and penalty points. Foreach AC submission you get 1 solved problem, and the number of minutes from start of contest plus 10 minutes per wrong submission of that problem as penalty.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you. I thought it meant I would have less time to solve problems, misunderstood that

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

i have a feeling that site may crash !!!!!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why on equal rank in div3 contest gives less positive delta then div2 on same rank. Suppose x rank in div3 will give less positive delta than x rank in div2 ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    coz having the same rank in a more difficult contest(since better rated participants are rated in Div2 contests, than in Div3) is better.

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Hope the contests won't get unrated because of long queue, we are reaching close to 30k , at this rate we might be reaching around 32k easily

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Got It.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

It's starting finally: the most awaited contest since yesterday :)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Cheers Codeforces for 30K registrations once again!!!

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

my code is running from more than 10 min, i also tried to cout<<"HELLO"; but it also taking more than 10 min ; MY internet connectivity is good. i also tried to logout and log in

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Is there any queue issue :( , my code is in the queue for last 20 minutes

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

It seems that my submission for G is executed twice, is this right...?

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

you guys should give atleast some weight to out-of-contest submissions. It's not like everyone participates in div3 :|

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

fucking queue

»
3 года назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

;

»
3 года назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

THE QUEUE IS TOOOOOOO LONG I CANT STAND IT PLEASE MAKE IT UNRATED

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

After waiting for 4-5 minutes.

WA on test 1

»
3 года назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Queueforces :(

»
3 года назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

No way this can be rated!

»
3 года назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится

Interactive is not good when long queue time is there.

»
3 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

This Contest should have been extended by 15-20 min to compensate for long queue

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -23 Проголосовать: не нравится

    what if some people have work after it ? Extending round is always a bad idea. They can keep it for 15-20 min extra but it should be announced before the contest. for majority of people queue time didn't matter much and it was fair for everyone since everything was same for everyone.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Actually, there have been situations in which the contest was extended due to long queue. I think it wasn't a really smart choice to put >100 cases in G considering that both F1 and F2 were interactive, though.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I agree that people may have other commitments after the contest but extension has been done many times during some the previous Div 3 Rounds and extension gives relief in some sense . if you have another work just go for it , there will always be some contest in a week after it so you can make a comeback in it to recover your rating loss

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am eagerly waiting to see test case 5 of problem "D".

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C,D<A<<B<<<E,F1<<<<<F2<<<<<<<<<<<G I know the number of solves indicate otherwise (difficulty distribution linear from A to G) But just look at the number of wrong answers and solution size.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone confirm if problem G was dijkstra ? I just submitted it and excited if my approach is correct.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    No. Brute force Dijkstra should TLE because the complexity is of the order $$$\mathcal{O}(E(G)) \sim 10^{12}$$$

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      dijkstra is O(ElogV) and not O(EG) if you use min priority queue

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        How is $$$E(G)$$$ not $$$10^{12}$$$? If you directly bruteforce from each teleporter you have $$$mn \sim 10^6$$$ edges from each node and so it behaves like Dijkstra on a complete graph which obviously exceeds time limits. I just dropped the $$$\log V(G)$$$ factor because removing that doesn't make my argument fail.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          there is actually a better way to do this, you can add a dummy node to which you connect all teleporters (from), and then you connect the dummy node to all teleporters (to). So in this Case you only have O(E) edges

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Sorry, but I don't see how that's an improvement in the complexity.

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Like floki said, each cell has 4 edges going out of it (up, down, left, right), but also for each teleporter you add an additional edge to a dummy node (at most $$$nm$$$ more edges), and an edge from the dummy node to each teleporter (at most $$$nm$$$ more edges). So the total number of edges is at most $$$6nm$$$, which is reasonable but still hard to get to pass on this problem.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There should've been extra 10-15 minutes for such a long queue!

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Google-forces

»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

So, I waited 10 minutes to get a TLE on test 114 of G after the contest had ended already . LOL

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

SlowForces

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Waiting for this comment. In queue

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

WHAT A BAD ROUND!I must wait 8 minutes for the result of my submission.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I remember getting up for Kickstart round H last year, quite early in the morning, I think it was worth getting up. But not on that that day, its today, cuz problem E is literally this lol. Also Thanks to people like Galen, Ecnerwala, Neal, who posted solution to (problem E) that round that day. High rated people do have time machine xD.

»
3 года назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится

F2 was an absolute bomb. It's been a while that I see such a beautiful problem.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Agreed, the rest of the problems felt very standard and paled in comparison to F2.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Depends on your solution... Mine was using something like SQRT decomposition and was really boring. But the intended soln is indeed beautiful.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Bad internet situation.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I forgot to delete a part of my code in F1 that I used to verify my solution, but since I was still in the queue I did not realize it, I feel very bad :(

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    same here i also face same problem in c i printed NO instead -1 :( when i realize contest is over :-(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain problem F2 and G?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    F2: You can query each prefix of the array with step of 8 (that is, 1, 9, 17, ...) and store the number of zeros in it. Now to answer the query, you must first binary-search these prefixes (takes 0 queries), and then search among the remaining 8 elements using exactly 3 queries. Now what happens when we change some 0 to 1? Some suffix of our array with prefixes has to be decreased by 1. To perform these operations quickly, you could use a segment tree. BIT and sqrt decomposition should also work.

    The total number of queries is t*3+n/8 ~ 5,5*10^4 < 6*10^4

    IDK if this solution is the same as the author's one, but this one seems really beautiful to me.

    G: Notice that you either don't use the portals at all or use them exactly once (since we can omit the intermediate steps). The variant without portals is solved using trivial BFS. About the case with portals: you first go from (1, 1) to a portal, then pay its cost, then the cost of the second portal, and then you go from portal 2 to the end. You can compute these sum of the portal's cost and the cost to go to this portal from (1, 1) and select the one which minimizes this quantity as the first one. The case with the second portal is symmetric.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      For F2, you can break the interval into blocks of size 32 ([1,32], [33,64], ...) and query the number of 0s in each of them. This takes roughly 2*10^5/32 = 6250 queries. Then you can answer each k by finding its appropriate block and binary searching on it.

      Each answer will require 5 queries, so we use at most 5*10^4+6250=56250<6*10^4 queries.

      The advantage of using blocks instead of prefixes is that we only need to update a single block after each answer. Also, since we chose a block size of 32, we can directly iterate to find the block that will contain the answer (since 10^4*2*10^5/32 = 6.25*10^7).

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      My sqrt decomposition solution of F2 is giving wrong answer on test case 21 (queries limit exceeded). has anyone done using sqrt decomposition

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        for me, taking block size as $$$n^.5$$$ failed on TC 21, but taking block size as $$$n^.25$$$ worked.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        Taking block of sqrt(n) will not pass. In worst case with block size of n^0.5 length will be 450 and log of 450 is 8.8 ~ 9. so for 10^4 tests atleast 9*10^4 queries will be made.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It's helpful. Thanks !!

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    For G using k+1 portals is never more optimal than using k portals. Hence we shall use either 0 or 1 portal. let cost[i][j] = minimum cost to move from [i,j] to n,m using only adjacent moves. Now for each portal do cost[i][j] += matrix[i][j] and find the minimum cost to travel from a portal to n,m. Let this value be equal to min_cost.Now the answer to the problem would be minimum cost to reach from a portal [i,j] to [1,1] + min_cost + matrix[i][j]. Which is equivalent to moving from [1,1] -> p1 -> p2 -> [n,m]. Dont forget the case when you use 0 portals.

»
3 года назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

Please make this round unrated. Couldn't solve the problems on time due to the waiting thing.

It took 10 mins to get the final verdict to one submission.

»
3 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 or greater than 1600 or even equal, then the round will be un-rated for you.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Too much queue waiting time. Please fix this

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Someone confirm I'm not blind, this was the sample shown for problem F2: Image please load

So this seems to imply that you have to read in a 0 after each test case, which is a thing that some interactive problems make you do. But not this problem. When I tried to read in 0, I got runtime error on test 1, and removing that worked. So did the samples lie to me?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There should've been extra 10-15 minutes for such a long queue!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Site was down for the last few minutes.

»
3 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Solving problems is faster and exciting then finding it on google! :)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Exciting- Very true
      But any regular CP-er has already practiced these common problems and knows where they can be exactly found.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    If you have already seen those problems somewhere before then gj here's a candy

    Let us (newbies) enjoy those quality problems.

    also imo, adding classical problems in a div3 is actually a good idea as they are hosted to improve your skill not the ratings

    but hey! you can switch the platform whenever you feel like ;)

»
3 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Started the contest 15 minutes late, but still managed to get till F1 in 1 hr 30 minutes. My best performance so far, thanks for the round and hope it remains rated.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    " Started the contest 15 minutes late "

    lol, you made 2 submissions before starting, thats so cool!!

»
3 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Anybody else think that solutions should be regraded for problem G with an easier time constraint? Maybe it's just java idk :P

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me whats wrong in this code 115328097

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

If long queue would not have been there then I could have got F1 and F2 right in time.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did someone got G?? I got WA on test-26

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

At least there should have been a 10/15mins extension of contest duration was needed due to the long queue problem. I just needed to change the answer from int to long long to get problem E AC. :(

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I'm so stupid!!! I used INT_MAX as infinity value in problem E :(

wrong ans on test 5
»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

too many copy-paste problem :(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did anyone else get WA on test case 37 for G? My submission if anyone wants to check it out.

My approach:

Do Dijkstra's algorithm, and find the shortest path to enter a portal (call it $$$P$$$). Then, run a multi-source Dijkstra's, with each source being a portal, and the starting distance to the portal as $$$P$$$.

In my code, the priority_queue stores <-distance, pii{i, j}>, and the distance is stored as negative, because Dijkstra's uses a min heap, while the default priority_queue<> uses a max heap.

The dijkstra lambda function is just so that I don't need to copy-paste the code.

The portal variable stores the shortest distance to a portal.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe the optimal answer may not contain a portal? It depends on how you wrote your code

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That's not it, because I only update a node if it has a new shortest distance.

      That's the purpose of the if (dis[i][j] <= -d) continue; code.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So far the Weakest pretest for problem D.. disappointed :|

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Weak test cases for problem D. Disappointed :|

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Nice problems, but really bad problem statement in F, especially F2, description is hardly understandable, and description of input simply wrong.

I am shown as +100, but would rather see it if it were unrated.

Also the queue was slow.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to check expected rating change before official changes ??

  • »
    »
    3 года назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    Totally agree about F2

    It is rather confusing to say the least

    First there are too many letters to be easily comprehended. But that's not the only problem

    For example at some point they talk about "requests", then there are "queries". You would think it is different things,

    Then right after the description of the output format there is "In case of an incorrect query, -1 will be displayed" and you try to match with the format, thinking that maybe you need to read some confirmation code after you cout the answer because it is natural to think outputing the answer is a kind of query

    Finally there is brilliant statement "Then t lines follow, each of which contains one integer k". I don't know about others but for me it means that at this point I can read t lines.

    Yes, it is possible to figure out what was meant by rereading the samples and 1KB statement a few times or by requesting clarificiation, but I find it rather inconvenient. It is especially inconvenient when the server barely works.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please help, why is this giving TLE in test 3 ? 115323338 , 1520F2 - Guess the K-th Zero (Hard version) Thanks ! UPD: I got it, since I used RUPQ Fenwick tree I forgot to update(r+1,-v) when I update(r,v)

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Not only the blog was almost-copy-pasted-part. But also the problems. Idk what did the testers do really test. And did not report for such well known problems.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I've just started getting the knack of codeforces. And I was able to solve A, B, C, D in this contest. But I was slow to think of the approaches and hence my rank is around 6k. Hopefully, I will get better at thinking fast about the solutions. If any tips that may help, please do tell me cause that would be great.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Practice

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What helps me to solve problems faster is to get better at math, especially competitive math, because the easier math problems have similar styles to the first few problems in a Div3 or Div2. Also, solving Codeforces Div3's and Atcoder abc's (Atcoder Beginner Contest) was one of the biggest factors in my speed. Now I just need to improve on actually getting the solutions...

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve F1?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Binary search the answer. Let's say you know sum(1,cur), then if cur-sum(1,cur) (which is the number of zeroes in that range) is greater than or equal to k then you know that the kth zero should be in the range [1;cur]. Else if n-sum(1,cur)<k then the kth zero is in the range ]cur;n]. So binary search over cur. 115289534 PS: sorry for not using LATEX

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

What is the intended solution for F2???

It seems that the author's solution is just do binary search every time and avoid query one segment twice.

But there's another very beautiful solution that divides $$$1$$$ to $$$n$$$ into blocks of $$$8$$$ and use data structures to maintain.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What is this technique of division to 8 blocks called?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It's not a common technique.

      That solution is only used for F2.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      It's kind of a sqrt decomposition, but it's better to use $$$8$$$ (or $$$16$$$, or $$$32$$$) instead of $$$\sqrt{n}$$$.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I maintained blocks of 32 and each time just iterated through each block until the total zeroes greater than k. Finally a binary search on the block

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That's the solution i mean.

      Iterate through each block is about $$$1e8$$$ so it can pass.

  • »
    »
    3 года назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Suppose there is a full binary tree with 18 layers, total nodes are (2^18 — 1) > n. We use this tree to do the binary search.

    So the problem is, the start node is root, find k end nodes, is it possible to cover more than (6 * 10^4) nodes?

    The optimal method is to make the k end nodes on the leaves. So the maximum covered nodes count is min(2^17, 10^4) + min(2^16, 10^4) + min(2^15, 10^4) + ... < 6 * 10^4. So the answer is no.

    We can do the binary search with simply cache to solve this problem.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me figure out whats wrong with my code for F1: https://codeforces.com/contest/1520/submission/115338765

It gives a weird error for test case 2

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    How to delete this comment.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      '0' initially stands for string it will be hidden for us so its length would be given, read the test case as 1(length of the string) 1 1.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Ok , now i get , it was not the input that i was getting from the grader , i was thinking that is the input that i was getting from the grader initially.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Could you explain again please? I didn't quite get it sorry

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I initially thought that , the input section of test case is same as the input that we will get from the interactor. I was saying now i understand where i was wrong.

            Now as for your initial question , intially you are quering with the indices as 1 and n/2 , but what happen when n was 1 , you will get 0 as a result of n/2 (integer division) but index zero is invalid in this question because indices start from 1.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Interactive problem in cf == Binary Search

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

HackForces (+51 successful hacks)

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone share a python solution that can pass problem G? All python solution are either failed or being hacked.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Is it only me or anyone else who found E way much tougher than number of submissions of it during contest?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It was a classical question I think. Most of the people have already done some similar kind of questions which involves taking median as a optimal strategy.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      bruh taking median is not optimal strategy i brute forced on all possible groups such that groups on the left are joined to this group and groups on the right are joined similarly and took minimum of all

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Yes your method is also correct. But taking median of indexes of all the sheep present initially to be the median of newly formed group works here. You can check my submission[submission:115335739]

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Its super easy dp. Sorry for my english

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

123 pretests for G, still got hacked :(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will the ratings be updated?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How does hacked works here? Can anybody explain. Thanks.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The standard tests are not always perfect and may miss some problems in the submitted solutions. Your solution for problem D has a bug, because arr[i]-i may be negative and so brr[arr[i]-i]++; results in accessing memory outside of the array bounds. Someone noticed this flaw and submitted a new testcase, which triggers this bug in your code.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The text for 1520F2 - Guess the K-th Zero (Hard version) is very misleading:

This is a hard version of the problem. The difference from the easy version is that in the hard version 1≤t≤min(n,104) and the total number of queries is limited to 6⋅104.

and adding this to the end of the problem:

To make the game more interesting, each guessed zero turns into one and the game continues on the changed array. More formally, if the position of the k-th zero was x, then after Polycarp guesses this position, the x-th element of the array will be replaced from 0 to 1.

Thanks for the problems.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My rating is only 386. Why it's unrated for me?? Tell me, please.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What makes you think it is unrated for you? You are on the leaderboard, it is rated for you. Dont Worry

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I think that round should've been extended, due to long queue a lot of people lost the time waiting the submission verdict.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain why this code is giving TLE on test 125?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem F1 it is said that n>=1 but the second test is 0 1 1.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

По-моему стоило продлить раунд, ведь люди потеряли много времени ожидая вердикта посылки

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

It's taking a long long time for system testing.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The simplest solution for problem C according to me is just print all odd numbers from 1 to n^2 and then print all even numbers. And for n = 2 it is not possible.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I submitted the solution of problem B during the contest and the verdict showed me accepted. Now in my submissions list it's showing that my solution is still in queue. How it is done please someone elaborate, I'm new here. This was my second time participating in any contest.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    System testing is carrying on now. It will execute all submissions again. You just have to wait until the system testing ended.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hello!

I've submitted 3 solutions for F2 with C++17(64) and C++14, but it kept on giving me "in queue", did I do anything wrong? I tried to submit another problem with C++17(64) and it worked correctly.

Here are my submittions: 115402170 115401934 115401509

thank you!

UPD: It's fixed now, thank you!

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is the contest unrated ?

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Why haven't the ratings been updated yet? It's not like the contest has been made unrated: there's no official announcement.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

when there will be a change in ratings ?

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

when will rating come ?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have a rating < 1600 but somehow i didn't get rated for this contest.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Felt unpleasant for G -_-#
I suppose it will let solutions with correct time complexity but huge constant pass ......
I need to use -Ofast to pass with time 2994ms ......

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is the round unrated?? If so then atleast give an announcement. People are waiting since yesterday

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

its not the good thing that now above 20 hr completed after round start but ratings are not yet given

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    You can use CF-Predictor. If you not cheated and the round is rated your rating change will be approximately the same as CF-Predictor says. Don't worry your rating will be up today.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

for unexpected queue i coludn't find my wrong for problem F1 otherwise I could solve it

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

System testing is happening again. Isn't it already happened 2-3 hours ago?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    I think it's happening again because all the hacks weren't processed by the time previous system testing happened.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

testforces

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If the round had to be unrated they should have announced during the contest ,so now its confusing seeing the contest in unrated section xD

»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

If the round had to be unrated they should have announced during the contest ,so now its confusing seeing the contest in unrated section xD

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Dream has reached the goal [The System Testing...Again...]

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Dream has reached the goal [The System Testing...Again...]

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Hopefully, they finish System Testing before tomorrow's round :(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why are sources evaluated that many times?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    The first system testing forgot to add hacking testcases,so they have to test it again...

»
3 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Again system testing!!! I am eagerly waiting for the rating update.

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Contest 1 days postponed:....:

Rating update : Hey I am following you contest

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

System tests have finished.....**FOR NOW**

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it rated?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ratings aren't coming because there are still some codes in the hacks section IN QUEUE

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what does this mean +40 in delta section it's showing for 2-3 minutes and then going off

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution for D failed system tests, I can't seem to find the bug in my code, can anyone help? I tried the same approach as in the editorial

115278462

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Hey MikeMirzayanov! Can you please check these 4 submissions? 115269387, 115321811 115286392, 115315037 I think it's obvious that these two contestants are cheating and the system did nothing about it!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How is the rating calculated?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me why I got a 'failed system test(tle)' using trivial BFS for problem G? And the same code got an AC just by using a different compiler. GNU C++11 998 ms AC: https://codeforces.com/contest/1520/submission/115447927 GNU C++17 (64) 3000ms FST: https://codeforces.com/contest/1520/submission/115322035

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just fell upon a question very similar to q4 of this contest-- https://codeforces.com/contest/1398/problem/C