Hello Codeforces!

On Oct/29/2021 17:35 (Moscow time) Educational Codeforces Round 116 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all the participants!

**UPD:** Editorial is out.

Thank you very much awoo for cool contest. We will wait for even more contests from you :)

.

I think you can check it on the internet

I checked 99 euros is 8,648.06 rupees. I was glad to help you.

Lighthearted MemeHave you paid copyright to naman1601 for using that tag?

Hey, I understand that you want to make a point, but don't you think tagging is unnecessary? I believe noone likes to be tagged just to see their

meme stylebeing stolen by random people.What harm did you get from this tag?

wasn't he joking ? I believe he was just memeing.

I wish if div 3's were more frequent...

when i started, i thought that i can't participate in Div2 because my rating is < 1600))) So i waited for Div3s)

xd

I have never participated in contests but it was my first time and I could not do well. when is Div 3 ?

https://www.timeanddate.com/worldclock/fixedtime.html?day=2&month=11&year=2021&hour=17&min=35&sec=0&p1=166

thans

How did you improve so much?

solved problems and watched videos on Pavel Mavrins YouTube channel

Good luck to everyone on this educational :D

u too good luck :D

Non-related mememy problem b just failed for longlong in this way...

I hope I can add 50 points

sure you can! if there are any problems, just use calculator!

LOL! I thought Codeforces Round #752 was going to happen before Educational Codeforces Round 116 [Rated for Div. 2]

Glad to see no unusual time.

Normal timings be like:Notice the unusual time of the round

Hey, I have few queries to ask about educational Rounds:

1) I heard that all problems have equal points, Is it so?

2) If every problem does have equal point, then, Is there any deduction of points after every minutes during contest? If yes, then does it vary for each problem?

Thanks in advance.

It is ICPC style contest. There are no points. Only number of solved problems matters. And there is a penalty which breaks a tie between people with the same number of solved problems.

Penalty is calculated like this. If you solve any problem, then the minute on which you solved it will be added to the penalty. For example if you solve problem after 1 hour and 23 minutes after the start, then 83(60+23) will be added to the penalty. Also if you had unsuccessful attempts on this problem previously, then each attempt will add 10 penalty points.

there are queue in codeforces it will be solved before the contest ??

I will AK Edu 116

A is way more difficult than B

mood

How to solve E ??

for dp[n][x], iterate over i = 0 ~ n but i != n — 1, which means i people died in the first round

The condition to have no winner is to have at least two same max numbers and then the rest of the numbers can be anything less than that. Am I correct?

Countercase: [1, 1, 2]

There is only one maximum, but all heroes receive 2 damage in the first round and die, so there's no winner.

Thank you for replying! Is this like an edge case? If no, then what was the intended solution?

It's not an edge case, there's no way to eliminate these cases easily.

We will post an official editorial in 24 hours after the contest.

Shortly, the main idea is dynamic programming of the form $$$dp_{i,j}$$$ — suppose, after some round, all heroes received $$$i$$$ damage, and exactly $$$j$$$ of them died, what is the number of ways to make it happen?

sorry but why wait 24 hours for editorial, when hacking ends in 12 hours? its almost as if educational rounds are notorious for slow editorials

So maybe just handle such cases alone?

My approach was adding all possible combinations with max value <= $$$min(n-1, k)$$$.

Then for all $$$i$$$ bigger then or equal $$$k$$$, do what faraz said, at least two same max numbers and then the rest of the numbers can be anything less than that.

I didn't implement in time though and unsure if even close to correct.

This solution doesn’t cover all cases, and there is no easy way for that. And that’s why you have to do dp

Does problem D have an actual clean solution other than sorting the rows and prefix/suffix max/min on four sides?

I did the same thing. 3961ms AC...

Me too, but only 810 ms. record

Would really like to see the editorial for D

:D In C Problem, complier 64bit wrong :D and 32bit AC :D -

:DMost likely the pow function here is the culprit. Even if both of its arguments are integers, it still works with non-integer types, so it sometimes causes precision issues.

tks, I think I need to use my pow function for the next contest.

Took me 40 minutes to figure that out :')

But i used the binary exponential as power still the error is there

Can u please explain how u solved C problem?

you can use n = 10^(a[i + 1] — a[i]) — 1 notes for each note. For the largest one, no maximum. Iterate each note from small to large. if k is more than or equal to n then use all the notes, minus n from k and move to next note. if you have k less than n, then use (k + 1) notes and done.

Thanks a lot

sr, my English is not good. You can following test example: F(59) = 14 / 9

s = 59 = 9 * 1 + 5 * 10

s = a * 1 + b*10 + c*100 + … + z* 10^9

follow k and array A ascending.

=> x = 10^(a[i+1] — a[I]) — 1

k = k + 1;

If (x >= k) => ans += 10^(a[I]) * k => update k = 0 => end program;

else

if (x < k) => ans += 10^(a[I]) * x and update k = k — x; and loop when end array or (x >= k)

but k maybe not = 0, u need to update ans += k * 10 ^ (a[n-1]) (with a[n-1] = maxArr)

Thanks a lot

:| How to solve Problem D? :( I can't think of solutions for it.

Hint 1... Find the prefix max, prefix min, suffix max, suffix min along each row.

Tks, I trying to solve it :D

If you sort the rows by the first element in increasing order, it turns out that blue rows is a prefix of the matrix.

I read D wrongly as

Me too, initially. But after looking at the figure, I corrected my understanding.

I want to ask all of you, honestly, pls tell me which problem was good for you and why? For me, it was so nonalgorithmic problems :(

All are quite good problems. If you talk about algorithmic, D — F of course are.

Hi Folks, need help, how can we approach problem A? I tried few ways but my approach is wrong.

first and last symbols must be the same of the string to achieve AB's = BA's

@ADO thanks valid point, let me think about it and try it out.

Yes. I spent 19 minutes to realize this simple result...

Me too got confused and after 5-6 WA i realized the simple solution :(.

Why Math.ceil() in java is giving wa on testcase 6 Wa But calculating ceil manually gives ac AC

coz I think Math.ceil() will give some precision error while manual ceil gives correct answer. See below: ~~~~~ Input: 1000000000000000000 2 Checker Log wrong answer 2nd numbers differ - expected: '500000000000000000', found: '500000000000000002' ~~~~~

. Using Math.ceil(), we will get above error . !!

Well that was embarrassing

How to solve E?

Think about how to kill a fighter. His health should be lower than n. So, no winner means all fighters have health less than number of fighters at some time. Pick k players and assign them any health lower than n. C(n, k) * POW(n — 1, k) choices. For the other n — k fighters, health of each of them is decreased by n — 1. So, here is a sub problem: the number of choices when we have n — k fighters with maximum x — n + 1 health point.

dp(n, x) = sigma(k = 0 to n, k!=n-1, C(n, k) * POW(n — 1, k) * dp(n — k, x — n + 1))

Thanks

where is the editorial?

Obviously not during hacking stage, huh?

Damn , I solve problem after contest ended by menuties

Today I got a lot of WA on third as I was using gnu c++ 64 bit

Spoiler4th numbers differ — expected: '999999920999999999', found: '999999921000000000'

but after contest friend suggested me to use gnu c++ 17

Spoilerok 4 number(s): "59 778 148999 999999920999999999

anyone know why this happen?

Here

No idea how but I just ACed F using $$$O(n^{\frac{5}{3}})$$$, actually its $$$O(nk^2+\frac{n^2}{k})$$$ with $$$k=150$$$. Posting this here hoping someone can hack it somehow. 133531014

I don't know whether or not it's hackable, but you can very easily improve the $$$O(nk^2)$$$ DP part of your solution to $$$O(nk)$$$ by simply not visiting useless DP states. Specifically, notice that you can't remove more nodes than you've currently processed, so if you've processed the first $$$m$$$ children of some node, and you're about to process ($$$m+1$$$)-th, then you have $$$\min(\sum_{i=1}^m sz_{ch_i},k)$$$ useful DP states. Proof for how this then becomes $$$O(nk)$$$ is here.

With this, setting $$$k=\sqrt{n}$$$, the complexity becomes $$$O(n\sqrt{n})$$$, which comfortably passes in 1s, my code: 133546415

how to solve c?

First One is Not Accepted During Contest :- WA

Second One Accepted After Contest :- AC

:( You can feel the pain after looking my code and why it gets rejected while in contest

When will the system hacking start?

So many hacks on problem B. Can anyone give me the edge case?

Hack Meme :(That's not the thing bro ! Any way your solution is going to fail the system testing :( My submission on B is not hacked but fails sys test. Rank drops to 4700+ :(

Test cases are added when someone hacks solution of other participant

yeah!!

can someone tell me whats wrong in my code? https://codeforces.cc/contest/1606/submission/133515590

Because 10000 iterations isn’t enough. Answer can be very large and you can’t loop.

thanks but i thought it grow fast like fibancci sequence so i thought 54 is enough can you explain why this conclousion wrong

After copied computers reaches k, each round could only add k more computers.

but i handled that by making a formula to simulate adding k computers every time till reaching n or larger this is the lines /*

*/ is there a problem in this formula?

For example n=10^18 and k=1. You can copy to 1 computer at a time

ok now i understand so the answer for this case shoulde be n — 1 i will try it thanks alot

Yes

I have a very simple solution for problem A, can someone tell me if its somehow not good??? https://codeforces.cc/contest/1606/submission/133508578

impressive, thats a clean and simple code thanks very much

How to solve F? I assume quadratic DP is trivial? Can it be improved or something?

It is really an educational contest thanks for writers

can someone help me with my code https://codeforces.cc/contest/1606/submission/133548731. It is giving wrong answer and I don't know why.

Overflow. Change dp[i+go][k]+=dp[i][j]*(power(go,j-k,mod)*ncr(j,k,mod))%mod; to: dp[i+go][k]+=(dp[i][j]*((power(go,j-k,mod)*ncr(j,k,mod))%mod))%mod;

This will solve the WA, but you will get TLE.

thanks a lot. i think the tle can be fixed by precomputing some stuff.

How to solve problem E? I'm stuck.

See my comments above.

It's been more than 8 contests and haven't improved yet, feeling very low and disappointed not able to solve even a single question in this round. Also doing upsolving but not improving any suggestions please

Create a mashup of 4 A(1000 level) problems + 4 B problems(1200 level) and solve them in the virtual contest.

Don't down yourself anytime it evens makes you perform bad in contests.Try practicing questions from a rating range greater than your currrent rating. believe in yourself and one thing nothing can be created in one step Try hard for it and keep all your efforts . I hope you will be fine

Can someone please explain their approach for Problem D?

let mnl[i][j] be min(a[i][k] for 1<=k<=j), mxl[i][j] be max(a[i][k] for 1<=k<=j), mnr be min(a[i][j] for j<=k<=m) and mxr be max(a[i][j] for j<=k<=m). Iterate from column number 1 to column number m-1. Let the current column number be j, let array t contains all the row indices i in ascending order of mxl[i][j]. Now, if we can cut the column into two pieces at column j (j being in the left part), there must be some prefix of t such that max(mxl[k][j] for k belongs to prefix of t)<min(mnl[k][j] for k belongs to suffix of t) and min(mnr[k][j+1] for k belongs to prefix of t)>max(mxr[k][j+1] for k belongs to suffix of t). Here, all the indices in prefix are coloured blue and the rest are coloured red.

Here is my code. (Ignore the segment tree templates. I initially thought of implementing using segment trees but, later used multisets).

will this contest be rated for me because when I am seeing my graph after the contest it is showing that this was an unrated contest

Can anyone tell me what's wrong with my solution? 133471460 For example on this test case : 576460752303423488 288230376151711743

Jury's answer is 60 but according to me it should be 59. As, first 59 powers of 2 will give the sum of n-1 and 2 ^ 58 < k here.

Even I got it wrong. The issue is with log2. Instead divide by 2 repeatedly.

Same :(

Any way learnt a thing about log2() function that's good for me:)

Oh, thanks! Never using log2 again :(

133567594 Can anyone please explain testcase 41 in this problem??

How to solve F using segment tree or treap?

Hi , i was checking my final standing and i saw i just got wrong answer after the contest and even hack session was over while before that i have got accepted in problem B. So i don't know if they changed the test cases or what but i think it's not fair to change the test cases when the contest is over and changing the test cases should just be allowed while the contest is running.(and i didn't get hacked , i just suddenly got wrong answer on test 30 in problem B).

This a rule in contest which have hacking phase in them. They collect all hack cases and insert them as new tests.

oh i didn't know that thanks for responding.

I am new can anyone share where I can find editorial of this contest.

Thankyou

Educational rounds have a 24 hour hackig phase after the coding phase ends and editorial is only published after the end of hacking phase.

I think hacking phase is of 12 hour.

In B, I got the value of pow(2,log2(k)) greater than k itself. How is this possible? It was for the testcase: 576460752303423487 576460752303423487

This is a problem with log2() .

see this : https://codeforces.cc/blog/entry/56975

When will the editorials and the ratings get updated?

Hello Community can somebody confirm that whether rounds #751 and Educational Round 116 were rated or unrated?

This is my hack case which kills more than 100 submissions.

The issue is numerical error of log or pow in 1e18.

see also the editorial of this problem : ABC215-B

correct outputThat took me down, welp :(

Hi, awoo, and other round coordinatrs. Please check this issue that my solution for problem C is skipped, reason stated that it was coincided with others solution. The solution to the problem is quite intuitive, may be, that's the reason. Please check it. Not this time again.

can you tell us the number of submission that coindieded with yours??

if you can't, you are just another cheater from India -the country of cheaters-.

The solution to the problem is quite intuitive, maybe, that's the reason,Yes it is so intuitive that you changed your template and coding style on C.try to take a quick scan on my previous 3 submission of problem C. I shouldn't reply to you but still.

why does most of the Indians doesn't know any shame?

do they think that people from other countries are dumb as them to believe their lies?

Can someone help me explaining why this solution for E problem is not correct?

In my solution winner must have >= n health to win(others n — 1 heroes can have < winner health)

Then I subtract from all possibilities win possibilities

https://codeforces.cc/contest/1606/submission/133586943

I did the same thing but it wasn't working for the fourth sample case. If someone can point out the error in the approach, it would be really helpful.

MikeMirzayanov In the Educational round that was conducted yesterday, I have been wrongly flagged for plagiarism. The solution for question C was fairly straightforward in terms of logic and coincidence should have been expected by the problem setters. I assure you I have not indulged in unfair practices. I participated after a fairly long time and was really happy that I performed well. Please return my rating delta. Thanks in advance.

awoo please look into this

MikeMirzayanov I am once again requesting you to return my rating changes.

Was waiting for an educational round for a long time.... Finally had a great contest today and was ranked 858(my first ever under 1000 rank :-) and got a rating boost of +105 :-)

When will be the editorial out for this contest? I didn't even get the solution for

`problem A`

that why would the answer be`s[0] = s[s.size() - 1]`

which got accepted.Problem B: https://acm.timus.ru/problem.aspx?space=1&num=1131&locale=en

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).I haven't been seeing them publishing top 5 winners and top 5 hackers and 1st one to solve the each problem for a while..