Hello, Codeforces!

I'm glad to invite you to amazing (we've tried to make it such) Codeforces Round #748 (Div. 3) which will start on Oct/13/2021 17:35 (Moscow time). This round is made by me (MrPaul_TUser), a significant contribution to the round was also made by MikeMirzayanov and BledDest.

The round contains 6-8 problems. The difficulties of the problems are expected to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make really strong tests — just like you will be surprised if many solutions fail after the contest is over.

You will be given **6-8 problems** and **2 hours 15 minutes** to solve them.

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

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

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

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

Thanks to _c_k_r_, Vladosiya, spotless, Yousry, powergee101, ncduy0303, I_Remember_Olya_ashmelev, A_Killer, OlegZubkov, mahade31, arjunsanjeev7, and UpS0lver for testing the round and improving tasks.

Good luck and have fun!

**UPD** Editorial

Looking forward to an interesting round!

Yeah Ofcourse !! good luck man.

Good luck bro!!!

This was really interesting round !! it has created confidence to continue competitive programming...

Hoping for a good contest :)

Looking forward to change my color :)

SpoilervrintletovrintlePlot twist:SpoilerDidn't expected this would be my last Div3 round..

Plot twist again:SpoilerGot hacked on E!T_TSpoilerI like your confidence, All the best

SpoilerWhere are rest of your heads ? reference

Actually, he is frightened coz dussehra is coming !!! :)

cracked me up lol. good one.

Nice one...Lol

@coder_ravan

You didn't get his joke. Just check the spoiler .. lol

brilliant, bro!

My first unrated round.

Nevermind, but can someone remove cheaters in last round

+1

I know bro... I feel sad a bit and very unfair

Now, I am feeling it . :(

That's not true, in the round before the last one, I got +24 after the contest, getting to 1599, and then, cheaters were caught and I hit 1600! Additionally, seeing this comment, we can conclude that cheaters have been/are being caught for the last round as well. Codeforces staff puts in a lot of effort, please don't belittle it with baseless accusations/claims.

Could anyone explain me about what happened in the last round?

apocalypse and destruction

I became eligible to participate in this round. :P

I hope I get +160 or higher rating points after this round. Good luck to you all.

Hello everyone! Good luck to everyone to write this contest and adjust the rating well!)

-1

VERY UNPAIR

It would be nice to recalculate the rating for honest users.

+1

It is sad(

Did you just say "Shame!!!"? What in the world do you think gives you the right to say that? Even you know that it's not a right thing to say, else you wouldn't be cowering behind an alt.

Please don't ruin the comments section of every blog you see. If there are some issues, create a blog or comment on blogs that already exist for that issue.

-1

Where did you see him say

it is fair not to remove cheaters? Aren't you making up the truth? Do you think it's fun to deliberately destroy the environment of the comment section? Aren't you ashamed of yourself? And you just put the blame on Codeforces?Don't you know that admins have to do a lot of things every day? And how can you be so confident? Less than an hour? Don't you know how much manpower and material resources it takes to run a website? Do not know how cumbersome it is to process all the competition information of more than 20000 contestants and then calculate the rating? Take your brain before you talk, and don't talk nonsense if you don't understand these things, okay?

Also, can you stop yelling "Remove cheaters! Remove cheaters!" in the comment section of each official blog? You think admins doesn't know these things? Don't know how many contests recently? Don't you know how much admins workload? Please, be considerate of others. You're happy to make others hate you, aren't you?

I didn't want to say anything at first, but I can't stand seeing the comment section like this. I hope this is the last time I get angry about such kind of shitposts.

Sorry for my bad English.

As an ex-admin of several huge online projects, I would like to agree with EasonCF: you can't imagine what enormous amount of work such kind of projects require.

And the subject of the problem is insanely ridiculous: cheaters? Does it really bother you??? Rating? Are you serious?

You've got a lot of great CP problems WEEKLY! Great tests, fantastic database of solutions and editorials, archive, and what are you talking about: cheaters and rating??? Be ashamed!

Big fan of all the positivity you just radiated :)

Can you create a blog for this problem??

The last provided ratings will be rolled back and then updated as usual I guess :)

Will be great a competition for sure :)

div3 contests are lub

Despite my earlier criticism , I have come to appreciate naman1601's light hearted memes under every contest announcement. I would request him to bless us with another light hearted meme.

P.S. He just became purple again. Everyone please upvote him as a congratulations.

lighthearted memeLooking forward to increase my rating.

Hope the difficulty level of is not equal to Div.2 which is the case with most Div.3 contest these dayz.

I believe I can finally be a

studenton CF. Good Luck everyone!You mean pupil?

In div-3 do all questions have same score? Like A and F have same value upon solving?

no, rating distribution will be updated later most likely.

no, in Div 3 and Education rounds the scores for all tasks are the same.

oh, right my bad.

It really hurts when rating is exactly 1600 :(

Yeah !! a little less and would have a big positive delta and would have been stable as an expert. But the reverse can also happen. Little less than expert, take part and it decreases more. In this case, you would have missed the expert and would have been disappointing :|

And now you're 1599 lol

Can't say I understand but I guess I can

Hoping to be a blue coder to change my profile picture xD

ah yes, all that's left is to convince my parents to let me stay up till 1am.

Or...Or do I speedrun solving 2 problems in 1 hour, and get deleted?

SpoilerLooking forward to this round!

After messed up Codeforces Educational Round 115 and Codechef starters 15 , I am looking forward to this round as my mood changer round :) .

why always on weekdays

Best of luck to everyone on this round!

Wish all participaters all good fortune

Participants. :)

But what if you're a beginner like me who hasn't taken part in two rated contests yet?

it says it'll be rated anyway. we're just being excluded from the official standings, i don't think it'll affect us in any way tho

True.

yes,

Note that the start time is unusually usual.

I hope everyone can raise rating

That's impossible.

Hoping to become green after this round. Wish me a bit of good luck.

Questioncan i get green tonight ?

Only if You're able to solve Problem G (XD)

but why?

There is no problem X.

Sure.

Allfather bless me so that my color changes (to the better side) this time.

Hi, Im New, but what languages will be accepted, like python c++?

both, my dear friend! There are still more language available for you :)

Today is my birthday, and I will participate in this round.... Yoooo

Wish u Happy birthday and High ratings too.

Happy birthday!Good luck!

Wish you a very happy birthday! May you acheive high rating!

Wish you a Happy Birthday!

Hope my color changes after this round ! )

It's cool that the penalty for a wrong attempt will be 10 minutes

I hope to stay newbie after contest :)

dude you have solved 1000+ problems

unfortunately, most of them were trivial, i hope the coming well be better

You are an inspiration truly! You are trying hard and didn't give up! [user:Khedr_]Best of luck!

thanks :)

Good luck.

I wish I could be green coder after this round!

Hoping for change my color =))

As a tester, I tested…

GL&HF

I hope that the penalty of all contests will be 10 minutes instead of 20, not only Div3

I'm not reading Announcement comments anymore.. Man I feel too old

You're old in this platform.

had a terrible contest

I hope my rating will reach 1900 after this contest Good luck !!!!

[

Any hints on F?

DP

I think it can be solved using digit dp.

solved G faster than rainboy pog

btw G felt too easy for its position...

can you give me idea how to solve G, i got stuck on it used dfs and take max depth of node , give me bad output.

editmy bad i mean problem E srydfs? how?

my $$$O(n+q)$$$ solution for pG:

note that we can change between $$$($$$ and $$$)$$$ (similarly, $$$[$$$ and $$$]$$$) at no cost, let's transform $$$($$$, $$$)$$$ into $$$a$$$ and $$$[$$$, $$$]$$$ into $$$b$$$

then we can subdivide each even length substring into blocks of length 2. there are 4 possible blocks: $$$aa, bb, ab, ba$$$.

A block of $$$aa$$$ or $$$bb$$$ cost 0, while $$$ab$$$, $$$ba$$$ cost 1. $$$aa, bb$$$ cancels themselves, and $$$ab, ba$$$ cancels each other. (both $$$abba$$$ and $$$baab$$$ cost 0) so the problem reduced to find how many $$$ab$$$ and $$$ba$$$ blocks are there in a range, and cancel them while possible.

the answer is the difference between the number of $$$ab$$$ and the number of $$$ba$$$ in a given range, using prefix sum can solve each query in $$$O(1)$$$ time with $$$O(n)$$$ preprocessing.

Thanks bro!I never imagined G could be that easy so never gave it an honest try T_T

in pE do DFS $$$k$$$ times result in a worst-case $$$O(nk)$$$ time complexity, it occurs when the tree is also a "chain" (edges are $$$(1, 2), (2, 3), ..., (n-1, n)$$$)

nice problems :)

Is D2 about iterating over the numbers which have more than half of the bits set in $$$[1,2^{N}]$$$ ?

you should just get the difference of between every 2 elements in the array and try all of their divisors

Yeah dumb of me to not notice that, btw please accept my apologies I hacked your E :(

That's the evilest thing I have ever seen

How is it TLE when I'm moving from the leaves directly to the next operation leaves

Edit OMG I forgot to add break after i edited my code the last time it was correct

My method:

If any element appears >= n/2 times, answer is -1.

Otherwise: for each choice of reference value a(i) from the array, consider the set of differences abs(a(j) — a(i)) for all j. Where the difference is 0, increment a counter z. Otherwise find the factors of abs(a(j) — a(i)), which can be done in O(sqrt(max(a))) time. Keep a count of how many times each factor occurs. Any factor such that count(factor) + z >= n/2 is a possible answer, and the max of these candidates is the final answer. Remember to reset the factor counter for each choice of reference value a(i). Total time complexity O(N^2 * sqrt(max(a)) )

Solution: link

Nice :)

this was my exact solution lol

hoooolly shit that was intense i accidentally solved D1 like how it should be solved in D2

:( ? Why D1. n<=40 but sum (n) <= 100 ?

Any idea how to do D1? I tried doing it by taking the GCD of all the differences of pairs but I was getting WA on test case 3

first find the minimum element, then take GCD on the difference between the minimum value and each element (except the ones with minimum value).

output -1 if all elements are same.

Thanks. I iterated through all the NC2 possible differences and was sure the answer is right . But I was using a long long gcd function which was giving gcd(0,negativeno) some overflowed value . I changed it to int and it got AC .

I guess you forgot to sort array

Sorting array is unnecessary. Any member of the array can be used as the reference value.

You are also required to check if all items are equal. In such case, answer is -1(Infinite)

I checked your solution here https://codeforces.com/contest/1593/submission/131802472

and you have an integer overflow issue as you use

`vll a(n);`

which expands to`vector<ll>`

of which`ll`

expands to`unsigned long long int`

.When you perform

`a[i] - a[j]`

and it is unsigned, you must take extra precaution.Thanks a lot , I will keep this in mind :)

Quite interesting problemset! Thanks for this round!

Really nice D2

How did you do it?

Really liked the problems!

Can anyone point out my mistake on B? Submission

I used bitmasks to simulate the removed numbers, implementation was buggy as it keeps getting WA on test 2

Anyway it will get TLE as your time complexity is O(n*2^n) where n <= 18, and for T <= 10^4 it will get TLE. I also implemented similar solution initially, https://codeforces.com/contest/1593/submission/131774681 But it gave TLE.

Thank you, will keep that in mind

What the heck is this second test for E?

Edge case when $$$n <= 2$$$, output should be 0

My output is 0 for this...

Same question (:

have you checked?

me and my friend have lost this case:)

Sure, but... Not in my case :(

Not in mine too..

bro me too.... missed this one :(

n = 5, k = 1; 1 5; 1 5; 2 5; 3 5; 4 5;

That helped me

Not in my case :(

Case when 3(or more edges are outgoing from a single edge). Consider the case: 7 2 1 2 2 5 5 6 2 3 3 4 4 7 Removing the first set of leaf nodes, shall not make node-2 as leaf. Your solution does. I had the same problem, figured out but couldn't implement. Your Answer — 1 Expected Answer — 2

oh, yes, it makes sense, thank you!

1 7 2 1 6 1 5 3 1 6 7 1 4 1 2 expected : 0

can someone help me by telling what i am doing wrong in Problem-E

solution link : https://codeforces.com/contest/1593/submission/131852543

Same request: 131819309

Draw the following case on paper.

Spoiler1

6 2

2 5

4 3

6 2

1 5

4 5

consider this example.

n=6 k=2

treeCorrect answer:Answer is 1

Your answer3removedAnswer is 0

I liked the problems, but this is really irresponsible behaviour. I understand sometimes issues may escape the testing phase too, but quietly changing the statement without announcements trying to not address the that there was an issue is not acceptable. I spent a lot of time trying to debug my initial submission, and finally when I couldn't believe that this was incorrect, I tried refreshing the page.

Following up on this, problem E did not have limit of sum of K over test cases, neither had tests which had this large sum. I don't understand why authors didn't put max tests? Weak tests in general on many problems, as you can see from the number of hacks and FSTs.

Constraint of problem D1 was a trap.

Isn't this solution correct for problem E

Number of nodes left = total nodes — number of nodes which have distance less than equal to k to the closest leaf node.

Your answer should be 1, but using the above logic, you will get 0

Got it. Thanks

Was giving the contest from an alt, logged in to orig to see friends standings, forgot to switch, did a wrong submission on E ;-; RIP me back to green ig :( Atleast if I had gotten AC on E, would have been worth it, but got a runtime error ;-;

bro also the sample was not strong in most problems

How to solve C?

Check my submission: 131779632

I used prefix sums and binary search :)

the cat moves exactly $$$n-1$$$ times, so the total times you can move a mouse is also $$$n-1$$$.

To save as many mice as possible, always move the mouse nearest to the hole first. You can sort the array of the distance of each mouse to the hole, then try to save the mice from the nearest until the total distance exceeds $$$n-1$$$.

Its easy sort the array . Take currentTime and t . Sort array and from last , for each mice calclulate the t = n — arr[i] this time will be to go into Hole . also add cnt++ . Add t to currentTime. If at any point , currentTime >= arr[i] break and print cnt

My idea to C was basically greedy . claim: making the mice closest to the hole move is the most optimal strategy proof : I guess it is by Exchange Argument consider a better solution exists . and this is not optimal so we move the mice ahead which is not the ending one . so making this mice move over larger distance . in place we could have moved more mice near the hole into the hole . so clearly our strategy is optimal

really nice contest! in problem b can anyone tell me if there a bug in my code or its not supposed to use bitmask due to constraints https://codeforces.com/contest/1593/submission/131838191 sorry for bad english

I think you have a problem with this : 1 <= t <= 10000.

meaning : t * pow(2, k). (2 <= k <= 19).

ok thanks i calculated the time complexity too but i thought it may pass XD sorry another question can you tell me if my code is correct or not i amnot very familiar with bitmask

Yes, I think it's correct.

Just for criticism I think it would be better if you could replace this line :

with this :

ok thanks alot

glad to help

Looking at the hacks, I foresee many TLEs on E, especially for those that BFS from leaves and keep track of degree of the nodes

If done smartly this approach is fine. Only perform updates when a node is trimmed, and the total number of updates is equal to the total number of edges, which is N-1. Why should that TLE?

Ok looking closer at the ones that got hacked and unsuccessful hacks by galen_colin (don't wanna tag for no reason), during one cycle of BFS they push the next elements into a separate queue/DS, and then replace the queue/DS. Maybe overhead from replacement is causing the TLE.

Yes I see. I just used a priority queue and did it Djikstra-style to avoid anything like that. That's not to say I won't be hacked though — who knows :)

I think the problem is that sum of k is not bounded and many people (including three of my div 1 Ukrainian friends and myself) just had a

`while(k--)`

loop or something similar.The problems were good but the samples were really weak

samples are not supposed to be strong lol... what's next? all tests are opened?

They could've added a test case for -1 in problem D1

imo, finding of cornercases must be a part of a solution

Imo there is no need for pretests at all let hackers do the deed.

Seriously this round is a joke.

samples!=pretests

They did, I forgot that, got WA on pretest-6.

missed (

I know you are impatiently waiting for the editorial, so I've decided to share with you my easy-to-understand solution for problem A.

Wow, very simple and efficient code. But I write all possible way with if else statements that what newbies do.

Can someone help me figure out why am I getting a different output (which is one more than the required output) when on codeforces judge, but when I run it locally on my compiler it gives the correct output for the same test case.

Here is my submission

Because you are including death[0] in your answer. death[0] is not set anywhere, so its value on your local machine may differ to that on the server.

Nice catch, but after fixing that, I have a similar problem but this time a 3 instead of 1, I tested it on my compiler and it gives the correct result,

Submission

PS: I have realised my solution is incorrect but I still want to know the reason for the inconsistency in the outputs for future reference.

It's very difficult to say for sure but I have (recent) experience of similar things and my finding has always been that I've been accessing something that I didn't mean to, or that I didn't think was there, by mistake.

A hypothesis might be that your adj is not resetting itself in the same way online (since you are not explicitly clearing the elements). But I confess I cannot say for certain.

You're setting some

`death[i]`

to be 1, but I think you might be assuming that the others would be 0, which is not correct.Why multisource bfs isn't working in E?

Reading your code, your method appears to be "ans(node) = min distance from node to any leaf". This method is not correct. Consider why this is incorrect with the below case, to which the answer is 1 but to which your code gives 0. During the 2nd iteration, node 1 remains.

1

6 2

1 2

1 3

3 4

1 5

5 6

Got it. Thanks

Can Anyone Help Me Out to find why am i getting wa for problem E ,My Submission : 131857557

You also fail the case mentioned in this comment

Thanks , will look into it :)

These types of Solutions are getting hacked with TLE, but it doesn't seem to exceed TL. This is O(KlogK) solution. Perhaps this is because of Java?

Correct me if I am wrong. Thanks.

I don't use java much but Arrays.sort(a) in java has worst-case time complexity of order n^2. Therefore the worst-case time complexity of your program is n^2 which gave tle.

You can read more here

Oh okay, thanks for the information. So there are more chances of java solutions getting hacked whenever sorting is needed in the solution, right?

Yes, you are correct. I have seen tons of solutions in java getting hacked on codeforces due to Array.sort(a). You should switch to Collections.sort(a) or suffle array before using Array.sort(a)

Array.sort(a) uses quick sort only on primitive data types. So if there is no primitive data type Array.sort() is ok.

An example of Collections.sort() can be seen here in the SecondThread solution

Notice that he uses collections.sort and fastio for speeding up the code. Collections.sort() wont get hacked as the worst case of it is nlogn

Submitted this after the contest as an experiment. Can anyone please suggest why wouldn't it work?

Anyone else with the following on Test case 2 for E

`wrong answer 37th numbers differ - expected: '1', found: '0'`

?What is this test case possibly? I did multi-source bfs starting with all the leaves of the tree.

I have this WA too, but i did dfs from a random leave

I don't know but I do know that even making the smallest mistake, things that you think are OK to ignore will cause trouble in this problem, in my code I had to add just 1 if statement and it would have worked fine :( .

Yours gives 0. Ans should be 1

Edit: My bad k >= 1

My code gives 0 for this case.

1 6 2 1 2 2 5 5 6 2 3 3 4 The ans should be 1. Multisource bfs gives 0

Can't understand the test case. What is n and k here ?

6 and 2

Found the mistake. Thanks. Its possible to solve using multi-source bfs but at every step you also have to subtract the degree of the parent of the leaf node and push it in the queue only if its degree == 1

try only pushing those nodes which are connected to the current node being processes(u) after removing u from the tree in the multisource bfs. If you didn't do it this way!

Video Editorial of E (Gardener and Tree)

A simple and easy to understand — Implementation for problem b : 131798547

I think anyone needs it :3 : https://www.youtube.com/watch?v=sZxP4zkSLSE

It seems that D2 has many suceesful hack. Is pretest weak or some conercase ?

when I run this code on some other compilers like gfg ide, visual studio I get correct O/P for sample test case 1st but on codeforces I am getting W/A on test case 1st, IDK how this happens ??

Code:

https://ide.geeksforgeeks.org/zN7ERcyWaB

Try with language

GNU G++17 9.2.0 (64 bit, msys 2).I am already running into G++17

Anyone solved E in O(n) by finding 2nd largest length from every node to leaves?

Nice idea :)

I think your algorithm is actually O(K + N log N) though. You use set (insertion log N). I think this explains your long run time — set is slow and you perform a lot of insert and erase operations.

If you wanted this to be truly O(N) you could store, for each node, just the two greatest distances you currently have, and update them in place without need for actually sorting (either through use of set or otherwise).

I brute forced like everyone.

Yup! I did just now

Why there is so much hacking in E? Which test case it is failing???

The majority of hacks seem to be time limit related, where the user has, K times over, created a whole new queue which could have size of up to N.

How though? I believe only the new leaves would be added to the queue and that should be of the order of the nodes since any leaf would be added at most once.

here's my codeSorry for the poor variable naming. Link to submission

Nice problems, but weak testcases. Thanx.

Were the weak tests on D1 and D2 on purpose? MrPaul_TUser

for E tooo. (my code giving TLE after the contest.) can you please answer why this code giving tle.

Thanks for easy +150 points(as cf predictor says)

guys i solved 3 problems my ranking 6000, does it mean i will get green or their is no way ?

It seems like it's going to increase, but not that much to become green)

Some people hacked a lot of solutions, it's hard to read a lot of solutions (at least for me) and find which ones can be hacked and which ones are not.

I think there is a way to test a lot of solutions automatically. Is that true ? and is it allowed ? and do you have any idea how to do that ? it would be great if you can help.

I got wrong on TC2 on C (my submission).... Please help!

I ran your code. use this

`if(i==k)break;`

at last in while loop.yes! got AC...a little bit sad for that silly mistake..however!Now I get relife that my idea wasn't wrong.

If you would like a testcase that fails:

`10 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999 1000000000 1 999999999`

It has to do with not checking for your vector being out of bounds when you incremented

`i`

.oo..thanks!

Here's my Solution to E 131874293. Do you guys have a better approach or this solution is fine.

I think the algorithm itself is fine, and the implementation has room for improvement.

`deg`

is not necessary, you can use`ar[i].size()`

instead.`leafs`

and`new_leafs`

can actually be`vector`

rather than`set`

And consider output

`'\n'`

for new line instead of`endl`

since`endl`

flush the output buffer each time, which may make the running time longerYou can refer to my submission, which has basically the same algorithm as yours and has 3x faster in running time.

Thanks for your time, also isn't set better for removal of leaf nodes.?

But in

`leafs`

and`new_leafs`

, all removals are removing all elements, which is actuallyclearthe set.If you need to remove

individualelements, using`set`

is better (so we use`set`

not`vector`

for the adjacency list in this problem).Ohhk thanks I didn't see I was clearing later

I have a serious concern about the problem A.

Is it fair to allow such submission getting AC?

To compare, this one gets TL. Of course, the only difference is the line 3:

`#pragma GCC optimize ("O0")`

I guess that checker must prohibit the loop elimination explicitly when compiling the solution, because that's what GCC does in this case.

Would be nice to listen to the contest authors' opinion. cc MikeMirzayanov MrPaul_TUser

Well, I'm kinda confused with people's reaction. Could somebody from those who downvoted to comment on that?

Why in the world would getting AC by this submission not be fair? Modern compilers nowadays apply an overwhelming number of optimizations, you cannot know all of them for sure. Which of the optimizations must be considered "unfair"?

Loop elimination is one of the simplest optimizations a compiler can do. If G++ is able to do it while others are not, well, one has to blame the other compilers for that.

I didn't tell the optimization itself was unfair. And I know well what compiler optimization is.

Also, I didn't participate the contest and I don't ask for some other people's solutions to be retested, etc.

I'm just pointing out that the solution which presumes 10^13 operations to be performed gets AC verdict.

Moreover, it does perform those when being compiled with -O0 or -O1. I guess, there's also some sort of flag to disable such optimization while having -O2 or -O3 enabled too.

So my intention was to raise a question about potential elimination of those optimizations while testing a solution.

Why? Because the compiler must not influence the correctness of the solution. And the solution above is wrong indeed, it must not be accepted as a valid one, IMHO.

The solution is not wrong. It gives correct answers for all the tests. If it is compiled without optimizations, then it will get TLE, but it does not mean that it's wrong.

But the question is: where is the margin between optimizations which influence correctness and optimizations which do not?

If you really want to be sure that your code will not be affected by

obstinateoptimizations, then write code in the assembly language. The processor will unquestioningly execute all the instructions you would write.After all, this is not a theoretical olympiad in informatics where participants are supposed to describe the algorithm and prove its complexity. If we code in high-level programming languages, then it's essential for a compiler to speed up the code wherever it's possible.

The fact that it gets AC for all test doesn't mean it's not wrong.

Of course we can't answer this for sure, but at least loop elimination prohibiting could be a good place to start.

I don't insist on it, I was just curious of the authors' opinion.

Anyway, what motivated me to start this conversation was

getting AC by the wrong solution, and I'll keep claiming it is wrong just because it's not completely correct (whether or not you agree with such interpretation).Once again: the solution is not

wrong. It'sslow. It's a slow correct solution. Not all correct solutions are supposed to fit into the time limit, as well as not all slow solutions are supposed to be rejected. Some of them may pass, though.Sorry, but this is not a constructive way of discussion.

Here is the discussion on turning on some optimization flags (-O3, -funroll-loops etc.) for G++ by default on Codeforces. You can't stop progress.

Has anyone done F using meet in the middle technique, instead of using normal dp. In which divide the string into 2 parts and checking each part individually ? I tried but got TLE in TC 7. Though I think it will pass if 2s is given as approx complexity is $$$O(2^{n/2}*{n/2})$$$

It's sad. I thought about question B for 2 hours and still didn't think of it. I think it's much harder than div2

you should have just google the properties of numbers which are divisible by 25 and then it was just an implementation that's what I did

I didn't think about it at all. I only need the numbers of 25, 50, 00 and 75. I've been thinking about how to greedy simulation deletion, so I went astray. I even use search to write, but I know it will timeout

https://codeforces.com/contest/1593/submission/131784183

Give It a look made too easy to understand for others

Thank you. I understand

Welcome !!

Can 131830101 be hacked? I didn't stop the

`while (k--)`

loop even after the queue (`q`

in my code) is empty and my solution has extra $$$\log N$$$ factor because of`std::set`

.after

`q`

becomes empty the`while (k--)`

does nothing (and won't consume a lot of time) because the`for (int sz = LEN(q); sz > 0; --sz)`

inside your`while (k--)`

.Can somebody please explain where I am going wrong in problem E?

My Submission

This code is giving wrong answer on Test 3.

My Approach:First, I found the centroid of the tree. Then I ran a DFS from this centroid and maintained an $$$ans$$$ vector where $$$ans_i$$$ will store the number of operations after which $$$i^{th}$$$ node will be removed.

1. ans[leaf node]=1.

2. ans[node having only one child] = ans[child]+1.

3. ans[any other node] = Second_Max(ans[all children])+1.

I am taking second maximum because for a node having $$$C$$$ children, atleast $$$C-1$$$ of its children must be removed for this node to become a leaf node(removable).

Final answer will be number of nodes having $$$ans[node]>k$$$.

Thanks in advance.

oooooh! Don't know where is the error but the logic is extraordinarily..

Can you prove that taking the centroid of the tree is always correct in your solution?

Well, it was kind of a intuition. But I think about it this way, since centroid is kind of a balance point because it divides the tree into forest of subtrees with size at most half of original, so centroid must be last one to be removed if we follow the procedure from the problem. Please correct me if I'm wrong.

Hello everyone here, Yesterday I solved 3 problems and got an accepted verdict. Today about half an hour back it still showed an accepted verdict. But now 2 out of 3 problems are showing a queue verdict. May I know the reason for this?

system rejudging your problem now !!!

Oh, Thank You so much. Was not aware of this.

Just system testing all the submissions. Don't worry.

Oh nice, now it is 2 out of the 3 submissions have received an "accepted" judgement. Hoping for the 3rd one to get judged.

We tried to make

reallystrong tests— just like you will be surprised if many solutions fail after the contest is over.You intentionally gave n <= 40 in d1 where O(n) soln is easily working just to mislead participants in directly using brute force without much thinking , however if u would have given n in range 1e5 then this thing wouldn't have happened , so it is really not expected from ur side , And also in problem C , u gave time limit 4 seconds and as a result of which some O(1e9 range) solutions got accepted and now they failed system tests.

Just because of your

really strong testsi got +2000 my expected place since i solved d1 before b and c so it was really disheartening to see :(Those who are downvoting will get to know how it feels when it happens to them :)

That's your problem. They all remind that passing pretests doesn't mean to pass system judge :))

When you will be at the receiving end you will understand. I hope you will remember what you preached at that moment.

Accepted.

TLE.

Just changed vector with array and now it is accepted. It feel very bad (T_T) During the contest my solution was accepted and after systest it gave TLE). First time I had got under 2000 rank. It was meant a lot for me. And now this happened because of vector vs array:|

SpoilerAlways, prefer to use arrays rather than vectors.

PS: Do anyone know how to use vectors as fast as arrays?

PS: TLE code

`accepted`

on removing`#define int long long`

.PS: But, creating dynamic array example:

`int*m = new int[k + 1];`

gives MLE. 131911303PS: Global vector working fine.

By the way nice contest ^_^. IMO there should have such testcases during the contest so that we can correct this things during the contest.

You were using a map, not vector.

See

I had put wrong link by mistake. Sorry for that.

Dear MrPaul_TUser and MikeMirzayanov

Testing the D2 question cases seems very inappropriate !

See my submission , it gets wrong on test 56! While it received accept in pretests. It costs me a sharp drop in rankings so from near 1500 i become 3500 because of weak testcases! So i really please you to reduce the testcases for D2 and rejudge this question.

131848968

You mean your code fails on a certain testcase meaning that your code isn't correct within the given constraints and hence the testcases which your code can't handle should be removed?

Nice

No i mean that the failure was because of the poor testcases , if this testcase was able in the pretests me and many of contesters could find and fix the problem! And this tragedy did not happen. I noticed that many of the codes that were accepted for the D2 problem are wrong now, with nearly 1,000 codes, a number of hacks and a large number of them due to poor test cases. This should not have happened !

Can anyone explain why my submission causes RTE, please? 131823111 Same code in Python3, I passed test

Technically, in C and C++ (and most other languages I guess), any integer other than 0 is considered true, so your comparator function that you passed into the sort function to sort your input in descending order is not working as intended, I replaced

`return a.first - b.first;`

with`return a.first > b.first`

and the code worked perfectly.thanks a lot!!

I can't get over this that was my best performance since I started on this site I had a break command in my previous WA submission for E and i fixed everything but deleted the break by mistake it passed and got hacked :'( I could have reached expert without that stupid break command went from 250 to 670 someone give me 10 bags of tissues :'( :'( :'(

Don't worry man. Just do your best next time.

dont feel bad man.these things help you alot in future to be carefull next time

dont worry bro! soon u ll become expert

When will the rating changed?

When will the rating changed?

System testing has not finished yet for God's sake!

I just saw it finish, and now it 99%.

You did not see it finish. That was an optical illusion. :)

Why do I see this contest in my unrated contest. My rating is < 1600

The rating hasn't updated yet. You need to keep waiting for a while until the rating get updated.

You may be not a trusted participant because you played only one rated round before this one.

Sorry, now I see you have already played 2 rated rounds.

I often see it is written in the open hack or system testing phase that only trusted participants. What does this mean?

Read the announcement carefully and you'll find:

When will the editorial be released Waiting for the explanation of D2 and E problems

Well, I have waited for 4 hours from the open hacking ended. However, I didn't see any signs about rating. I'm very nervous and I want to ask when will Codeforces rate? Thanks and I know a lot of people are waiting like me =))

Now it has been updated :)

i am wondering(HELP) what is the significance of n is even in D1 problem

Nothing. This detail is more important in the harder version, D2.

nitin_05

ashokesen02

Even though they cheated in the latest round, they got rated instead of being skiped.

MikeMirzayanov

Thank you for your contest, it was great. Can I ask how long will there be a new contest?

Can we use meet in the middle for D2??

Possibly someone smarter than me will have a way but I can’t see it. For me this is brute force over all possible smallest values of your set where you try to find the largest factor which exists in N/2 of the differences with that element (itself included).

Now, I think that (meet in the middle one)approach would result in TLE since in that approach you will divide the array into 2 equal sizes and look for all possible subsequences that would result in TC(2^20) which is roughly 10^6 and if you try all possible values of k you will get TLE

No, that’s not how it works. See this comment

In problem C: "The actions are performed until any mouse hasn't been hidden or isn't eaten."

That should be

whilenotuntil. Every programmer should know it regardless of English proficiency.@Viettran, 8528190072TuanHDCongratulationIt's sad to see that top1 and top2 in div3 are cheaters (U need to use unofficial leaderboard to see them). They have multiple submissions to different problems within one minute using completely different templates xD MrPaul_TUser maybe something can be done about that, althought I doubit it.