Привет, Codeforces!
В Nov/30/2020 17:35 (Moscow time) состоится Educational Codeforces Round 99 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | neal | 7 | 223 |
| 2 | jiangly | 7 | 224 |
| 3 | tute7627 | 6 | 190 |
| 4 | nocriz | 6 | 195 |
| 5 | noimi | 6 | 213 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | MarcosK | 41:-6 |
| 2 | dapingguo8 | 34:-2 |
| 3 | jerdno | 12:-4 |
| 4 | ARTpositive | 10:-1 |
| 5 | halyavin | 9:-1 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| 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: Разбор опубликован
Hope this round will be good
Another Educational Round! hopefully I will do better like previous Educational round. Hopefully the problem will be more interesting.
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.
Notice the usual start time
Super Excited !!
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 !!
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 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 distribution awoo ?
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 :)
I just pray and hope that it wouldn't be another Mathforces round.
pikMike loves Math problems, so who knows!!!
aaja mahi aaja mahi aa soniya aa ve aake aaj mere gale lag jaaa tu hoye....
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
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
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.
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.
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
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!
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 !!
How to solve E?
How to solve E??
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 than 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.
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.
Solved Div.2 Dfor the first time.How to solve c (please tell along with proof) ?
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
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?
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://mirror.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 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 .
The best boring ping pong in C.
I don't like this round. Learned nothing from ABC.
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 \gt 1$$$ and also we have $$$o \lt 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.
I might get a lot of downvotes here, but I felt that $$$C$$$ was a pathetic problem, with no learning at all.
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.
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:
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://mirror.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!!
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
For B, let's use only +i as 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 !!
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
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 please
This 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 :
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://mirror.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://mirror.codeforces.com/contest/1455/submission/100073456.
Edit: I'm not sure if this solution is always correct.
Guys look at this Topic(Contest) rating, going to 0 XD
Guys 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://mirror.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 :)
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
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 \lt =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.
Wish I was dumb like you!
People didn't like problems so they downvote, what's wrong with that? — Errichto
source
Problem E is not binary_search
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
minwithn - 1doesn'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$$$, wherea[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$$$,iis $$$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 — SabrCoder
They are most likely coping someone else's code and testing their hacks on the dummy account.
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://mirror.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?
I'm curious why Educational Round doesn't system test instantly after finishing the hacking phase.
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.
where is the editorial?
Where are the tutorials?
Can we solve 2nd using dp?
Can anyone tell me why am i wrong ? :'< https://mirror.codeforces.com/contest/1455/submission/100029658
Below average problem set.
Cf standard going downward day by day
Why, then, could not solve problem E, since the standard is easy?
The answer is in your comment XD The guy who cannot solve E,solved ABCD within 50 minutes! and no ds recquired till D! Neither a hard implementation problem nor any requirement of hard observation or ad-hoc logic till D -_- so you want to treat problem D as B in previous difficulty standard, Nice. Clap clap
when will the rating changes will be published ???
what about ratings update?! hacking phase is annoying.
Yeah Even I thinks why there is 12-hour hacking phase.
probably timezones, so people don't have to stay awake at 3AM to make hacks.
It's annoying to check and find that the rating is not changed yet. update: Oh finally! the rating changed.
By when shall we expect ratings to change?(Don't know why I'm getting so excited for having a -30 :( )
My case is same as yours :( and I am also excited
Why the rating hasn't been updated yet?
Has it ever occurred that after a round has been conducted the ratings are not updated and as a result the whole round gets canceled? Just Curious.
As long as nothing serious happened during the contest,(no wrong checkers, no wrong problemsetter's solution, no wrong/very misleading statement) then there is no reason to make the round unrated.
I don't know why does it take so much time to give us the rates !
eliminates those who copy code
Why codeforces takes long time for the rating?what's going on.
Will the editorials be published for this contest?
Yes .as soon as possible
bad luck :(
I bet one cannot write something more stupid than this XD XD
How is it possible that his solutions were skipped and not yours? Weird! I mean ideally submissions of both the contestants should be skipped. MikeMirzayanov
No. Not both. First submission shouldn't be skipped(at least in normal Div 2's). I will leave it as a practice for the reader why first submission should be accepted.
Hint: Think about hacking within contest rooms.
Okay Got it!
No use claiming such thing here. They are just too irresponsible to check whether or not did you really copied the solution or not. Once the MOSS has flagged you then even if you are trully innocent, they will just don't give a shit.
Ratings updated
After 6 months finally expert, excited
Have you noticed codeforces just crossed 100M submissions during this(Edu 99) contest?
Thanks for the contest for +191 and pupil :)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
worst contest ever :/
Girl say:Can you open this jar for me? Boy say:Download Java
I_have_achieved_Komedy.jpg