By awoo, history, 10 months ago, translation, In English

Hello Codeforces!

On Nov/30/2020 17:35 (Moscow time) Educational Codeforces Round 99 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 223
2 jiangly 7 224
3 tute7627 6 190
4 nocriz 6 195
5 noimi 6 213

Congratulations to the best hackers:

Rank Competitor Hack Count
1 MarcosK 41:-6
2 dapingguo8 34:-2
3 jerdno 12:-4
4 ARTpositive 10:-1
5 halyavin 9:-1
357 successful hacks and 769 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A edickLPM 0:00
B SSRS_ 0:03
C corol 0:03
D pajenegod 0:08
E neal 0:29
F jiangly 0:55
G jiangly 1:17

UPD: Editorial is out

 
 
 
 
  • Vote: I like it
  • +146
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Hope this round will be good

»
10 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Another Educational Round. Hopefully I will do better like previous Educational Round. I think, The problem will be more interesting. Ops! I'm waiting for that.):

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

    I don't know why people giving me down vote! I just expressed my feelings! I really shocked about people's attitude. But I have done well today that is my satisfaction.

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it +22 Vote: I do not like it

      People downvote your comment probably because they think this types of comments just fill the comment section and then one need more time to find useful content. No one wants to read 100 comment of people expressing their feelings!

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

        Thank you for knowing me. I didn't guess it before. Next time i wll keep it in my mind.

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

[Deleted]

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

Super Excited !!

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

In awe of the mentions UwU

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

This is my chance to go up to master!!!

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

People reading this comment, hope you have a good contest. All the best!!

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

May i become specialist this time !!

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

This may be my last contest before my college final exam. After that I will open my brand new advanced mathematics book and my linear algebra book. Oh my god, brand new(╥﹏╥). I hope i can get good results all of them.

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

    Maybe my last contest too before my college final exam. After that I will open the PDF notes send by the topper and hope I can get good results.

»
10 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Maybe the last round before senior high school...
It's time to say goodbye to you now guys. Hope we'll all do our best in this round. :)

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

    Don't go :(

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

      I don't want to do that either but I have to :(
      After all, high school entrance examination is always more inportant than OI :(

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

    However, I come back now... (Eason_AC is my another account)
    That means I can enjoy the CF rounds again guys :)

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

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

the comment section is shit

»
10 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Score distribution awoo ?

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

    There is no score in Educational Codeforces Round

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

      Why? Also what is differnece between educational div. 2 and other div. 2.

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

        In edu each problem scores 1 point, other div2 have different points per problem.

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

In the hope that I don't mess this round by silly and not required lengthy implementations.

»
10 months ago, # |
  Vote: I like it -16 Vote: I do not like it

I have end semester exam tomorrow. Should I compete this round?

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

    What? So early in India? In China usually in January or February...
    Anyway, you'd better take a good rest as the end semester exam is more important than a CF round :)

»
10 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I just pray and hope that it wouldn't be another Mathforces round.

»
10 months ago, # |
  Vote: I like it -38 Vote: I do not like it

aaaja mahi aaja mahi aa soniya ve aake aaj mere gale lag jaaa tu hoye

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

I don't understand why I perform bad in educational rounds, despite the fact that standard problems are asked unlike Div 2 contests. Anyone else with same problems?

P.S: This is an alt account.

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

    yes but if u sing arijit singh songs while solving questions then u will get AIR 1

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

When will be shown the difficulties of tasks from Codeforces Round #685 ? It's been more than a week ago!

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

7 min left be ready i hope u solve many problems good luck :D

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

My opportunity for Expert

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

    same i have opportunity for 1000 points

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

I'm gonna participate so more chance to gain lost rating on sunday

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

Congratulations to the 100000000th submission!

»
10 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Man, is this educational round a joke?

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

Most uninteresting problem set ever

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

    nvm

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

      Also, example- Education round 99 problem C

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

        Yes, i will also agree that 'C' is uninteresting, but this guy is shitposting before solving them which is not fair. The only problem i found interesting was 'B'.

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

          can you share your solution please

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

            keep moving greedily and once you cross you destination you will come to know what step you should not have taken greedily that will be K=(finalDest-x)th step.

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

              can you explain the case for 7

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

                sorry k is actually (finalDest-x-1)th step, for 7 finalDest will be 10, so difference=3 so inspite of taking second step greedily, take a step back and again proceed greedily

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

                Keep jumping greedily till you reach a point >= x. If your current_pos-x is 0, then obviously answer is number of jumps. Now if its not, then there are two cases

                1. current_pos-x == 1
                In this case, you always need to jump back a step. So, answer is jumps + 1.
                

                The second case current_pos-x > 1 Since it is greater than 1, there is always a jump in range [1, jump], that you can decide to not perform and jump back. Example

                x = 7
                1 3 6 10
                lets stop jumping since 10>=7
                

                cur_pos = 10, jumps = 4 here, difference is 3 (10-7), so there is always a previous step,in which you decide to not jump forward and jump back. In this case, if you dont do the second jump (+2) and jump back (-1), you will end up at 7 in 4 jumps.

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

                  this is hard for a Div2 B

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

                  How would you prove the last section of your comment? Why in case we overjumped our x by 1, then we make a jump back, but when we overjumped by n greater than 1, there is ALWAYS a jump in range [1, jump] that i wanna not perform and jump back? Why if I overjumped by n greater than 1, i can't just jump back n times?

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

                  This is because the kth jump goes over k positions, and n-x is garanteed to be smaller than the last jump.

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

                  Ok, I understand that the distance of overjump is less than kth jump, but i don't understand why i shall do a jump back(and what's the count of them) somewhere in my jump path, instead of inserting my backjumps in the end of jump sequance?

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

                  See it that way: If you do a step back in ith step instead of jumping, then the contribution of this step back is i+1 positions to the left. (Because you did not jumped i and steped one back).

                  So if you are in the end y position to much on the right, then you kind of revert one jump. And because it should cause y positions, you choose the y-1 -th one. This works as long as y>1. If y==1 then there is no jump you could revert.

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

                  Because you want to minimize the number of steps. Changing one of the already taken jumps to -1 will cost nothing. But jumping back in the end will cost 1 move for jump.

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

                  Wow, great! As soon as I read your comment i firstly started to think that i misunderstood the task, then i read again the task, returned to this post and started to write that you're wrong, and in this moment i finally understood why it works. Thanx!

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

                  Consider 4 jumps [1, 2, 3, 4]. Here, the sum is 10. Now try replacing any of these by -1 and check what the sum will be. You will get all sums except 9. So you always a need an extra jump if difference is 1.

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

                  So well explained!

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

      Kid looks like its your first time solving D. Doesn't mean its an interesting problemset (atleast for me). Besides I left the contest long ago, and I dont judge someone's opinion based on their rating or whether they have solved B or not in a contest I like problems which are ds oriented not based on Math

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

        Looks like you got a burn?

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

          Yes burnt just like your rating graph

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

            Haha your Humour is great! Btw nice talking to you

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

            You just literally said you dont judge anyone based on their rating and then went on to judge him on his rating graph. Hypocrite much

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

              lol what I said I don't judge someone's opinion/likeness towards a problemset on basis of his rating or whether he solved B or not lol

              He was mocking me for my comments I mocked him for his graph.

              These are unrelated. You need some humour man.

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

Congratulations to ub33 for the 1e8-th submission!

»
10 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Is C's statement an english test? I can't understand it.

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

    C's statement is definitely hard to understand at first, need to google "ping-pong" after reading the statement

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

      hm. later i solved it by guessing output from samples.

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

Either I will live or geometry in this world !!

»
10 months ago, # |
  Vote: I like it -36 Vote: I do not like it

It was a good round!! Really enjoyed the problemset which I could do :)

»
10 months ago, # |
  Vote: I like it -37 Vote: I do not like it

How to solve E ???

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

ez game pls dont hack me pitch

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

Use me as dislike button if you also didn't like this contest.

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

Solved C in 1 minute after the announcement ;)

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

It's the second time in a row that in a Educational Round problem C is easier then problem B what is this :(.

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

    ObservationForces

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

    I think C easier then A. Because during contest I solved A help with pretests but C was really apparent but for understand what it says on C i need to read multiple times maybe this becomes C harder than A.

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

    So it's a good reason to start solving C firstly the next time. I think cfpredictor is a suitable work for you :)

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

How to solve E?!

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

Sounds stupid.. But someone help me with B

  • »
    »
    10 months ago, # ^ |
      Vote: I like it -22 Vote: I do not like it
                    ll n;
       		cin>>n;
       		ll i;
       		for(i=1;i<=n;i++){
       			if((i*(i+1))/2>=n) break;
       		}
       		ll ans=(i*(i+1))/2;
       		if(n==1) cout<<1<<endl;
       		else if(n==2) cout<<3<<endl;
       		else if((i*(i+1))/2==n) cout<<i<<endl;
       		else if((ans-n)>=2) cout<<i<<endl;
       		else cout<<i+1<<endl;
    
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After you draw the steps (don't come back initially) you will realize that you can come back by not making some pth move in front, but by just making it backwards. suppose you are at point y such that y>x, you need to check if there exists some p, such that (p+1) = (y-x). this accounts for not making the pth move in front, i dont have proof, but since p can take all natural numbers, it's always possible.
    and yeas if(y-x)=1 then add one.

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

      I kind of have a proof so basically, y — x will always be less than or equal x, so let y-x be p so p can be written as 1 and p-1 which are steps which we have already taken 1 + 2 + 3 .... to remove the extra p we can remove 1 and p — 1 because they both sum up to p too, we can replace the p-1 step by taking -1 jump in p-1th step, and this way we can always remove any extra step taken. Also when we have y-x == 1 we cannot write it as 1 + some number, to remove it we need -1 so therefore an extra step is taken.

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

    U can go about like this--- u can see that x is less then 1e6 right and sum of first n natural numbers is n*(n+1)/2 which is approx the square of x so first u can create an array where u put the sun of first n natural numbers value of index i(1 based) will be sum of first i natural number now u can do a lower bound to check the value of index i. Now we are not done yet,let the array name be res now u need res[index] — x backward right so as u have already moved K steps what u can do is reduce j+1 for all j belongs to [1,index] i.e j dont not add j in the jth step but instead subtract 1 and thats how u can greedly approch at an optimal solution

    Solution for B : https://ideone.com/HZvp8J

    Now i having trouble with problem C can someone help me understand it. For problem D can somewhere tell where i made a mistake would be grateful. D wrong solution dp approach link : https://ideone.com/i3lWQr

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

Solved Div.2 D for the first time.

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

A being as expected,B being a bit unexpected then comes the one liner C......XD crazy contest

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

How to solve c (please tell along with proof) ?

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

    print(x-1,y)

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

    Ans is always (x-1,y), since the 2nd player wants to maximize he always gets y points by loosing the first x-1 games and now player 1 has only 1 stamina and uses it to serve and player 2 reflects it to get his first point and wins the rest y-1 points after that.

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

      how you can say that ? he also has to minimizes the apponent chance of winning can u please tell the proof why u r doing this little more ??

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

        but first priority is to maximize his own points

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

          got it man , thanks can u tell how to solve B what was the intend/intuition behind the problem

          Thanks in advance ?

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

        The order is that in first place they want to win as much as possible. Only if they cannot win any more they will care for the other ones points.

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

          How the above strategy ensures that bob cannot play in such a way that Alice wins less than x-1 times and he wins y times ?

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

            If you are not serving, its always optimal to lose the play and not lose stamina. This way you make the opponent lose stamina on the next try, since they compulsarily have to serve.

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

          what if alice doesn't return in the 1st move?

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

            She has to. This is mentioned in the problem statement : "On the contrary, when the server commences a play, they have to hit the ball, if they have some stamina left."

»
10 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

wasted 35 min on b then did c in 1 min then went to b for another 35 min to actually solve it. C must have been in place of A. C<=A<B<D

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

    C easier than A. Seriously?

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

      ok ,say C=A in difficulty,because, Ans is always (x-1,y), since the 2nd player wants to maximize he always gets y points by loosing the first x-1 games and now player 1 has only 1 stamina and uses it to serve and player 2 reflects it to get his first point and wins the rest y-1 points after that.

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

        I get C is easy but what did you find tough in A that you placed it after C? In A you don't even have to think anything.

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

        in A ans is always n.size(), where n is the string in input. So A easier than C.

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

      Yes.

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

I miss those times when Educational used to be great!

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

Thank you for the new mathforces round !

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

Is it just me or the game thoery problems are a bit tough to understand?

»
10 months ago, # |
Rev. 2   Vote: I like it +57 Vote: I do not like it

Strong dislike for C, it is completly based on observation and hence has no educational worth at all. That might be a nice problem, but simply misplaced in educational contest.

It is basically no programming problem.

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

    Exactly. A,B,C were more about observation than implementation! -_-

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

    The problem wasn't even interesting. Just trying to come up with possible ways of playing and hoping one of them is optimal.

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

    Today's A,B,C were more like Atcoder's ABC contest A,B,C

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

    Yes, C was very ambiguous for me

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

    I wouldn't say that it was a complete observation-based problem. I think the most obvious thought process was a greedy one : Prioritize wins which you can do by not interfering with the opponent's moves. The next part of minimizing the opponent's wins was trivial after getting the main idea. I would have liked it if this problem was B instead of C though.

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

    I won't say C was bad even though i was not able to solve it during contest . I didn't expected that observation will be so simple and was always thinking in complicated way .

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

    if the intended solution was minimax dp, It can be an educational problem.

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

The best boring ping pong in C.

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

I don't like this round. Learned nothing from ABC.

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

D was pretty easy,such a shame that I and made a terrible mistake kept failing to solve it.

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

How to deal with D?

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

How to solve B ?

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

    It was observation that you calculate $$$s = 1+2+3\, ...\, + k\ge n$$$. Now see that if $$$s = n+1$$$ then answer is $$$k+1$$$, otherwise it is $$$k$$$.

    This is because if you overstep by some amount $$$o > 1$$$ and also we have $$$o < k$$$ so we can do the $$$-1$$$ step on $$$(o-1)^{th}$$$ move and $$$+j$$$ step on other $$$j^{th}$$$ moves and so effectively we have reduced the sum to $$$n$$$, so answer is $$$k$$$.

    But if $$$o$$$ is $$$1$$$ then you must step back on $$$(k+1)^{th}$$$ move, so giving total $$$k+1$$$.

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

      Can you explain me that how I reach to 7 in problem B

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

        You can follow the sequence $$$0, 1, 0, 3, 7$$$ (step back on the second step).

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

.

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

How to solve B?

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

I might get a lot of downvotes here, but I felt that $$$C$$$ was a pathetic problem, with no learning at all.

»
10 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

What was the intended solution for problem D?? Was it DP or greedy??

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

    greedy

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

      I did dp, I guess there are more solutions.

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

        can you explain the dp solution plzzz

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

          dp[index][valueofx][0/1] So you can see that you have n+1 elements in total, let's rename them 1 -> k (where k is the number of distinct elements) The solution will have n elements from your n + 1 elements. For example, if your normalized values are 1, 2, 3, 4, 4 and x = 5 (in total 6 elements), you can see that the solutions can be something like 1, 2, 3, 4, 4 or 1, 2, 4, 4, 5 etc. (you pick 5 elements). index — means the element you are at valueofx — the current value of x after you do the operations on the first "index" elements 0 / 1 — you haven't skipped / have skipped an element (which means if you are still taking the smaller n elements, or have already skipped 1, so your solution will end with the n+1th) dp holds the answer obv. Try solving yourself from here on, since it is not hard.

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

            i got it thanks

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

          The states are (current position i, Max element from [0,i), current x).

          Transitions are simple, you either make the current element x or you don't. My submission

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

            This is a way easier solution, but performs worse. But for this problem, n^3 is fine as well

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

              Yup, I noticed the memory limit was 512 MB which was unusual from a general 256MB. So I decided to go with this since its pretty easy to implement

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

                If it would have been 256MB, you could have only kept the last 2 lines of dp, because you only need them. And had like dp[2][500][500]

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

                  that would work in iterative solution right? because in recursive dp, we can't remove the state $$$pos$$$ as far as i can think.

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

                  Isn't the current state unique for (i,x)? Submission

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    I used a greedy approach: First check whether the original array is already sorted or not. If it is sorted, print 0. Otherwise traverse the original array. Swap the value at current index with 'x' if it's greater than x and increment your answer by 1. At every step of the traversal check whether the Array has become sorted or not. The low constraints allows this. If it has become sorted print your answer. At the end of the traversal if the array is not sorted print -1.

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    It was a greedy solution. I solved it this way:

    • Notice that $$$x$$$ is monotonically strictly increasing.
    • If at any point, for any $$$i$$$ starting from $$$1$$$ to $$$n$$$, $$$a_{i \dots n}$$$ is sorted, break out.
    • If for any $$$i$$$, $$$a_i > x$$$, do the operation. As an operation can only lower down the value of an element, so it is optimal to lower down the values when possible starting from the left.
    • Finally, at the end check if $$$a$$$ is sorted, if it is, then print the moves you took, else print $$$-1$$$.

    Update: Cleaner and faster code.

    C++ Code: 100058194

    Time Complexity: $$$O(n)$$$
    Auxiliary Space: $$$O(1)$$$

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

Problem C was really ambiguous. Strongly dislike it.What was the point of it?

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

Maybe my complexity analysis was wrong. But I think I probably submitted an O(n^3) solution to the problem D where the sum of n over all test cases was <=500. Am I missing something in my complexity analysis? I would be glad if someone helped out.

My submission: 100048016

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

Got VERY stuck on B ;(.

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

Interesting problem С, liked it. But, in my opinion, problem B is more difficult than problem C :(

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

neal's stream is running now, feel free to join :)

https://codeforces.com/stream/71

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

I can't believe D is just mostly implementing what they given, I overthought that so hard D:

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

Someone, please help me with the logic of problem D. Thank You in advance!!

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

    Hey, I iterated on the input array and every time check whether input array is equal to sorted input array if that's the case print answer and return else if the current element is greater than X then swap it. Here is the implementation of the same.

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

what is hacking here? How can we hack? Can we hack anyone? please enlighten me..:)

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

how to solve b

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

    Find the cnt where cnt*(cnt+1)/2 is just greater than x Then find by how much it is greater than x,let it be y=(cnt*(cnt+1)/2)-x; Now just we have to remove the step y which can be done without any extra step. if y>1 so ans = cnt and if y==1 ans=cnt+1

    Let's say x=7.So cnt=4; And the guy moved 1+2+3+4 steps. Then his final position is at step 10; y=(1+2+3+4)-7=3 Only if he could move 3 steps behind then the problem will be sorted. So we just need to remove the step size 3. So lets do Step 1: +1 position =1 Step 2: -1 position =0 Step 3: +3 position =3 step 4: +4 position =7

    So we get the minimum number of steps as cnt=4

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

    For B, let's use only +i as long as sum < X.

    +1  +2  +3  +4  ...  + K  =  S  (>=X)
    
    If we switch a "+i" to "-1", then S updates to S-i-1
    That is great, because for i = 1, 2, 3.. it is -2, -3, -4 ... -K on S with no more jumps (result = K), and we could reach any S, S-2, S-3, ... except S-1, in which case we need an additional "-1" jump (result = K + 1).
    
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How the answer of B for n=12 is 5 ?

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

How to solve B?It took me an hour and a half to solve problem B,but I did not succeed in solving。

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

    Find the cnt where cnt*(cnt+1)/2 is just greater than x Then find by how much it is greater than x,let it be y=(cnt*(cnt+1)/2)-x; Now just we have to remove the step y which can be done without any extra step. if y>1 so ans = cnt and if y==1 ans=cnt+1

    Let's say x=7.So cnt=4; And the guy moved 1+2+3+4 steps. Then his final position is at step 10; y=(1+2+3+4)-7=3 Only if he could move 3 steps behind then the problem will be sorted. So we just need to remove the step size 3. So lets do Step 1: +1 position =1 Step 2: -1 position =0 Step 3: +3 position =3 step 4: +4 position =7

    So we get the minimum number of steps as cnt=4

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

MarcosK Make a nice hacks for E

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

    Doesn't it mean that someone did bad tests?

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

      They don't need to have perfect test btw you can resubmit if you think your solution bad while accepted this means no one says pretest are perfect

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

        What? What is your point? Do you wanna say that it's normal that in all tests $$$t \leqslant 10^3$$$ while $$$t \leqslant 10^4$$$ is in statement?

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

This was my first contest ....can someone please send me solution for strange functions A question ? Pls it will be of great help ...thanks

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

    You simply have to print the length of the input for this question

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

    You just have to print the length of the input. while(t--) { string n; cin>>n; cout<<n.length()<<"\n"; }

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

    Its just the number of digits in the number.

    Reason: Any number without starting or ending 0s will give g(x)=1. We get a different value for g(x) only when a number contains 0s at the end(i.e. multiples of 10).

    EG: for if n=124, take 100. We get g(x)=100 as it is (100/1). We get g(x)=10 from x=40. So the answer is 3(1,10,100)

    The various values of g(x) possible are 1,10,100,1000,etc.

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

The constraint of $$$E$$$ is $$$1\le t \le 10^4$$$,but the maximal $$$t$$$ for the tests are $$$1000$$$ only...

That's why there can be a lot of hacks in $$$E$$$...

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

    Out of curiosity, was the limit for $$$t$$$ originally $$$10^3$$$ and not $$$10^4$$$ awoo? I had a solution without ternary/binary search in mind, but I saw my solution passed in only 483 ms, so I assumed that it most likely wouldn't be hacked :P

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

Is it codeforces or ObservationForces?

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

This was a really nice round, but I have to complain about problem E. I hacked more than 40 submissions (including mine), just because the complexity is $$$O(log(10^9) * 4!)$$$, and all of them exceeded time limit because of having 10^4 subtests. I don't get the decision of the setter about it.

Besides that, thank you for the round, i loved the problems!

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

    Theoretical computer scientist: That is O(1) XD

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

    My solution is $$$O(4!)$$$ if we allow such notation. Initially, I didn't intend to make limits so tight and wanted to allow sub-optimal solutions but, I'm sorry, I messed up with tests.

    P.S.: it's a little strange that something that looks like $$$t \cdot \log^2$$$ doesn't pass with $$$t \le 10^4$$$.

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

    Wait, that sounds weird. 2 sec TL, log(10^9) is ~30, 4! is 24, then for all tests we have 7200000 (7M) total. How that could be TL?

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

      In most of the codes, the constant factor is not small. For example, some codes perform more than one binary search. My hacking method was:

      Open submission. Look for a binary/ternary search. If there is one, send a hacking attempt with $$$t=10^4$$$. Successful hacking attempt.

      Of course it didn't work in 100% of the submissions, but I did more than 40 hacks in that way :P

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

        That’s all pretty cool, but math is math: constant factor should be very big to jump from 7M to TL. Hack is hack, good for you, just very weird.

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

problem C was much much easier than b.

»
10 months ago, # |
  Vote: I like it -8 Vote: I do not like it

any tutorial for b please

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

A~D: No programming, just observation and math...

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

    well , I solved D with DP , is there another solution?

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

      We will iterate over the given array a from beginning. If a[i] <= x, we can't change the value. If a[i] > x and a[i] should be changed to sort the whole array, we should swap a[i] and x — if we don't, it cannot be corrected later. After each swap, I checked the array is sorted. If then I escaped the loop and printed # of swaps.

      If the array is not sorted after all swap, print -1. We can solve the problem by this greedy approach.

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

        That's problem B, not problem D.

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

          Oh, it's my mistake. I will edit the comment.

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

No offense to the writers but I don't really think this contest is educational.

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

Adhoc-Forces crossed 100 million+ submissions. wow!

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

How to solve Problem E?

  • »
    »
    10 months ago, # ^ |
    Rev. 3   Vote: I like it +25 Vote: I do not like it

    Essentially you are compressing the x and y co-ordinates each to two distinct values, and the problem has many similarities to making all elements of an array equal. In the array problem, you compress all elements to be equal to the middle value, or in the case of an even-length array, one of the middle values.

    In this problem, we want to compress the co-ordinates such that x and y deltas are minimal. If we sort our starting X co-ordinates (X1,X2,X3,X4) and starting Y co-ordinates (Y1,Y2,Y3,Y4), ideally we will compress them such that all x co-ordinates are between X2 and X3 inclusive, and all Y co-ordinates will be between Y2 and Y3 inclusive. The optimal length of the square, L, will be the max(Y3-Y2,X3-X2), since we don't want to compress the square more than necessary.

    Suppose we cannot fit the whole square inside the bounding box X2 to X3 and Y2 to Y3. Then we want as much of the square as possible to be inside that bounding box, and as much of the rest of the square to be inside the bigger bounding box X1 to X4, Y1 to Y4. It can be seen quite easily by drawing an example that any shift outside of these bounding boxes is sub-optimal.

    So we can say the bottom left corner of our square is at (min(X2,X4-L),min(Y2,Y4-L)). [Note the we equivalently could have positioned the top right corner at (max(X3,X1+L),max(Y3,Y1+L))].

    Therefore we have the four co-ordinates of the optimal square. From there we can try all 24 permutations of starting points to corners, and find the optimal one. There may be a neater way to do this final step, but I brute forced it as 24 is not many.

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

      I dont get it how here the connection between x and y is done. Since it is a square x and y size of resulting rect must be same. But the logic separates the x from the y coordinates :/

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

        The logic combines the x and y results, though.

        • Length (both horizontally and vertically) = max(Y3-Y2,X3-X2), so the length is determined by the x and y co-ordinates

        • Bottom left corner of square is at (min(X2,X4-L),min(Y2,Y4-L)), so the position of the square is also determined by the x and y co-ordinates

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

      This is my approach for E after taking some ideas from jimm89 :

      int x[4], y[4], old_x[4], old_y[4];
          for(int i = 0; i<4; i++){
              cin>>x[i]>>y[i];
              old_x[i] = x[i];
              old_y[i] = y[i];
          }
          sort(x, x + 4);
          sort(y, y + 4);
          int b_a_u = x[3] - x[0]; // The upper limit for difference of x2 and x1 where x1 and x2 are defined below
          int b_a_l = x[2] - x[1];
          int d_c_u = y[3] - y[0];
          int d_c_l = y[2] - y[1];
          int side = min(b_a_u, d_c_u); 
          int x1 = max(x[0], x[2] - side);
          int x2 = x1 + side;
          int y1 = max(y[0], y[2] - side);
          int y2 = y1 + side;
          cout<<findmin(old_x, old_y, x1, x2, y1, y2)<<"\n";

      Here, x1, x2, y1, y2 are choices for the lines that define the square (4 lines x = x1, x= x2, y = y1, y = y2) and findmin() checks the minimal distance to corners in all permutations. https://codeforces.com/contest/1455/submission/100091962

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

        Looks like a nice variant on the same ideas. Nicely done.

        My in-contest submission was a little messy as I was very short on time, and a little panicked. Afterwards I tidied it up.

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

    Here is a case-work based solution (no binary search) to problem E: https://codeforces.com/contest/1455/submission/100073456.

    Edit: I'm not sure if this solution is always correct.

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

A<C<B

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

Guys look at the topic(contest) rating, going to zero XD

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

How to solve E?

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

Me after reading the solution of problem C

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

Coded an n^3 solution for D using DP, is it hackable? 100060462

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

    Problem statement guarantees:

    The sum of values of n over all test cases in the input does not exceed 500.

    So (sum of n) * 500^2 operations should be fine.

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

    no problem with the given constraints n^3 solution passes

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

Is the round difficulty below average ?

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

G was nice, thanks authors! Sadly, I needed 20 more minutes to solve it :)

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

is their hack points in this contest??

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

Solving A-D feels like guess some conclusion and just try it...Even don't need to think seriously. Am I too impulsive?

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

    I own none of these problems' ideas but I personally find the observation problems the hardest of them all. They tend to make me think a lot more than the standard-ish ones and usually way more than it takes people of my rating :( The fact that you don't need to think seriously just shows that you have better intuition I guess. So you can enjoy your "free" rating and the guys like me can enjoy practicing more in this kind of problems :P

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

      I also got immediate ideas for A, C, and D but didn't believe them in the first place so spent a lot of time proving them :(

»
10 months ago, # |
  Vote: I like it +66 Vote: I do not like it
»
10 months ago, # |
Rev. 2   Vote: I like it -45 Vote: I do not like it

Hello nerds,

I think contests of codeforces also drowning into the scam of plagiarism and it can be seen that moss checker isn't giving justice to the genuine programmers who really work hard to get better in every other contest and they don't get their deserving ranks because of some people take this place as fun and plagiarise easily get the good ranks this gives a lots of demotivation to genuine guys.

So i request codeforces community(BledDest ,awoo,MikeMirzayanov,Roms,adedalic,vovuh,Neon) to check these submission neutrally and if found guilty required action should be taken. https://codeforces.com/contest/1455/submission/100047211 https://codeforces.com/contest/1455/submission/100051933

Thank YOU

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

I can't understand why so many people downvote a contest. Just for the problems? ok but also the writers and the testers make some effort to gives us these contests. And about the problem : Easy A like always , a easy math problem for B , C an observation one and D greedy (I Didn't understand that N <= 500 but that is not an issue). If A-D were easy why just 300 make at least 5 problems? You can say , was a huge gap between D and E and I agree , but that s not a reason to downvote a contest. I enjoy every contest (and I would like to see more DP and graph problems in div2 and Educational contests)

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

    problem D I solved it DP lol. I didn't even think. I just wrote the code and AC that is why $$$N<=500$$$ so dumb people like me could write a standard DP solution :/

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it +9 Vote: I do not like it

      N=500 you can get accepted with O(N^3) if I am not mistaken. I think N=5000 was better but that's the most irrelevant thing in this contest

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

        i guess it was intended that authors wanted N^3 dp solution to pass, that's why n=500, just doubling N would have cut dp solution.

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

            i am wondering that why it doesn't depend on $$$prev$$$ state in dp. can you please elaborate on this?

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

              I'm very bad at proof and explanation but here's a try.

              I thought of it this way, dp(i,x) is the min number of steps needed to sort [0,i]. Obviously, the configuration we are considering might be invalid so i return inf in that case.

              I did not consider prev, because I'm swapping x and a[i] in every move. so if x=a[y] for any y at idx i, I can be sure that I've sorted from [0,y] and infact used moves from [0,y]. From [y+1,i] I have not used the moves. This is enough to uniquely define the state of the array.

              I might be wrong, if so please correct me.

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

        I coded DP solution with O(N*X). Even if N=5000 then also it will pass. So I chose DP over greedy as I will learn something.

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

      Wish I was dumb like you!

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

    People didn't like problems so they downvote, what's wrong with that? — Errichto
    source

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

Good contest. Finally I can be expert

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

hi all, in problem B,if we consider only the first operation jumping to y+k, then we can do the following jumps,

on 1st jump 0 to 1

on 2nd jump 1 to 3

on 3rd jump 3 to 6

on 4th jump 6 to 10

so we get the following series of 1 3 6 10 15....

now what i did is stored this series upto the given constraint of x which is 10^6 in a vector a. Then if x is just greater than or equal to any a[i] I calculate ans=i+1+a[i]-x where i+1 is the jumps to reach a[i] and a[i]-x is to move back to x by using the second operation y-1;

now after this I noticed this that for x=4 following is the optimal operation

1st jump 0 to -1

2nd jump -1 to 1

3rd jump 1 to 4

then i noticed if we do this kind of operation for any x(except 1 2 3) the total number of jumps will be x-1;

so at last i took min(ans,n-1).

is my approach wrong?pls help here is my code

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

    You seem to have made a few false assumptions, just trying to get your formula to match the example solution.

    The main problems are that the min with n - 1 doesn't really play a role for larger n, as the answer starts to increase much slower than $$$n$$$. The other one is that the answer will be the same for multiple consecutive $$$n$$$, where a[i] stays the same, but your formula does not account for that.

    Thus, as the second test shows, for example with input $$$7$$$, a[i] is $$$10$$$, i is $$$3$$$, and it is possible to reach $$$7$$$ with the sequence $$$0, 1, 0, 3, 7$$$ ($$$4$$$ jumps), but your formula gives $$$3 + 1 + 10 - 7 = 7$$$, and with the minimum $$$min(7 - 1, 7) = 6$$$.

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

Problem G is really nice.Thanks!

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

    What should be the problem rating for E,F,G in the contest according to you?

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

      Sorry ,I haven't read E&F.For me G is about 2600.

»
10 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

I can't understand why people are writing wrong code and then hacking theirselves like this guy — You_Will_Be_Hacked

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

    They are most likely coping someone else's code and testing their hacks on the dummy account.

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

Observed Cth problem solution printf(x-1,y) just in 1 minute but thought how can it's solution be so dumb! And then wasted 30 min and submitted wrong and most dumbest solution ever. RIP my rating.

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

I personally believe that if problem C was given as Problem A I would have come up with a solution much faster, I just thought since it was a C problem, it can't be so simple!

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

Can we apply BFS in B problem??

»
10 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Solved D with DP and used only two states — [index][x]. I thought that x and prev are inter-related. I also tried [index][prev] but it was wrong. Is it wrong and just a coincidence with test cases? https://codeforces.com/contest/1455/submission/100080134

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

    (i,x,prev)
    (i,x) They are inter-related according to me. How is it wrong?

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

      Can you please explain why both these states are inter related? What redundant information are we providing in 3D DP?

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

        Does this help?

        In other words, if prev!=v[i-1] then it's obvious that it has been swapped till i-1. you will see that the prev does not matter when you have fixed x because it's v[i-1] if not swapped, and previous x if swapped.

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

          Thanks for your explanation. I think I got the gist.

          For any state to be uniquely defined. You need 3 information here: - current index - x on the current index - Maximum value till now on [0, curr_index-1]

          Since you only proceed further when you are convinced that [0,curr_index-1] is sorted, you can derive the 3rd information from the first 2.

          That is, it will always be arr[curr_index-1] (considering you have made swaps in the array wherever needed).

          Thus the 3rd condition is redundant and can be removed only because of the virtue of having a sorted array.

          I hope I got it right?

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

            Yeah that's pretty much what I meant.

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

    Oh, that's a nice idea to remove the index from the state as it is not providing us any useful information, just telling on which step we are. So, it makes sense to just focus just on values at step and step — 1

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

anything on when ratings will be displayed?

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

It has been 12 hours since the contest ended. My rating didnt change.

Wasn't this contest rated?

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

    Div 3 and Educational round gives 12 hours for open hacking. After that, system testing starts and rejudge all the solutions. Then rating gets updated. System testing isn’t started yet.

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

I'm curious why Educational Round doesn't system test instantly after finishing the hacking phase.

»
10 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Ratings will be displayed as soon as system testing complete.

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

Next time add/change notes or info in the main problem page too. In problem C, changes didn't show up after refreshing the page.

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

    There was no change in problem statement. Announcement for the explanation and that was writing on problem statement.

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

      Well, it was an explanation and it should have been included in the lower section.

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

where is the editorial?

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

Where are the tutorials?

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

Can we solve 2nd using dp?

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

Can anyone tell me why am i wrong ? :'< https://codeforces.com/contest/1455/submission/100029658

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

Is it rating???

»
10 months ago, # |
  Vote: I like it -50 Vote: I do not like it

Below average problem set.

Cf standard going downward day by day

  • »
    »