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 |

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

Hope this round will be good

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

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.

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!

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

[Deleted]

[Deleted]

Super Excited !!

In awe of the mentions UwU

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

Good luck

my chance for expert !

my chance to lose expert

may be next time

I entered the contest with my smurf. Delta = -134. I went back to blue

nvm round #688 awaits, btw smurf means alt account right ?

yes

My chance for pupil!

Hoping I get my blue back in this contest

a bad contest for you :(.. dont worry next one may make you blue.....i am sure of it.keep up hopes

Thank you.. After losing 250 rating in 2 days I seriously needed this :)

I hope I become an expert after this :)

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

May i become specialist this time !!

all the best !!

Wish me luck too

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.

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.

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

Don't go :(

I don't want to do that either but I have to :(

After all, high school entrance examination is always more inportant than OI :(

However, I come back now... (Eason_AC is my another account)

That means I can enjoy the CF rounds again guys :)

the comment section is shit

And you're not Errichto

Score distributionawoo ?There is no score in Educational Codeforces Round

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

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

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

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

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

no its happening in december as usual

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

pikMike loves Math problems, so who knows!!!

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

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.

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

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

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

My opportunity for Expert

same i have opportunity for 1000 points

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

i hope that :D

Congratulations to the 100000000th submission!

Congrats ub33 :p

Man, is this educational round a joke?

Most uninteresting problem set ever

nvm

Also, example- Education round 99 problem C

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'.

can you share your solution please

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.

can you explain the case for 7

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

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

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

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.

this is hard for a Div2 B

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?

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

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?

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.

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.

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!

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.

So well explained!

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

Looks like you got a burn?

Yes burnt just like your rating graph

Haha your Humour is great! Btw nice talking to you

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

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.

Congratulations to ub33 for the 1e8-th submission!

yayy!! congrats ub33

meow

CONGRATULATIONS !!!!!!

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

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

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

Either I will live or geometry in this world !!

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

How to solve E ???ez game pls dont hack me pitch

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

Solved C in 1 minute after the announcement ;)

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

ObservationForces

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.

why didnt I look at C? I tried A, B and D

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

How to solve E?!

Sounds stupid.. But someone help me with B

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.

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.

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

`Solved Div.2 D`

for the first time.what was the fucking test 2 in C

Don't know.

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

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

print(x-1,y)

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.

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

but first priority is to maximize his own points

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

Thanks in advance ?

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.

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 ?

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.

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

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."

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

C easier than A. Seriously?

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.

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.

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

similarly in c, answer is always (x-1,y) . :D

Yes.

I miss those times when Educational used to be great!

lower end question may be interesting so try them !!!

Thank you for the new mathforces round !

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

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.

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

And D was just a blunt implementation of the statement.

How to solve D using DP?

https://codeforces.com/blog/entry/85116?#comment-727912

This was more disappointing than ABC combined. ;_;

Was it intentional to give an implementation problem with low constraints to confuse low-confidence participants like me?

I messed up because of the same reason. I think the intention was to let n^3 solutions pass too. if constraints were high there would've been less confusion.

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

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

Well, I did work like an hour on C and needed 7 submissions ;)

A,B were not as simple as A,B of atcoder's ABC .

Atcoder's A is not a problem, but a solution!

Epic XD

Yes, C was very ambiguous for me

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.

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 .

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

The best boring ping pong in C.

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

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

How to deal with D?

check this https://codeforces.com/blog/entry/85116?#comment-727852

How to solve B ?

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$$$.

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

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

Oh!I understand this.Thank you so much.

.

How to solve B?

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

You aren't wrong

A should be a better example.

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

greedy

I did dp, I guess there are more solutions.

can you explain the dp solution plzzz

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.

i got it thanks

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

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

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

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]

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

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

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.

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

operation. As anoperationcan only lower down the value of an element, so it is optimal to lower down the values when possible starting from the left.Update:Cleaner and faster code.C++ Code: 100058194

Time Complexity: $$$O(n)$$$

Auxiliary Space: $$$O(1)$$$

Problem C was really ambiguous. Strongly dislike it.What was the point of 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

Got VERY stuck on B ;(.

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

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

https://codeforces.com/stream/71

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

Ikr. i don't see why it was a D. Q.Q

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

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.

Thanks!!

Can you explain why this solution will work?

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

how to solve b

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

if y>1 so ans = cnt, why is this always happening?

For B, let's use only

+ias long as sum < X.How the answer of B for n=12 is 5 ?

1 + -1 + 3 + 4 + 5

1 -1 3 4 5

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

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

Really,really thanks a lot man!

Welcome !!

And for x=11?

1 2 -1 4 5

MarcosK Make a nice hacks for E

Doesn't it mean that someone did bad tests?

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

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?

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

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

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

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.

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$$$...

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

Is it codeforces or ObservationForces?

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!

Theoretical computer scientist: That is O(1) XD

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$$$.

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?

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

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.

problem C was much much easier than b.

any tutorial for b pleaseThis comment

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

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

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.

That's problem B, not problem D.

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

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

Adhoc-Forces crossed 100 million+ submissions. wow!

How to solve Problem E?

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.

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 :/

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

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

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

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.

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.

A<C<BGuys look at the topic(contest) rating, going to zero XD

How to solve E?

Some explenation on E would be of educational worth.

I just posted my method above — I hope it makes some sense.

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.

Me after reading the solution of problem C

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

Problem statement guarantees:

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

no problem with the given constraints n^3 solution passes

Is the round difficulty below average ?

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

is their hack points in this contest??

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

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

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

MarcosK

Hello nerds,

I think contests of codeforces also drowning into the

scam of plagiarismand 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 ofdemotivationto 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

I agree they have same code. Please take action BledDest

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)

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 :/

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

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.

Wouldn't

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

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.

Nice explanation @nagraj41. More formally, I think that is what he means.

https://codeforces.com/blog/entry/85116?#comment-728332

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.

Wish I was dumb like you!

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

source

Good contest. Finally I can be expert

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

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$$$.Problem G is really nice.Thanks!

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

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

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

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

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.f

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!

Me too :(

Can we apply BFS in B problem??

I know u r gr8 at graphs but why for this problem

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

(i,x,prev)

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

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

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.

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?

Yeah that's pretty much what I meant.

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

anything on when ratings will be displayed?

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

Wasn't this contest rated?

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.

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

Me too :)

I think some successful hacks are added to the system tests.

Ratings will be displayed as soon as system testing complete.

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.

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

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

where is the editorial?

Where are the tutorials?

Can we solve 2nd using dp?

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

Is it rating???

Below average problem set.

Cf standard going downward day by day