Hello Codeforces!

On Apr/10/2020 17:35 (Moscow time) Educational Codeforces Round 85 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

*Hey Codeforces,*

*What a crazy month it’s been!*

*We hope you and your loved ones are taking care of one another and catching up on everything you didn’t have time for on your normal schedules.*

*We’ve temporarily closed our physical campus and moved our classes online. It’s not as bad as it sounds though — we’ve always known the future is digital, so we were already preparing for this moment. Either way, we’re back.*

**SPECIAL PRIZE FOR EDU ROUND 85**

*This digital transformation opens the door to some pretty awesome new opportunities that allow us to get closer to our community, no matter where in the world they are.*

*That’s why we have a special prize for the next Educational Round, a space in a course of your choice from our Computer Science or Data Science Programs. You’ll be able to study online with us for 1, 2 or 3 weeks under some of the best Data and Computer Scientists in the world, with all fees on us.*

**The prize will be for the top 3 users who have confirmed their desire to participate in this competition. To sign up for it, leave us your handle in the form below.**

*Enrollment in the course you will participate in will depend upon the availability of the course, as well as the prerequisites required for that course.*

*We hope this provides you with extra incentive for the round, and we’re looking forward to seeing some of you soon!*

**FULL SCHOLARSHIPS FOR BACHELOR’S PROGRAM**

*On a different note, we’re happy to announce that we’re offering full scholarships for the most talented high school students who want to study in our Computer Science or Data Science Bachelor’s programs at our university.*

*At the moment, we have two types of scholarships available:*

**The Full Scholarship.** For the best of the best — all tuition costs are covered by the university. Just show up and show us what you’ve got.

**The Co-Creator Scholarship.** For those who want to help us change education — all tuition costs are covered by the university, and in addition to your studies, you get to help the Harbour.Space team on their mission for 4 hours/day, getting valuable practical experience in the field and working in a team with some of the brightest young professionals in town.

*Fill out the form below and we will contact you for the next steps!*

*Looking forward to seeing you kick some ass in the next Educational Round, and stay safe!*

*Best,* *Harbour.Space University*

Congratulations to the winners:

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

1 | MiracleFaFa | 7 | 153 |

2 | jiangly | 7 | 195 |

3 | amnesiac_dusk | 7 | 244 |

4 | risujiroh | 7 | 290 |

5 | bmerry | 7 | 310 |

Congratulations to the best hackers:

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

1 | greencis | 174:-53 |

2 | Java | 94:-8 |

3 | hackVerly | 55:-2 |

4 | EwNacEsirNiaga | 55:-10 |

5 | TheScrasse | 40 |

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

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

A | IQOver20 | 0:02 |

B | arknave | 0:02 |

C | Siberian | 0:03 |

D | sevlll777 | 0:16 |

E | LJC00118 | 0:19 |

F | IceWiz | 0:31 |

G | Cirno_9baka | 0:25 |

**UPD:** Editorial is out

.

CodeforcestheSaviour!!From

Corona:Dlol the meme has more upvotes than the blog

why did you cut out the part where Codeforces suplexes us

Wow!!! The last line of announcement is more likely to be said by a ROCK STAR than a university staff!!! /m/ LoL :))

What if it got wrong during system testing?

Maybe kill

codeforces;DYou don't have to do anything, just wait for next contest

then you'd better warn Mike ;)

When you hack your own solution

is it allowed? i tried to do so but some error message popped

Your test was incorrect

No. That hacking window didnt open when I tried. I knew case where my solution failed

Exactly how I felt haha

If you hack yourself succesfully, you would get 100 points from hacking while losing point from the task right ?

It's educational round, hacking happens after the contest ended, there are no points here.

oh, ok

I really hope there will be problems about COVID-19 and quarantine.

Before reload Oh there are No contests after it

After reload Oh What can I do with these contests

Its raining contests.

Hope to be a good week for everyone and high rate <3

vovuh is ready with div3

I hope the problem statements will not be long

why?

Because long statements are more hard to understand, and it feels not right to have language difficulties in a programing contest.

I hope some day people will stop writing stupid comments

I hope to become Expert in this contest!! If I succeed I will be Expert in just 7 months of coding!! I hope i can do it!

All the people who have downvoted my comment, I WILL PROVE THEM WRONG!!

ok

You cant go from specialist to master in one contest lol

ok

I meant expert, I got confused between expert and master lol

Good luck mate, I am going to be an Expert during the quarantine too <3

Hope the best for everyone <3

It's probably been said a 100 times before:

Hope is a dangerous thing. Hope can drive a man insane.Ok , wish the best for everyone *_*

Hope is a good thing, probably the best.

I want the best for everyone and high rate for them , and they downvoted on my comment !!!!!!!!!!!!!!!!!!

Have you considered the thought I want everyone low rating so it boosts my rating higher? :smirk:

Hoping for no queueforces and strong pretests!

Hoping for strong pretests

A lot of people enjoy some applications at home, but we enjoy with codeforces forever <3

There's no points for hacking in 12 hour hacking phase right? Although the person's solution you hacked would fall on the leaderboard. Am I right?

Yeah

Yes, killing the ones right in front of you is sufficient.

Is it Rated??

it says, it is rated for participants with rating lower than 2100. so for you,

yes its rated.the penalty for each incorrect submission is 10 minutes ?? What does that mean ? also can we hack even after the contest ? I'm a newbie so please explain :-)

For the people who have the same number of problems solved the one with lesser penalty is higher up on the ranklist, penalty is the sum of the time at which each question is solved and also 10 minutes are added to the penalty for each wrong submission. Also the penalty for incorrect submissions is only added if you solve the question.

After the contest if you feel that a particular solution from a user has passed the system tests but you think that you can provide a valid test case which that solution might fail than you can try that and if that solution fails that particular user will lose the points gained on that question.

Thanks yash, it was helpul :-)

Your photo is so cute.

Desperately waiting for the contest

Me: Codeforces is the savior from boredom. Meanwhile Codeforces : Sometimes it feels, I am the GOD...

Sacred Games!!!

good luck all))

.

I've never seen a contest with so poor input examples

How do you know tests are poor?

I said it wrong. By pretests I actually meant the input examples.

Beautiful Problems, thanks awoo

Hi! I'm a newbie.I started doing competitive programming in march'20. Since then I have given almost 10 contests on codeforces but everytime I am able to solve only the first question. How can I improve? Which path to follow?

Solve tasks from here

What's so great about it?

There are a lot of good problems in greedy algorithms topic, which is very helpful in solving B tasks in CodeForces. And also graph problems are pretty good too. Basically, if you are a newbie in competative programming, this site is very helpful.

Also this site is based on Antti Laaksonen's book, which is wonderful for a newbie

Thanks!

In your level you can try to solve problem 'b' after the contest. And then when your can solve b problem , you can try 'c' ......

Hardest Div2 C I have ever seen.

See 631 Div2 That was more harder than this one!

I thought it was super hard for a long time before I realized the explosions only hurt the monster in one direction

Yeah, me too, but then it still was hard to implement, IMO.

nah the implimentation was very easy look at my solution https://codeforces.com/contest/1334/submission/76178082

76131257 Boilerplate and input aside, the actual solution has 10 lines.

Hey nice solution, Can you explain me this why are you adding "best" to "cnt" arent we counting it twice? Thanks.

try reading my code: 76135183 :)

Define $$$f(n) = max(0,n)$$$. If start at $$$i$$$, answer $$$count_i$$$ would be

$$$a_i + f(a_{i+1}-b_i) + f(a_{i+2}-b_{i+1}) + ... + f(a_n - b_{n-1}) + f(a_1 - b_n) + f(a_2-b_1) + ... + f(a_{i-1} -b_{i-2})$$$

Replacing $$$a_i$$$ with $$$(a_i - f(a_i - b_{i-1}) + f(a_i-b_{i-1}))$$$, number of bullets needed would be ($$$(a_0,b_0) \equiv (a_n,b_n)$$$ )

$$$count_i = (a_i - f(a_i - b_{i-1})) + \sum_1^n f(a_i-b_{i-1}) $$$

So, to minimize the number, we compute min of first term (second term is a constant).

What if the question was like "Explosions hurt both the adjacent monsters"? How will we solve it?

You do chain reactions(explosions) in two half circles starting from the monster with least health, I guess?

Video tutorial for C

for D also

Any hints for C?

just solve if we start from 1 and store result at each index. then traverse through i=2 to n so for each such i if we pick this as a stating point calculate the cost. it can be done in constant time and update the result to get global minimum. my_sub

Its easy think :: suppose if we start killing from monster i , then cost of killing all monsters will be ai + (a[i+1]-b[i]) +(a[i+2]-b[i+1])+.... etc.;

so to solve it we can maintain an array d[i]= max(0,a[i]-b[i-1]) {dont forget for i==1} , we should also find sum of whole d[i] array as S;

through above info , now we can iterate over our array and check for every position as :

ans= min(ans,S-d[i]+a[i]); in O(N) time;

Thank you for your video solution. I can sleep comfortably....

just above you

What's the logic for E? The fact that I couldn't even factorise D (10^15) stumped me. How to solve it without factorizing it? Or does the method draw the factors online from the queries... Very interesting problem to say the least. Thanks.

You can factorize $$$D$$$ in $$$\mathcal{O}(\sqrt{D})$$$ :)

You can loop upto 3*10^7? I thought you couldn't go beyond O(10^5-6) operations ;(

You can go up to around 3*10^8 operations lmao.

Wow, how did you even reach Candidate Master without knowing this?

The inputs are generally O(10^5) and solutions are either O(n) or O(nlogn), neither of which pushes the boundaries. I don't really have a sense of how many seconds stuff takes, just in relation to what it generally is.

nvm I misread your comment.

Do we have to make graph or is there any other trick because most of people doesn't used much space?

Optimal path is x -> gcd(x, y) -> y. Every path from x to gcd(x, y) by going down is valid, and every path going up from gcd(x, y) to y is valid. Answer can be calculated by multinomial coefficient.

The person in first place made his code obscure, that is a violation of the rules

It says so right here in the rules:

It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.

(copied from http://codeforces.com/blog/entry/4088)

Obscured by using an algorithm template? :thinking:

I meant first place in official standings, DreamLolita. Here is one of his submissions 76166237

Oh my bad. Yeah that's definitely obscured code.

OMG! this is C++ beyond my thinking, what this guy has done

got TLE on question A , in aprogram with O(n) time complexity , question A and B were easy but with strong test case

Well if you got tle it means your program wasn't O(n)

program of O(n) but i made one silly mistake , i did this :-

`int n; int A[n],B[n]; cin>>n;`

here some very big random value was taken by compiler as value of n was taken input in third line,but i was using it the value of n in second line too and my program mulfunctionedRead all of the input for a tc, even when you have conclude on the answer

i found this error as but by then contest was over.And the fun fact is my program was giving error in third test case , i was checking for loops again and again but didn't checked the declaration part . I am so stupid .

iamxlr8 A with strong test case?

Problem F. Please, explain first testcase. I can't got 20. Sum of all p is 41. Max sum of b in a is 16. Why 20 in answer?4 133787910 7113 50-253678 24Incredible code by DreamLolita

https://codeforces.com/contest/1334/submission/76152622

https://codeforces.com/contest/1334/submission/76137503

https://codeforces.com/contest/1334/submission/76111293

It's not incredible, it's just obscured.

Each variable/function/class name is replaced with ReplacementFor_ (eg. the struct TREE becomes ReplacementFor_TREE). Numbers are decomposed in HEX+DEC-HEX form (eg. 0 becomes 0x113c+1395-0x16af). String/char are written with ASCII code (eg. "YES" becomes "\x59\x45\x53"). Moreover, every non-essential spacing, line-break or indentation is removed and then random line-breaks are put here and there in unusual places.

He/She has made a simple script that obscures the code before submission so that it's harder to copy/paste but otherwise exactly identical to the original one.

Code obfuscation is not allowed, for good reasons. This kind of code is more or less unhackable.

In the last contest, his codes for A, B, C were of quite different styles. I suppose he did this to reduce suspicions this time.

Yeah, I know) Because of this I decided to read his submissions

Can you please tell just basics..what he has written. I was unable to understand

I don't know, it's unreadable for me

Any hints for D? I used OEIS Sequence but got WA on test 2.

see (https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_algorithm)

You can start creating a path like

Then, insert after the n, but before the last 1

and again, like recursive.

The length of the path in every iteration is $$$2*(n-i)$$$ From that you can construct the interval (l,r)

Analyze the cycle for n = 4 and n = 5. Once you do that it's easy to see that the cycle will consist of n blocks, i'th of them will be of size 2 * (n — x) (except for i = n, in that case the block will be just 1) and will look like this : {i,i+1,i,i+2,i,i+3,...}. From that it's easy to restore answer for given l,r.

A general hint for any problem: If you don't know how to solve it, implement backtracking, maybe you notice a pattern.

What's bkt?

maybe his bkt ~ bruteforce

Stands for backtracking (i.e. brute-force), I thought everyone abbreviated it like that :D. I modified my comment.

Wow I was also able to find this but WA on pretest2

Same with Me I wasn't able to solve A :(

What was test case 2 in D?

For C, I took a damage array and at each position I stored the difference(its zero if difference is negative), then I calculated the sum of all the elements in the damage array and also the element where I would start, which is the least possible

`a[i]`

value. I know I count a value twice, I even subtracted that from the final result. What was I doing wrong?Are you sure you always select the optimal start? It's optimal to select the one which has maximum diff[i] — a[i] (or equivalently minimum a[i] — diff[i]).

$$$i$$$ with $$$min(a[i], b[i - 1])$$$ is the optimal start.

got it! thanks

Sorry, but I don't understand what you wrote.

i with min(a[i],b[i−1]), doesn't make sense to me.

The argument of min should be a scalar, it's not the min(iterable) function we're talking about.

I guess you mean "i with min(min(a[i],b[i−1]))"

Can anyone tell me the complexity of Problem C?

It is $$$O(n)$$$ 76190446

Then why it is showing TLE on my soln

you should have used fast input output.

my bad ..i forgotten to call

Can you imagine the feeling of finding the mistake 2 minutes after the contest end?

I feel really great!

Haha, I feel ya fam! Just keep going, we shall bleed red :)

Can somebody Explain why this solution using binary search is wrong (Problem C )?? Submission link

This C is so hard lol while D is braindead.

Problem C:

`Idleness limit exceeded on test 3`

. Note: this isnotTLE (time limit), butidleness limit.Does anyone have any clue why these submissions failed with this weird error on G++ x64? I thought this might be because I don't flush the output (

`'\n'`

instead of`endl`

), but the second one also failed:(Edited for clarity).

same problem occured with me too my solution was of O(N) still got TLE

I edited the comment to be more clear. I don't have TLE, I have ILE, whatever this means. I've never seen this error before.

Try removing those print()s and submit 76193796. It turned to TLE.

Thanks a lot! It works without the debug output (76199653), just like my other submission during the contest. But I'm still surprised it didn't get TLE outright: maybe it's because the solution was unable to read all input before the time limit?

What is hack case in problem A?

1 2 100 50 101 99

answer is yes or no?

Hacked your solution :P

You could've just said yes or no..

now don't hack mine.

I thought the day the finally come when I solved 3 questions in Div.2 Contest.

Sorry, no hard feelings bro.

No issue would have failed System Testing in end.This is Hard Life after All

Keep coding, you will manage to get it after soon days.

Thanks!

I cannot wait for the editorial.. I solved C question in O(n) time . yet it shows TLE in Case 3. tried everything to remove it. Does it have better solution?? Can't think of any :( If yes, please reply to this:)

use scanf and printf instead of cin and cout. Or use faster input/output. Same thing happened with me also.

Yeah. Tried it one minute after the contest ended... Wasted half an hour on removing TLE, still missed this. Next contest, I will try to do better :)

don't use endl, just use "\n"

http://www.cplusplus.com/reference/ostream/endl/

I think you are facing the same issue as I have mentioned here.

how to solve F and G?

Is there anyone whose same solution for div2C get TLE in python but get accepted in c++ ?

Codeforces reply to my query regarding the same issue:

Unfortunately, this is the way things are on most programming contests: it is not guaranteed that each problem can be solved in every languageSad!!!

Can anyone explain why am I getting TLE on test case 3 for problem C? My solution — https://codeforces.com/contest/1334/submission/76172390

maybe you are using endl instead of \n

I submitted an O(n) solution on Python, it got TLE on test case 3: https://codeforces.com/contest/1334/submission/76161837

I rewrote that solution to C++, it got TLE on test case 3: https://codeforces.com/contest/1334/submission/76185611

I inserted the magic string "struct

{(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}__;", it got accepted :https://codeforces.com/contest/1334/submission/76187533G: is it finding (s_i-t_i)^2 * (p(s_i)-t_i)^2 summation across all the substrings using fft. Or are there better ideas.

you can use bitset :D

does bitset actually pass? I didn't try it because I thought it would be $$$26n^2/64$$$

i used pragma also.

What is the usage of input l and r in problem D? I am not understanding what should be output :(

For example, the provided test case n = 3, l = 3, r = 6. The lexicographically minimum cycle is 1 -> 2 -> 1 -> 3 -> 2 -> 3 -> 1. How is this converted to an output of 1 3 2 3 ?

You should take subsegment from l to r(inclusive) from sequence of the cycle(1,2,1,3,2,3,1)

Ahhh, lol, it is used this way. Thanks!

Can Anyone Please tell me why my logic in E is wrong — I thought that if we are given a range from l to r , then we should find a prime number which satisfy r>=l*prime , so that means prime = max prime smaller than or equal to r/l;

finally my answer will be minimum of (r-l*prime + 1 OR r-l)%mod . I applied that logic , but still got WA .

I got my mistake — i forgot considering that each edge have different weight :-( . Miss read the problem . Also not all edge from 1 to N are connected.

76190416 can anyone explain why in problem C , TLE occured in my code. I think the time complexity is O(N)

try fast io .

ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;

is there a soln to C using Binary search ?

it worked using this line struct

{(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}_I think there is a mistake in the validator for problem C. In the problem it is stated that $$$1 \leq n \leq 300000$$$, but when I tried to hack, the validator states

Validator 'validator.exe' returns exit code 3 [FAIL Integer parameter [name=n] equals to 1, viola... range [2, 300000] (test case 1, stdin, line 2)]

Why are the bounds different?

+1, WTF? I submitted a solution that failed on $$$n = 1$$$ and spent 12 minutes submitting a fix (because of something unrelated to the test case itself). Now I tried to hack myself and apparently I shouldn't have even bothered, because the test is not allowed?

Unfortunately, this is true. We excluded the tests with $$$n = 1$$$ just before the contest to exclude unnecessary casework, but we forgot to update the statement :(

We are sorry for that.

76184731

76186776

and here are the cheaters of the day please take some action against such people

He's back. 76138708 , 76144561 , 76160631

Going live on YouTube explaining A, B, C: https://youtu.be/FDbd_sYP7hM

Great tutorials man. I like your style! I will watch if you have D-F tutorials :D

A — check that all p[i] >= c[i], p[i] >= p[i-1], c[i] >= c[i-1], and p[i] — p[i-1] >= c[i] — c[i-1].

B — sort the array and check every suffix.

C — The explosion of the last monster killed is always wasted; we can utilize all other explosions. The number of bullets saved by an explosion is equal to min(b[i], a[i+1]). The answer is the sum of a[i], minus the total number of bullets saved, plus the lowest number of bullets saved by any explosion.

D — The sequence is always of the form 1 2 1 3 1 4 ... 1 n (cycle for n — 1, with each element increased by 1 and the last element excluded) 1. Use simple recursion.

E — The shortest path is always from u to gcd(u, v) to v. To find the number of paths from a to b where b is a factor of a, consider the value x = a/b. Each time we make a move, we eliminate a single prime from x. The number of paths is therefore t!/p1!p2!...pn!, where t is the total number of prime factors (counting repetitions) in x, and p1, p2, and so on is the exponents of the individual prime factors. Multiply the answer for (u, gcd(u, v)) and (v, gcd(u, v)).

F — Use dynamic programming. f[i][j] represents the minimum cost if we consider the first i elements of array a, with j elements of array b already placed. Optimize the transitions with BIT, after noticing that each time, we simply add p[i] to an interval and take care of the case where a[i] is equal to an element of b.

G — Define f(x, y) = (x — y)^2(p[x] — y)^2. Observe that if x and y matches, f(x, y) = 0; otherwise, f(x, y) is always positive. Then we just have to compute sums of the values f(x, y) to determine if two strings match. Optimize the process with FFT after reversing one of the strings.

the question d was easy and i found the logic but I didnt have enough time to write code cz i spend so much time on C, I got frustrated as it was actually the first time I got the logic for c level question in div 2.

(For E) The number of paths is therefore t!/p1!p2!...pn!

I didn't know there was a formula for that. I spent a lot of time write dynamic programming for calculating that, which in the end turned out to be wrong anyway.

My dp solution passed :) 76192690

https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_unique_permutations_of_words

Think about how this problem is fundamentally the same.

My B got hacked even though I did the same :(

https://codeforces.com/contest/1334/submission/76120878 The link for problem B

For problem E, Can you tell the proof of why no. of shortest paths from (a, b), where b is factor of a and x = a/b = p1^a1 * p2 ^ a2 * .... pn ^ an, is :- (a1+a2+.....+an)! / (a1!*a2!*...an!)?

For C, why "plus the lowest number of bullets saved by any explosion"? Is this because the last explosion is wasted and you want to waste least?

Yes. You want to waste the least.

Codeforces should give a note on C problem as it uses fast IO in CPP I had not used until my 6th submission. I am not new in CP as I knew about it but still, they must give a note so that we can check it once in our solution

The problemstatement says there are up to 300000 monsters, each data on one line, each two integers.

Fast IO is a really basic thing.

I think I solved C, but reading TLE with python3 :(

First note that if monsters weren't in the cycle (but in a line) then there is only one solution and you have to shoot the first monster on the left and then the next monster that didn't die from explosion and so on …

Now with the cycle you can notice is that if you shoot a certain monster it breaks the cycle and the solution to the line is just shoot next monster that didn't die. Now which monster to shoot first then?

Naïve approach is to N^2 for each monster, shoot it and walk in a circle. But you can also prove that you don't need to solve again for the next monster you pick. Instead, if you solved for i-th monster, (i+1)-th monster will take sol[i+1] = sol[i] + min(a[i], b[i-1]) — min(a[i-1],b[i-2]), that is you're adding current a[i] (unless it didn't die from b[i-1] before) cause you're starting with it and subtracting a[i-1] cause that one dies off explosion (unless b[i-2] didn't kill it). b[i-1] and b[i-2] serve as upper bounds.

Pretests for problem A are too weak..

Yes..I Agree!

Particularly,Those codes were Hacked Who didn't check "c(i)-c(i-1) <= p(i)-p(i-1)" this condition

In pretest , one testcase is missing and many codes are hacked for that particular testcase. (Those codes were Hacked Who didn't check "c(i)-c(i-1) <= p(i)-p(i-1)" this condition) Testcase : 1 2 4 1 5 3

I'm confused because I failed pretest 2 when I didn't check

`c[i]-c[i-1] <= p[i]-p[i-1]`

, and adding that line was the only change to get acYou got wrong answer because you didn't check

`if c[i] >c[i-1] then p[i] > p[i-1]`

but only checked independently that two array should be non decreasing so that's where you got wrong answer not because of`c(i) - c(i-1) <= p(i) - p(i-1)`

Does Educational Codeforces Round has FST after hack?

Yes

I get struck in recent greedy questions, but struck less in the previous ones. Why? I can't get it? Please help me with ideas and tutorials how you approach greedy problems

Today's $$$E$$$ was a bit tricky to prove.

Firstly, let's represent any number $$$x$$$ by a sequence $$$x_i$$$ where

where $$$p_i$$$ are all the $$$n$$$ primes from $$$1$$$ to $$$n$$$.

Now, observe that the weight of the edge from $$$x$$$ to $$$y$$$ will be

where $$$x = y \cdot p_k$$$. (Why ?)

Now, if we want to go from $$$u$$$ to $$$v$$$ in the graph, in each step we can either add $$$1$$$ to some $$$u_i$$$ or subtract $$$1$$$ from some $$$u_i$$$. As we want to find the shortest path, we will reduce $$$u_i$$$ by $$$1$$$ only if $$$u_i > v_i$$$ and add $$$1$$$ only if $$$u_i < v_i$$$. Also, its optimal to reduce all $$$u_i$$$ which are greater than $$$v_i$$$ before increasing any $$$u_i$$$ which are less than $$$v_i$$$. Both these statements can be proven.

Now, consider all $$$i$$$ having $$$u_i > v_i$$$. In what order would you reduce these? I claim that the order in which you reduce these doesn't matter.

ProofWe can think of this problem as a game. Given two sequences of $$$n$$$ numbers $$$a_i$$$ and $$$b_i$$$ with $$$a_i > b_i$$$ for all $$$i$$$. Initially we have a score of $$$0$$$. In one move, we can can choose some $$$i$$$ having $$$a_i > b_i$$$, reduce $$$a_i$$$ by $$$1$$$ and add $$$\prod_{j \neq i}{a_j}$$$ to our score. We continue this until both the sequences are equal. Prove that no matter the order of our moves, the final score is $$$\prod{a_i} - \prod{b_i}$$$

We can prove this by induction, let's assume that for any sequence $$$c_i$$$ having sum of all numbers $$$= k$$$, score is always $$$\prod{c_i} - \prod{b_i}$$$. So, if we have a sequence $$$a_i$$$ having sum $$$= k+1$$$, choosing any number $$$a_j$$$ will reduce the sum by $$$1$$$. Hence, the total score will be:

The base case is trivial, where $$$k = \sum{b_i}$$$ and score is $$$0 = \prod{a_i} - \prod{b_i}$$$

Thus, the number of shortest paths is the number of ways to reduce all $$$u_i > v_i$$$ to $$$v_i$$$ multiplied by number of ways to increase all $$$u_i < v_i$$$ to $$$v_i$$$.

For your proof block, there is a much simpler proof: if you go from u to w where w divides u and always step by removing a factor, the cost is just the number of factors of D that divide u but not w, regardless of the path.

Wow. Short and beautiful

That's what she said.

Yuki726 you just made my day. :D

Wow! Now, my proof looks stupid :(

I was about to start trying something like your proof, but I decided that I'm too old to enjoy grinding through that sort of maths :-)

I agree, If I am going from u to w and w divides u, then cost will be number of divisors of u — number of divisors of w.

now the cost of going from u to v trhough gcd will be: c1 = cost(u --> gcd) + cost(gcd --> v) = number of divisors of u + number of divisors of v — 2 * number of divisors of gcd

however, there is another possible path: u --> lcm --> v and its cost is: c2 = 2 * number of divisors of lcm — number of divisors of u — number of divisors of v

why is c1 always better than c2? I was not able to prove this, and I submitted a solution based on that c1 is always smaller and it got accepted.

Another proof: In any sequence of primes that got removed, we can swap adjacent primes in the sequence and the total weight of the sequence(path) doesn't change. Hence every sequence has same weight(since we can transform one sequence to other using adjacent swaps).

That's what I'm always saying when I can't figure out any nice way to prove it :)

I wrote solution for C with O(N) time and O(1) memory in Python3 but got TLE on test 3. I tried to optimize input reading and other possible bad performance cases but still have TLE.

I suppose, that it can be some I\O mistake (like input() on empty stdin) but can't even imagine, where such mistake can be in so simple python code.

76161270

Is there someone with similar problem? (Or maybe someone can find mistake in my solution?)

PS. I even try to rewrite this code in C++ (76168690), but result is the same = TLE on test 3. I definitely miss something important, but I can’t understand what exactly

Try to add these three strings in the beginning of main function:

Oh my god, it works! Thank you! Well, I will take this fact about I\O functions into account in the next competitions

It is so frustrating when you get TLE bcz you use python. Today in Problem (C) it happened with me. I think it can be avoided, like most of the times in first 4 problems, what went wrong this time, constraint seemed fine for pypy but shows TLE.

You can try using Fast IO in python.

https://codeforces.com/blog/entry/47667

I got TLE in C++ because I didn't use

`ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);`

at first.I was already doing Fast I/O, maybe because my complexity was O(nLogn). But I guess nlogn is doable in c++ but not in python

I would not call what you are using for fast IO! That is not even close to being fast. Just switching to a faster IO makes your program TLE on tc 7 instead of tc 3 76211878. Also switching the sorted(m)[0] with min(m) results in AC 76212190. If you want a drop in actual fast IO that works in general then check out https://github.com/cheran-senthil/PyRival/blob/master/templates/template_py3.py

Thanks for your help @pajenegod. I definitely learnt something new. Thanks again.

I have found two plagiarism cases in the last contest(Educational Codeforces Round 85 (Rated for Div. 2)).

Here's the submission links: https://codeforces.com/contest/1334/submission/76179771 https://codeforces.com/contest/1334/submission/76175619

They did the same crime at previous round too (Codeforces Round #632 (Div. 2)). https://codeforces.com/contest/1333/submission/75904417 https://codeforces.com/contest/1333/submission/75907575

Ahnaf.Shahriar.Asif just copied the code from Shafin_Ahmed and added some extra lines to avoid plagiarism checkers.So we can call it plagiarismforces. Kids should get some education from it :p .

"Educational" is not in the process of solving problems, is in the hacking phase. Especially,in Problem A.

[submission:https://codeforces.com/contest/1334/submission/76137503]

I cannot understand any of DreamLolita submission. Someone please explain it?

MikeMirzayanov Please review this account DreamLolita and its submissions.

Is he a robot?

I think it's a violation of Codeforces Contest Rules and the participant should be punished:

In C if i declare input arrays as global array it does n't give TLE.else it gives tle. TLE: 76195191 76196229

Because if you declare array locally space will be allocated for each testcase that will consume additional o(n) time.

But mine got accepted even if i use local array .76145135

for every test case, your array size is N, not n

I didn't get what you want to say ?

in the solve function, which is called every test case, it's allocate array with size N, which is 300007

so the total is T*N = 150000 * 300007

if it's only allocate the necessary size, which is n, it's guaranteed the total n in all test cases does not exceed 300000

make it a global with size N is also ok, because only allocate it once, not every test case

is this solution correct ?

Solution to problem G:

Similar to this problem, we define the distance between two strings A and B of length $$$n$$$ as follows:

Then we can see that when $$$A$$$ is $$$s$$$ and $$$B$$$ is a substring of $$$t$$$, $$$B$$$ is an occurrence of $$$A$$$ if and only if $$$\operatorname{dist}(A,B)=0$$$. However, in this problem, we want to know $$$\operatorname{dist}(s, t[j:j+|s|])$$$ for all $$$j$$$-s. To do this, we can expand the formula a little:

Note that the first and last terms only have to do with on $$$j+i$$$ or $$$i$$$, so they can be easily calculated in $$$O(1)$$$ with prefix sums. The three terms in the middle are related to both $$$i$$$ and $$$j+i$$$, but if we reverse string $$$s$$$, it will only depend on $$$-i$$$ and $$$j+i$$$. To solve for all $$$j$$$-s, it turns out to be a typical FFT problem. So the whole task can be solved with 3 polynomial multiplications, which is fast enough to pass the time limit.

Don't forget to set $$$eps$$$ a little larger to avoid precision problems. My submission: 76170703

Complexity: $$$O(n\log n)$$$

I had a slightly simpler (but most likely slower) FFT solution. My actual submission was dangerously close to the time limit, but I've since come up with a slight modification that's faster.

For each letter c from 'a' to 'z' in turn, and for each position where S could be placed, count the number of positions where T contains c and S contains either c or p[c]. Sum these counts over all letters, and you can now tell whether each position is a match. For a given letter c, create a 0/1 array U where U[i]=1 where T[i]=c, and similar a 0/1 array V where V[i]=1 where S[|S|-1-i]=c or p[c]. Then to get the count you just convolve U with V via FFT. It's almost certainly slower than the solutions other people have described because it requires 26 convolutions, but should be fast enough.

Here is a very simple bitset solution for G, that can pass with pragmas:76287369

Can someone please tell me why am I getting TLE on this code for E

You could've pre-calculated inv modulo before queries.

Problem A systests are garbage!!!!Yeah right! There was 1006 test case overall and none contained the case where the increase in plays is less than the increase in clears. I wonder how did they put the test cases

i got hacked... still i m happy cz i got AC in C

actually pretests did contain this case. I failed pretest 2 when i didn't verify that increase in clears <= increase in plays

Well I got accepted in contest without checking for it there’s no magic going on.

weird, I also failed on pretest 2 because of that

Pretest had something like this

which you passed because of checking

`if (p[i] != p[i - 1] && c[i] != c[i - 1]) { b = false; break; }`

But it fails for this case

Yeah thank you I know that. But this does not justify the available system tests There’s only 4-5 cases to check and they couldn’t do so in 1006 tests. The number of hacked solutions for A speaks for itself.

C is educational, taught us the importance of fast IO

Can someone please check my code for problem C and tell why it is giving TLE, I think what I wrote is clearly O(n) 76183582

UPD : Used fastio and got it accepted after contest :(

I'm really mad with myself :(

I got problem E wrong (WA on Test 22), because I didn't add these two lines to my code. I would have got 101st place as well. :( if (temp > 1) primes.add(temp);

Basically, for D's such as 6 or 15, my prime list is {2} and {3} respectively, instead of {2,3} and {3,5} respectively.

Lmao, I've also had issues with this! I wrote factorization several times, and I knew I had to add "if (temp > 1)" line, but I accidentally wrote "if (temp > 0)" instead, and it took me 20 minutes and 4 attempts to fix it xD

cf predictor is not working for me anyone has the same issue?

I uninstalled it.

Держи в курсе

I like you rating graph.

From the last contest my cf predictor working again..today don't know , what will be happened. Bofore last 3 or 4 contest it was give me wrong prediction too.

Actually it takes some time to refresh . If you do a submission and immediately check cf predictor it still predict till your last submission . Check after 2-3 minutes of submission , it will predict correctly.

Almost 1/6th of the submissions of A have been hacked and its not even been 2 hours yet.

nice.

What is the hack case for C ?

For a unsuccessful hack attempt how much score reduce ? please help anyone..

No reduce, no gain.

Then if i hack other solution , no effect on my score or gain rating + point ?

No, also no gain. But the other one falls down in ranking, because one less solved. So you should hack the ones right in front of you in ranking.

In this contest no fall and no gain . generally its +100 points for successful hack and -50 points for unsuccessful hack.

For Problem C — "Circle of Monsters", is there any solution got accepted in java?. in practice, i tried the same as the top scorer "MiFaFaOvO" in java, but it says "Time limit Exceeded".

https://codeforces.com/contest/1334/submission/76208845 I think it has worst time O(nlogn) where as people have done it in O(n) but that was just lazyness and can be reduced to O(n)

are you using fast IO?

My JAVA Submission for C 76160407

You should always use fast IO in JAVA.

Timecomplexity: O(n)

Some tests for A 4 3 2 1 3 2 4 4 2 5 3 5 6 2 2 2 3 2 3 1 1 2 2 145 1

How do i see div 2 ranking on standings page? It shows div1 participants as well, even if I untick 'show unofficial'

I didn't understand this line as a result GOT wa "Note that both of the statistics update at the same time (so if the player finishes the level successfully then the number of plays will increase at the same time as the number of clears)."

Still didn't get it.

For c problem, if any person has set Max to less than 3*10^17. U can hack c. Many persons asking me,so I shared. I hacked 5 in problem C.

give me a test case only if u interested.

https://codeforces.com/contest/1334/submission/76160649

This is my link to the code for C this is in o(n) still tle in 3rd case any reason for this like if any further optimization required ?

Many codes written in c++ also got TLE due to large input/output. You can use Fast IO to avoid TLE!

try using scanf and printf instead. Want to know the reason ? try to refer this.... https://www.geeksforgeeks.org/cincout-vs-scanfprintf/

screencast of me trying to prove B and E for an hour

nice

Thanks!. i would like to confirm some this line on your problem C solution.

if(a[i] > b[p]){ ans += a[i] — b[p]; a[i] = b[p]; }

What I'm getting is that this is to find the blasts that doesn't instantly kill the i+1 monster so add a[i] — b[p] to ans as in the number of bullets it will take to kill after explosion. And after that we find the minimum of all a[i]..a[n] and add it to the ans as the starting point and we don't have to do anything anymore because the blasts will insta kill everything. Correct me if I'm wrong, and thanks for the video!

Is there any efficient way of doing the

hacking? Some people hack like a killer machine (+20, +30). Can you just tell us if there is any faster way of doing that rather than seeing hundreds of codes?Why when I want to hack a problem a message is shown "Illegal contest ID"?

The method has worked, thank you very much

Why my solution in C gets tle in test 3 https://codeforces.com/contest/1334/submission/76201302

you should have used fast input output metods.

scanf/printf??

yes, or ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

Yes scanf printf will work

Yeah I got AC. But, why?? Like cin cout isn't working but scanf and printf working. Anyway, I am facing problem on finding solution on greedy problems. How do you guys approach? Any tutorial for beginning?