On Nov/12/2018 17:35 (Moscow time) Educational Codeforces Round 54 (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 extented ACM 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 **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 and me.

Good luck to all participants!

**UPD**: There certainly will be a discussion of the problems on the local Discord server shortly after the contest ends. I might join it as well)

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | Anadi | 7 | 266 |

2 | HIR180 | 6 | 129 |

3 | mrscherry | 6 | 152 |

4 | Vergara | 6 | 158 |

5 | Jeel_Vaishnav | 6 | 185 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | teapotd | 100:-4 |

2 | vlad.raw | 52:-5 |

3 | MarcosK | 32 |

4 | tataky | 28:-5 |

5 | knotValid | 23 |

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

Problem | Competitor | Penalty |
---|---|---|

A | Dalgerok | 0:01 |

B | Nazikk | 0:03 |

C | neal | 0:03 |

D | tamref | 0:14 |

E | shadowatyy | 0:13 |

F | killer_god | 0:34 |

G | lxrvelory | 1:03 |

**UPD2**: There was an error in problem D which caused some incorrect solutions to get accepted. We will investigate the number of users who were affected by this issue and decide whether the round is rated.

**UPD3**: We discussed the issue and came up with the following decision:

Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated.

**UPD4**: Editorial is out

2 hours for 7 problems seem to be too less. Any chance extending the time to 2.30 hours? Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems. C'mon beloved Codeforces! Give a thought.. :)

"Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems".

Not really that's what Div. 3 rounds are for.

Div3 rounds (both frequency and problem difficulty level) are inconsistent, Edu Rounds are still the best way to get introduced with ideas that can be used in broader extent.

Most of the div2 people solve at most 5 of them anyway. Having 2h for 7 problems is good enough, since it gives a challenge for the better contestants too

I'm saying just for education rounds though, the idea is to Educate, so why not give an extra half an hour?! That will surely benefit lots of programmers like me who are not yet to the level but trying to attempt and solve more problems than they usually do. There're lots of other div2 rounds where better contestants can be challenged by 2 hours time limit.

Pretty sure the meaning of "Educational" rounds was lost a long time ago.

Back when they started, educational rounds had classic problems which highlighted ideas and techniques that contestans should learn.

Nowadays they are just normal contests with different rules ¯\_(ツ)_/¯

Maybe they ran out of ideas and techniques that new contestants should learn...

that's a good idea but maybe 2 hours make us want to try faster .. for me at my best I would solve 3 problems in less than 2 hours so it won't make that difference but it could for others so I agree with you

Hoping to get some plus ratings in this round :p

well... not anymore :/

Lower, or lower and equal to 2100?

educational round == div2 round sponsored by harbour space

True

If your rating is equal to 2100 then your rating will not change no matter what.

Hi, guys, is it rated for me too?

I am participating after a long time and I have heard that some changes have been done in the divisions — div1,2 and 3. What are the rating ranges in these divisions and will my rating be affected if I participate in this contest? Thank you.

You rating will change

okay. Thanks

An Educational round after several bad contests, time to get new high rating.

69 ( ͡° ͜ʖ ͡°)

what is test 5 on E???????????????????

Why can't we see the test cases?

wait are we allowed to discuss

Why in E d can be>n?

it doesn't matter. you can just take d=min(d,n).

There was an error in problem D which caused some incorrect solutions to get accepted. We will investigate the number of users who were affected by this issue and decide whether the round is rated.

I am really sorry :( Both bugs (in D and G) were mine.

<3

Why not consider it as a part of the hacking since Accepted here is not a final verdict because there is testing after hacking phase is finished

Just imagine the number of people who attempted to other problems after submiting a wrong solution to problem D and its affection to the rankings...

The tests aren't exhaustive, and Accepted doesn't necessarily mean your solution is correct.

<3

Isn't that the whole point of having hacking-phase or system tests?

You are poset

Please don't unrated. Please. :(

Please turn on hacking phase to hack solutions with cout << 0 (to investigate the number of users who REALLY affected by this issue) and then run system tests.

Such a noob

Please don't be unrated

TOM TOM TOM

i submit code for problem D with just cout << 0 << endl; and get AC but good vertices in my code ans simple test 1 are different why??

NO!!! Plz be rated!!!! It's my first time to be MASTER!!! :(

I was gonna be an expert too:(

Poor you, bro. I hope this contest could be rated.

How was your result today?

After seeing that "cout << 0" passed all tests in D, it is really unnecessary to consider it should be rated or not:(

The system is judging at the moment. :)

I hope it's rated too.

I agree

The same thing man, I can be

expertfor the first time in my whole life after 2 years of work, if this round will berated, please let it be so.Please don't unrate this contest.

Could we rejudge problem D or some accepted incorrect solutions?

I don't think so...

I myself didn't solve D, but there might be some guys with little bugs, who would have solved this problem after getting WA.

How does correct checker guarantee that you will get WA for the little bug? The little bug is the most common reason for hacking

It mustn't be that little you're thinking...

Not everyone solve problem D in on try. But getting AC in pretest means don't working on it anymore.

And the pretests was really weak, the guy posted above (alireza_kaviani) got AC with outputing only 0.

Spoiler Alert:In D, is it true to:

1- Find MST.

2- If

n- 1 < =kthen we have reached the answer, otherwise, erase edges starting from leaves until the number of remaining edges equals k.I think it needs to be tree that grants minimum distances from the node 1 (like, dijkstra-tree)

You're right. Dijkstra tree with the root at 1. Not MST.

Thank you! I had forgot what MST represents, but have just remembered.

Shouldn't it be shortest path tree rather than MST?

Apply Dijkstra from source 1. Get tree with n-1 edges. Start removing leaves edges from that tree. Too bad I had a small bug in Dijkstra and could not submit on time.

@MatPhySC what if # of edges in optimal paths is greather than K, dijkstra tree should answer less edges than the solution

If I understood your question correctly than if K >= N-1 then answer will be Dijkstra tree because all vertices are

goodSorry, poor english, but what i mean is that even when all vertices in Dijkstra tree are good, there could be another ones that belong to some other Dijkstra tree and they are also good edges

consider this case: 3 3 3 1 2 2 1 3 1 2 3 1

if i understood your solution, it should give 2 1 2

however, 3rd edge is also good, at least the way i get the problem

UD: i got it now, it's good vertices, not good edges

There are two Dijkstra tree. You can consider any of them.

Wrong solution:

Consider the following case - 3 3 2 1 2 2 2 3 2 1 3 3

Answer is — 2 1 3

Answer from MST - 2 1 2

Minimum distance from 1 to 3 is 3 units. MST gives 4 units distance from 1 to 3, so 3 is no more a good vertex.

This will fail. Consider this tree. 1 2 1 1 3 1 1 4 1 2 4 1 There are multiple MST. But taking any MST other then 1,2,3rd edges. Will give WA.

MST does not guarantee that all edges are at the minimum distance from vertex 1.

Thank you all!.

Beautiful problem BTW :D

I don't think MST works. I got AC on this problem with SPT(shortest path tree). and maximum number of good vertices is min(n-1, k).

What is test 3 in D?

First time I wrote a buggy segment tree. :(

It means you get an Accepted for Problem E, don't you?

Could I see your solution?

Yep. It was accepted after the contest was over. In the last minute, I realized my mistake.

My Soln.

Thanks, bro. Hope you high rating :)

when I wondering how this guy passed D in 31 ms lol, lmao

I bet a lot of contestant will fail on D :|

It seems like the checker was wrong, because the code is clearly wrong for even the sample cases.

This solution doesn't even take the input.

It's not necessary to take the input. See this blog.

Thanks got it :)

It's not necessary to take input in any of the problems.

I am sorry to be saying this but in my opinion it would be extremely unfair to declare this round as unrated because there would be many people who might not have done 'D' and have performed well in today's contest. If some incorrect solutions were accepted then it may as well be considered as a case of weak test cases. I urge you to consider the plight of many like me who believed they did well in today's contest and would be stranded disappointed if it is made unrated. PS Edit1: To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.

feel about those coders who cannot improve his D solution to get actual AC solution. because of he/she already get AC.

I can understand that but that's also the case in many contests when your pretests get passed and your main tests fail. I understand that either decision would be unfair to some but it comes down to which one is more on the fairer side. It comes down to 1 question vs 1 contest and I believe that making it unrated would be more unfair.

My solution on D is actually failing on pretest 2 but during contest it passed Now consider if the checker was correct i would have checked my code again and solved it after getting a WA.

Yes, I understand it wasn't fair to you. I sincerely apologise for ranting out.

To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.

make it unrated omfg !!

thats what you wont say when you did a heck good job today (or at least you think so). and the guys who got a crappy AC for that problem will get their ratings back to what they should have in the next contest or two ei?

yeah i forgot

mostof the ,s and .s but yeah nice day too :Dyou didn't submit any solution for D lol

When will we know if our submission for D is correct or not?

Why can't simple dfs + 2 multiset pass problem E?

I passed with a simple DFS and a vector of maps.

Perhaps you got some bugs? Personally I wasted 30 minutes for not realizing I overwrote queries instead of accumulating those lol.

You were right, I made insanely stupid bug. GG

Mine passaed 45632893 (After the contest and the code is probably bad)

rated plz!

Just fix the problem(s) of specialjudge.

And those best hackers will get everything done. ;)

In system test, the code that pretest is passed can be wrong, naturally. I think there is no reason that this round will be unrated. Moreover, this round is educational round and hacking can't be attempted in the contest. So this round wasn't influenced by something wrong.

If our solution failed on pretests we will have time to make that solution correct. But now we can't do anything. So if round gets rated it will be unfair for all participants whose solution failed on D because of bug in checker. So round should be unrated.

if your solution is this: then you obviously know your solution is wrong.

and if its something different, how is it different then having very easy pretests if it passes sample correctly?

My solution is not even close to this. And we can't assume all 36/37 pretests are like samples (in running contest).

Same would be the case when pretests are weak. but we don't make it unrated in that case.

36 weak pretests in D! We are not that unlucky

Let's hit the unrated button.

PikMike said this in Discord server...

damn that feels good..

It seems that the special judge of problem D is incorrect. So I'm thinking about something like ummmmm.. unrated? In fact, I just wanna complain about the awful quality. Please check your contest more carefully.

Let's make it unrated

I feel that the contest

should not be rated. Any opinions?please make it unratedIt say people, who get WA1 on D.

I'm wondering why my bruteforce solution on problem E could get Accepted... Can anyone explain why?

Don't worry fam, it's no longer accepted now :)

The answer to "why" it was accepted before is because pretests are never perfect.

Please keep it rated !!

please rated

So many people wanting the contest to be unrated are people who just did bad, not people who were affected by D.

I did bad and was also affected by D

OK ,The contest must be UNRATED!! ;)

I solved problems A, B, C, D and F. I was really happy with my results and now my D got wrong answer on test 1 (after the contest). I have A, B, C, F problems accepted, which worth less than A, B, C, D because solving A, B, C, D is faster than solving A, B, C, F. A similar problem was at round 485 (the queue froze during the contest): http://codeforces.com/contest/987 I lost 166 rating points there, I can't believe this is happening again. Instead of gaining points, I will lose :( Please make it unrated.

If you got wa on even sample who is to blame really?

I never check the 1st example, I don't get penalty if I get WA on test 1. And why would I check after it got AC?

I messed up, got stock on C god please make this unrated

Am feeling kinda stupid.... Anyways how to solve E ?

Whenever you enter or exit any node, update BIT. I got that idea but implemented it with set instead of BIT during contest.

solution: http://codeforces.com/contest/1076/submission/45630591

Thnx

You can do a simple DFS throughout the entire tree, starting at node 1 (i.e. root).

Before starting, let's denote

`accumulated`

as an integer storing the sum of all added values for the current node. We'll get on with the way it worked below.When we start traversing from node

`z`

with depth`depth`

, we'll do all these things:`z`

as subtree root, and add thexvalues of all those queries into`accumulated`

.`z`

(only those with distance not larger thand). Therefore, we'll use a global array`deactivated[]`

(more info in next steps). For each query with maximum depth allowed ofd, addxinto`deactivated[depth+d+1]`

. Of course, sinced≤ 10^{9}, if`depth+d+1`

surpasses the maximum depth of the entire tree, ignore it.`deactivated[depth]`

from`accumulated`

.Then,

`accumulated`

will be the answer for vertex`z`

. Store it and start running DFS like usual. When done traversing, remember to undo all the above steps before leaving the function.My submission, for further clarity: 45624305

Thnx. Got it. Simple!! My bad.

Nice solution!

Wait, another Kuroyukihime around here? <3

lotus is my wife!

We discussed the issue and came up with the following decision:

Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated.

very well

Please make it rated for those who use

`cout << 0`

It is clear that someone might get lucky enough to try it and get AC

But it does not makes sense that many people were able to do it.

It is clear that they clearly discussed the hack among themselves.

Can you explain what was the issue clearly? Incase if the WA was on hidden pretest then maybe next time make it unrated for everyone having WA after final system tests too in all rounds?

For some solutions in problem D that should be rejected the checking program answered that they are accepted.

How many such users are there? I still fail to understand if a solution gives correct answer on sample tests and gives WA on some hidden tests whats the problem... How is it different from having weak pretests..

Because the checker gives AC even if the solution gives incorrect answer on samples.

2 categories:

gets AC on samples previously, WA on samples now

gets AC on samples previously, WA on

hidden pretestnow (eg: http://codeforces.com/contest/1076/submission/45623636)i think number 2 should be rated

I think number 2 should be rated

The checker wasn't correct,

It outputs ac if you just printed less than or equal to K distinct numbers from what i understand(even if you print 0).

What about the people who are getting +ve rating change even after being affected by WA in D? It doesn't make sense to make it unrated for them.

Just unrated all, let this round be a practice round

Like traditional educational rounds

Make it like those who got accepted earlier and get WA now won't be affected by rating changes if their delta is negative. P.S. My delta shows positive by predictor

How about being unrated for negative deltas?? Seems cool!!

But just a question, the unrated people will be considered out of contest(unofficial) or not??

Similar thing happened in this contest

Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!

Sorry, I miss your mean.

Why different decisions for similar problem that happened in educational round 51?

BledDest any comments?

When there were only 10 contestants affected, it was easy to check them manually.

When there are 500 of them, it is much harder since we can't automatically do it.

You should take the "unrated" users out of the rating pool entirely (i.e. make them unofficial). Rating deltas are comparative: if somebody gains rating, someone else is supposed to lose it. If you just make the users not affected by rating changes, you'll have some users who influence the ratings of others but don't get their ratings influenced themselves.

I hope what I'm saying makes sense, I don't really know how to express my idea.

D-Forces

It's my first chance to become master, I'd like to see it rated, but if the wrong make the contest unfair seriously, it should be unrated.

If you deserve it then you will get it

Actually I don't even it's rated, lol.

Can someone explain to me what I messed up?

http://codeforces.com/contest/1076/submission/45631931

It's just a dfs + 2 multisets. I must have looked over this more than 20 times. (I also put the updates to active/spent before and after the recursion, but that didn't do anything.)

Thanks in advance.

nvm solved, made stupid bug

Can someone explain me why this solution for problem A will fail ? http://codeforces.com/contest/1076/submission/45621631

3 baz

Your answer is ba when my answer is az.

Deleting biggest one is not the solution check it 5 abcad

Consider this case:

3 bac

Your code output "ba", while the correct answer is "ac".

So, what you have to do is not removing the largest char in the string, instead you have to remove the

firstchar s[i] such that s[i]>s[i+1], as this will result in smaller string.Can someone explain me why I'm wrong? I made a submission to count number of good vertexes and with 50000 edges, one can't have more than 50001 good vertexes.

45607996 // the original one, from the contest 45632353 // the modified one

The edges you give aren't necessarily connected. So you could have tree fragments everywhere. You have to do a dfs to get the edges and make sure they can actually reach the 1 node. (I might be wrong.)

I'm using Dijkstra starting from vertex 1, so the graph is connected for sure

I submitted problem D 3 times.

In the second time, I get AC but the system said WA.

When rejudge, My second submission is changed (it exactly the same solution of prolem A). I think this is a bug of Codeforecs. Could you consider my case?

Submission number: 45627317

Before rejudge, WA on test case 3.

After rejudge, WA on test case 1, and the code is totally changed :( why ?

Hi Mr.MikeMirzayanov,

My submission 45627317 was changed after system rejudge. I sent a message to problem setter but he did not respond. Please check again I will support any thing.

It maybe I submitte wrong file code. :’( Sorry

is your standing in the leaderboard affected by how many accomplished hacks do you have?

Please don't unrated, I probably become specialist after this round TAT.

Don't worry, I think u can become specialist soon ~~~ fight!

weird behavior, according to my code it never can be N for 69 but here in cf it is showing N.

Looked at your code — if you use the cin/cout speedup for C++, never mix them with printf/scanf — the streams are desynchronized so the output may not come out in the same order as you expect it to. That's what is happening here.

Thanks!! i got it.

You should look up what things do before you use them :)

That

`#define timesave ios_base::sync_with_stdio(false); cin.tie(0);`

, isn't some magic fairy dust that you just sprinkle over your program to make it faster. It has some effects.To be more specific,

`ios_base::sync_with_stdio(false)`

means (as the name suggests) that you are disabling syncing between io with streams (the kind you do with cin and cout) and standard io (the kind you do with scanf, printf etc). You disable the sync, yet in your code you usebothmethods of io (you use cout for the "No" case and printf for other cases) and then expect them to be synced up.Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!

The thing is that people could check their source once more if they knew that's wrong, but everyone usually stops at the AC verdict

He meant, "those who got accepted due to the bug, and the same submissions got WA after rejudging".

And for that, it's certain enough to say why it should be unrated (at least) for them.

Thanks, bro. I know his mean now.

Isn't is unfair to those who are getting positive delta but it will be unrated for them.

Can you please proof the problem C ?

It's a pure mathematical problem.

According to the given formula, we can figure out , thus .

You can draw the graph of the equation , and figure out a few things:

d= 0, obviouslya=b= 0.d< 4, no solution can be found.d≥ 4, the functiond=f(a) is a monotone function. Thus, you can binary search the valuea, andbcan simply be obtained asd-a. Keep in mind that your precision has to be right to fit the output's relative/maximum error criteria.For the last case (

d≥ 4) no need for binary search, instead, solve the equation which is actuallya^{2}-d*a+d= 0. After that,b=d-a.Simple.

I feel freaking odd to deny solving this simple quadratic equation and binary searching the answer during contest time :D

Well, whatever that works :D

if i did't got accepted, my rank will up. and now my rank won't up. sad :'(

And persons that haven't try the quest D? Is unrated or rated?

Yo yo dudes, come on, the ones who got affected should have their rating increased if it shows +, and nothing if it shows -.

Preview twice, post comment once.

just another [partial unrated educational round rated for div 2]

If I got D accepted with a wrong solution, but still managed to gain some rating after my D got WA, I do not see the point of why my rating should't increase.

How to solve C?

x + y = d xy = d Math system

binary search

I spent a lot of time for D problem. And i have a nice score . Why my contest won't be rated. I don't do

printf(0);

I do bfs but my solution get wrong answer after rejudge. Please help me!!!.

It is not fair.

You are so right. Why do you ban from contest. Don't accept question but it should be rated for all.

Can anybody proof me B problem, pleace

If n is even, then the smallest prime divisor is 2. After subtracting 2 from it, n is still even, so the smallest prime divisor will keep being 2. Therefore, the answer is how many times you can subtract 2 from n, which is n / 2.

If n isn't even, find the smallest prime divisor d. You do one subtraction and get to n — d. Now, d is most certainly odd, therefore n — d is even, so the answer for n — d (as described above) is (n — d) / 2. Counting the subtraction of d from the start, the total answer is (n — d) / 2 + 1.

"Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated."

This is unfair for the users with positive rating changes even with WA on D. Please see if there is an alternate solution for this issue.

I totaly agree. Please make it rated for the ones who will increase their rating.

BledDest why not doing this ?

Atleast make it rated for those getting +ve rating change, no matter if they were affected by D or not.

this contest should be rated for all those who got correct the 4th one but failed later..but still are getting their ratings better than before and unrated for the ones whose ratings would be decreased due to the 4th question.

Can anyone tell me how to solve problem D ?

run dijkstra from vertex 1 to all other ones

that gives you a tree of shortest paths

all you need to do is remove leaf by leaf untill you have k+1 vertices (and k edges)

it clearly maximizes the number of 'good vertices' and is always valid as well

Can anyone gives me a hint on problem E?

My friend tell me its depth segment tree ， but i still no idea yet update： I pass the problem just now，here is my code http://codeforces.com/contest/1076/submission/45654052，I think u can get my idea easily。orz，the solution not very difficult，But I've been thinking about it for so long. It seems more practice is needed……

Can anybody please proof the problem C mathmatically. It would be greatly appriciated. Thanks :)

Consider a * b = a + b = d

we can get 2 equations for a , a = (a+b) / b = d / b and a = (a * b) — b = d-b

d / b = (d — b) ->

b^2 — bd + d = 0so , we can use quadratic equation to get b , then a = d/b But if there is no valid answer from quadratic equation then answer is

NWe know:

1) (a + b) ^ 2 = (a ^ 2) + (b ^ 2) + 2 * a * b

2) (a — b) ^ 2 = (a ^ 2) + (b ^ 2) — 2 * a * b

So we can calculate (a — b) ^ 2 as follows:

1) (a — b) ^ 2 = (a + b) ^ 2 — 4 * a * b

We know also that a + b = d & a * b = d.

let A = d ^ 2 — 4 * a * d

So we have (a — b) ^ 2 = A

Now, in order for the problem to have answer, A must be positive. In case where A is negative simply output 'N'. In case it is positive, find it's square root and name it c.

now we have to equations:

1) a + b = d

2) a — b = c

So a = (d + c) / 2 & b = d — a

After calculating the values for a & b check them. The problem wants a & b to be non-negative real numbers. So if either of them is negative then output 'N' and else output the numbers.

By Vieta's formulas, we know that the sum of roots of the second degree polynomial

ax^{2}+bx+cis equal to while their product is equal to . So if such numbers exist they will be roots of the polynomialx^{2}-dx+d.why exactly did people try to submit solutions with cout << 0 anyway?

that feels just odd to me

Can someone please explain me why my answer is wrong for problem A in the shown test case? Input 1000 rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgurflfvnersfqkwnsmsh...............

Participant's output rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqavgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgu................

Jury's answer kqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngw..................

(why is 'r' being cut instead of 'z'?)

Consider the simpler case:

Output:

`ac`

Your code's output:

`ba`

You should delete the first character s[i] such as s[i] > s[i+1], not the largest character

Can anyone make me understand solution of D. Had a terrible round.

My solution is based on dijkstra's algorithm from vertex 1. So while we're running dijkstra , i just pick the first K node(that is not 1) that we visit by dijkstra , if we were about to exceed K just break the loop. (FYI my dijkstra is implemented in a while loop with a priority_queue as the main data structure , you can see the submission from my profile.)

Actually Dijkstra process built a shortest-path tree with N vertices from the graph. So we will build that tree, and repeat this N — k — 1 times: Find a vertex that is a leaf and delete it. This process make sure all the current vertex of the tree has as same shortest distance from vertex 1 as it was before the deletion, and the number of these vertices is largest. This can be done with dfs

You can make the deletion simpler, by dfs the shortest-path tree and build a subtree of k edges. Here is my submission 45633192.

How to solve problem G ?

Was the contest unrated for all..as my rating has not been increased.

So we have just eliminated everyone affected by D... what?? This is just so stupid. Someone who has done E or F and whose rating might be +100 would be unfair for them!! Make it rated for those with +ve rating change please.

" Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated. " — What if the those contestants will get a higher rating if we skip D submissions of those users?

My rating still hasn't changed, is everything fine? I haven't touched D at all.

UPD. It did now, sorry.

deletedFor those who got TLE on test 64 on D: When implementing Dijkstra, do not check edges from a vertex if it is already visited (in other words, if the distance from the PQ is greater than the one written in the distance array). A vertex can be pushed into the PQ O(V) times and it also can have O(V) outgoing edges, so it can be O(V^2) in the worst case. Furthermore, this can be repeated for multiple vertices and possibly reach O(V^3) in a complete graph.

The generator is:

This is unfair to me. Predictor was showing I will get +50 rating. But now this became unrated for me. This is unfair...ummmmmmmmm

Is there a way to look up what test was used to hack my solution, in case I want to debug?

View test under the hack verdict: https://codeforces.com/contest/1076/submission/45608998

Is there

editorial?For E is it possible to build some type of tour so that we can use segtree for range update and then push all the changes?

I have the same question. Can someone answer this?

i was wondering how setters managed to change the rating based on a particular problem's verdict... is it a database sort or ??

Why TLE on Test Case 64? problem D

maybe this

Thanks. Accepted.

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).I think in "Meme Problem(C)" float and double will give different answers. Both the answers shall be considered valid since logic is same. If programmer is able to give any one of them it implies his/her logic is sound.