By awoo, history, 14 months ago, translation,

Hello Codeforces!

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!

PARTICIPATE

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!

FILL OUT FORM

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 Retired_MiFaFaOvO 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 nGu 55:-10
5 TheScrasse 40
2405 successful hacks and 1303 unsuccessful hacks were made in total!

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 sevlll 0:16
E LJC00118 0:19
F IceWiz 0:31
G Cirno_9baka 0:25

UPD: Editorial is out

• +361

 » 14 months ago, # |   +529 .
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Codeforces the Saviour !!
•  » » » 14 months ago, # ^ | ← Rev. 4 →   +4 From Corona :D
•  » » 14 months ago, # ^ |   +25 lol the meme has more upvotes than the blog
•  » » 14 months ago, # ^ |   +3 why did you cut out the part where Codeforces suplexes us
 » 14 months ago, # |   +29 Wow!!! The last line of announcement is more likely to be said by a ROCK STAR than a university staff!!! /m/ LoL :))
 » 14 months ago, # | ← Rev. 2 →   +158
•  » » 14 months ago, # ^ | ← Rev. 2 →   +35 What if it got wrong during system testing?
•  » » » 14 months ago, # ^ |   +16 Maybe kill codeforces ;D
•  » » » 14 months ago, # ^ |   0 You don't have to do anything, just wait for next contest
•  » » » 14 months ago, # ^ |   +5 then you'd better warn Mike ;)
•  » » 14 months ago, # ^ |   +60 When you hack your own solution
•  » » » 14 months ago, # ^ |   0 is it allowed? i tried to do so but some error message popped
•  » » » » 14 months ago, # ^ |   0 Your test was incorrect
•  » » » » » 14 months ago, # ^ |   0 No. That hacking window didnt open when I tried. I knew case where my solution failed
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +11
•  » » » 14 months ago, # ^ |   +13 Exactly how I felt haha
•  » » » » 14 months ago, # ^ |   -9 If you hack yourself succesfully, you would get 100 points from hacking while losing point from the task right ?
•  » » » » » 14 months ago, # ^ |   +7 It's educational round, hacking happens after the contest ended, there are no points here.
•  » » » » » » 14 months ago, # ^ |   -9 oh, ok
 » 14 months ago, # |   -66 I really hope there will be problems about COVID-19 and quarantine.
 » 14 months ago, # | ← Rev. 2 →   +90 Before reload Oh there are No contests after it After reload Oh What can I do with these contests
•  » » 14 months ago, # ^ | ← Rev. 2 →   +47 Its raining contests.
•  » » 14 months ago, # ^ |   +6 Hope to be a good week for everyone and high rate <3
•  » » 14 months ago, # ^ |   +8 vovuh is ready with div3
 » 14 months ago, # |   +10 I hope the problem statements will not be long
•  » » 14 months ago, # ^ |   -14 why?
•  » » » 14 months ago, # ^ |   +13 Because long statements are more hard to understand, and it feels not right to have language difficulties in a programing contest.
•  » » 14 months ago, # ^ |   -11 I hope some day people will stop writing stupid comments
 » 14 months ago, # | ← Rev. 2 →   +139
 » 14 months ago, # | ← Rev. 4 →   -47 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!
•  » » 14 months ago, # ^ |   +28 All the people who have downvoted my comment, I WILL PROVE THEM WRONG!!
•  » » » 14 months ago, # ^ |   0 ok
•  » » » 14 months ago, # ^ |   +13 You cant go from specialist to master in one contest lol
•  » » » 14 months ago, # ^ |   0 ok
•  » » » 14 months ago, # ^ |   +4 I meant expert, I got confused between expert and master lol
•  » » » » 14 months ago, # ^ |   +1 Good luck mate, I am going to be an Expert during the quarantine too <3
 » 14 months ago, # | ← Rev. 2 →   -14 Hope the best for everyone <3
•  » » 14 months ago, # ^ |   +9 It's probably been said a 100 times before: Hope is a dangerous thing. Hope can drive a man insane.
•  » » » 14 months ago, # ^ |   +13 Ok , wish the best for everyone *_*
•  » » » 14 months ago, # ^ |   0 Hope is a good thing, probably the best.
•  » » 14 months ago, # ^ |   0 I want the best for everyone and high rate for them , and they downvoted on my comment !!!!!!!!!!!!!!!!!!
•  » » » 14 months ago, # ^ |   +11 Have you considered the thought I want everyone low rating so it boosts my rating higher? :smirk:
 » 14 months ago, # |   +108
 » 14 months ago, # |   -12 Hoping for no queueforces and strong pretests!
 » 14 months ago, # | ← Rev. 2 →   -22 Hoping for strong pretests
 » 14 months ago, # |   0 A lot of people enjoy some applications at home, but we enjoy with codeforces forever <3
 » 14 months ago, # |   0
•  » » 14 months ago, # ^ | ← Rev. 2 →   +14 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?
•  » » » 14 months ago, # ^ |   0 Yeah
•  » » » 14 months ago, # ^ |   +16 Yes, killing the ones right in front of you is sufficient.
 » 14 months ago, # |   -26 Is it Rated??
•  » » 14 months ago, # ^ |   -12 it says, it is rated for participants with rating lower than 2100. so for you, yes its rated.
 » 14 months ago, # |   +5 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 :-)
•  » » 14 months ago, # ^ | ← Rev. 2 →   +9 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.
•  » » » 14 months ago, # ^ |   0 Thanks yash, it was helpul :-)
 » 14 months ago, # |   0 Your photo is so cute.
 » 14 months ago, # |   0 Desperately waiting for the contest
 » 14 months ago, # |   0 Me: Codeforces is the savior from boredom. Meanwhile Codeforces : Sometimes it feels, I am the GOD...
•  » » 14 months ago, # ^ |   +17 Sacred Games!!!
 » 14 months ago, # |   +7 good luck all))
 » 14 months ago, # | ← Rev. 2 →   0 .
 » 14 months ago, # | ← Rev. 2 →   -37 I've never seen a contest with so poor input examples
•  » » 14 months ago, # ^ |   +1 How do you know tests are poor?
•  » » » 14 months ago, # ^ |   0 I said it wrong. By pretests I actually meant the input examples.
 » 14 months ago, # |   0 Beautiful Problems, thanks awoo
 » 14 months ago, # |   0 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?
•  » » 14 months ago, # ^ |   0 Solve tasks from here
•  » » » 14 months ago, # ^ |   0 What's so great about it?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 14 months ago, # ^ |   0 Thanks!
•  » » 14 months ago, # ^ |   0 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' ......
 » 14 months ago, # |   -46 Hardest Div2 C I have ever seen.
•  » » 14 months ago, # ^ |   +5 See 631 Div2 That was more harder than this one!
•  » » 14 months ago, # ^ |   +38 I thought it was super hard for a long time before I realized the explosions only hurt the monster in one direction
•  » » » 14 months ago, # ^ |   -9 Yeah, me too, but then it still was hard to implement, IMO.
•  » » » » 14 months ago, # ^ |   0 nah the implimentation was very easy look at my solution https://codeforces.com/contest/1334/submission/76178082
•  » » » » 14 months ago, # ^ |   0 76131257 Boilerplate and input aside, the actual solution has 10 lines.
•  » » » » » 14 months ago, # ^ |   0 Hey nice solution, Can you explain me this why are you adding "best" to "cnt" arent we counting it twice? Thanks.
•  » » » » 14 months ago, # ^ |   +6 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).
•  » » » 14 months ago, # ^ |   +13 What if the question was like "Explosions hurt both the adjacent monsters"? How will we solve it?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 You do chain reactions(explosions) in two half circles starting from the monster with least health, I guess?
 » 14 months ago, # | ← Rev. 2 →   +16
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 for D also
 » 14 months ago, # |   +1 Any hints for C?
•  » » 14 months ago, # ^ |   0 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
•  » » 14 months ago, # ^ |   +3 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;
•  » » 14 months ago, # ^ |   0 Thank you for your video solution. I can sleep comfortably....
•  » » 14 months ago, # ^ |   0 just above you
 » 14 months ago, # |   +9 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.
•  » » 14 months ago, # ^ |   +30 You can factorize $D$ in $\mathcal{O}(\sqrt{D})$ :)
•  » » » 14 months ago, # ^ |   +17 You can loop upto 3*10^7? I thought you couldn't go beyond O(10^5-6) operations ;(
•  » » » » 14 months ago, # ^ |   +16 You can go up to around 3*10^8 operations lmao.
•  » » » » 14 months ago, # ^ |   0 Wow, how did you even reach Candidate Master without knowing this?
•  » » » » » 14 months ago, # ^ |   0 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.
•  » » 14 months ago, # ^ | ← Rev. 4 →   0 nvm I misread your comment.
•  » » » 14 months ago, # ^ |   0 Do we have to make graph or is there any other trick because most of people doesn't used much space?
•  » » » » 14 months ago, # ^ |   +9 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.
 » 14 months ago, # |   +50 The person in first place made his code obscure, that is a violation of the rules
•  » » 14 months ago, # ^ |   +34 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)
•  » » 14 months ago, # ^ |   0 Obscured by using an algorithm template? :thinking:
•  » » » 14 months ago, # ^ |   +4 I meant first place in official standings, DreamLolita. Here is one of his submissions 76166237
•  » » » » 14 months ago, # ^ |   +1 Oh my bad. Yeah that's definitely obscured code.
•  » » » » 14 months ago, # ^ |   0 OMG! this is C++ beyond my thinking, what this guy has done
 » 14 months ago, # |   0 got TLE on question A , in aprogram with O(n) time complexity , question A and B were easy but with strong test case
•  » » 14 months ago, # ^ |   +3 Well if you got tle it means your program wasn't O(n)
•  » » » 14 months ago, # ^ |   +5 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 mulfunctioned
•  » » 14 months ago, # ^ |   0 Read all of the input for a tc, even when you have conclude on the answer
•  » » » 14 months ago, # ^ |   0 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 .
•  » » 14 months ago, # ^ |   +1 iamxlr8 A with strong test case?
 » 14 months ago, # |   +8 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?
•  » » 14 months ago, # ^ |   +5 4 1 3 3 7 8 7 9 10 7 113 5 0 -2 5 3 6 7 8 2 4
 » 14 months ago, # |   +80
•  » » 14 months ago, # ^ | ← Rev. 2 →   -19 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.
•  » » » 14 months ago, # ^ |   +34 Code obfuscation is not allowed, for good reasons. This kind of code is more or less unhackable.
•  » » 14 months ago, # ^ |   +16 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.
•  » » » 14 months ago, # ^ |   0 Yeah, I know) Because of this I decided to read his submissions
•  » » 14 months ago, # ^ |   -8 Can you please tell just basics..what he has written. I was unable to understand
•  » » » 14 months ago, # ^ |   0 I don't know, it's unreadable for me
 » 14 months ago, # |   0 Any hints for D? I used OEIS Sequence but got WA on test 2.
•  » » 14 months ago, # ^ | ← Rev. 6 →   +15 You can start creating a path like 1 2 1 3 1 4...1 n 1 Then, insert after the n, but before the last 1 2 3 2 4 2 5...2 n 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)
•  » » 14 months ago, # ^ |   +5 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.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +3 A general hint for any problem: If you don't know how to solve it, implement backtracking, maybe you notice a pattern.
•  » » » 14 months ago, # ^ |   0 What's bkt?
•  » » » » 14 months ago, # ^ |   0 maybe his bkt ~ bruteforce
•  » » » » 14 months ago, # ^ |   0 Stands for backtracking (i.e. brute-force), I thought everyone abbreviated it like that :D. I modified my comment.
•  » » 14 months ago, # ^ |   0 Wow I was also able to find this but WA on pretest2
 » 14 months ago, # | ← Rev. 2 →   +4
•  » » 14 months ago, # ^ |   -14 Same with Me I wasn't able to solve A :(
 » 14 months ago, # |   +8 What was test case 2 in D?
 » 14 months ago, # |   0 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?
•  » » 14 months ago, # ^ |   0 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]).
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 $i$ with $min(a[i], b[i - 1])$ is the optimal start.
•  » » » » 14 months ago, # ^ |   0 got it! thanks
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 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]))"
 » 14 months ago, # |   0 Can anyone tell me the complexity of Problem C?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 It is $O(n)$ 76190446
•  » » » 14 months ago, # ^ |   0 Then why it is showing TLE on my soln
•  » » » » 14 months ago, # ^ |   +1 you should have used fast input output.
•  » » » » » 14 months ago, # ^ |   0 my bad ..i forgotten to call
 » 14 months ago, # | ← Rev. 2 →   +23 Can you imagine the feeling of finding the mistake 2 minutes after the contest end?I feel really great!
•  » » 14 months ago, # ^ |   +5 Haha, I feel ya fam! Just keep going, we shall bleed red :)
 » 14 months ago, # |   0 Can somebody Explain why this solution using binary search is wrong (Problem C )?? Submission link
 » 14 months ago, # |   -19 This C is so hard lol while D is braindead.
 » 14 months ago, # | ← Rev. 2 →   +1 Problem C: Idleness limit exceeded on test 3. Note: this is not TLE (time limit), but idleness 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).
•  » » 14 months ago, # ^ |   0 same problem occured with me too my solution was of O(N) still got TLE
•  » » » 14 months ago, # ^ |   0 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.
•  » » 14 months ago, # ^ |   0 Try removing those print()s and submit 76193796. It turned to TLE.
•  » » » 14 months ago, # ^ |   0 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?
 » 14 months ago, # |   +12 What is hack case in problem A?
•  » » 14 months ago, # ^ |   +5 1 2 100 50 101 99
•  » » » 14 months ago, # ^ |   0 answer is yes or no?
•  » » » » 14 months ago, # ^ |   +57 Hacked your solution :P
•  » » » » » 14 months ago, # ^ |   -9 You could've just said yes or no..now don't hack mine.
•  » » » » » 14 months ago, # ^ |   0 I thought the day the finally come when I solved 3 questions in Div.2 Contest.
•  » » » » » » 14 months ago, # ^ |   0 Sorry, no hard feelings bro.
•  » » » » » » » 14 months ago, # ^ | ← Rev. 2 →   +17 No issue would have failed System Testing in end.This is Hard Life after All
•  » » » » » » » » 14 months ago, # ^ |   +4 Keep coding, you will manage to get it after soon days.
•  » » » 14 months ago, # ^ |   0 Thanks!
•  » » 14 months ago, # ^ |   +2 T = 1 N = 2 1st pair : 4 1 2nd pair : 5 3
 » 14 months ago, # |   0 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:)
•  » » 14 months ago, # ^ |   0 use scanf and printf instead of cin and cout. Or use faster input/output. Same thing happened with me also.
•  » » » 14 months ago, # ^ |   +3 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 :)
•  » » 14 months ago, # ^ |   0 don't use endl, just use "\n"http://www.cplusplus.com/reference/ostream/endl/
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I think you are facing the same issue as I have mentioned here.
 » 14 months ago, # |   0 how to solve F and G?
 » 14 months ago, # |   +5 Is there anyone whose same solution for div2C get TLE in python but get accepted in c++ ?
•  » » 14 months ago, # ^ |   +20 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 language
•  » » » 14 months ago, # ^ |   0 Sad!!!
 » 14 months ago, # |   0 Can anyone explain why am I getting TLE on test case 3 for problem C? My solution — https://codeforces.com/contest/1334/submission/76172390
•  » » 14 months ago, # ^ |   +8 maybe you are using endl instead of \n
•  » » 14 months ago, # ^ |   +3 I submitted an O(n) solution on Python, it got TLE on test case 3: https://codeforces.com/contest/1334/submission/76161837I rewrote that solution to C++, it got TLE on test case 3: https://codeforces.com/contest/1334/submission/76185611I 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/76187533
 » 14 months ago, # |   0 G: 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.
•  » » 14 months ago, # ^ |   +8 you can use bitset :D
•  » » » 14 months ago, # ^ |   0 does bitset actually pass? I didn't try it because I thought it would be $26n^2/64$
•  » » » » 14 months ago, # ^ |   +8 i used pragma also.
 » 14 months ago, # |   -8 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 ?
•  » » 14 months ago, # ^ |   +1 You should take subsegment from l to r(inclusive) from sequence of the cycle(1,2,1,3,2,3,1)
•  » » » 14 months ago, # ^ |   0 Ahhh, lol, it is used this way. Thanks!
 » 14 months ago, # |   0 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 .
•  » » 14 months ago, # ^ | ← Rev. 24 →   0 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.
 » 14 months ago, # |   0 76190416 can anyone explain why in problem C , TLE occured in my code. I think the time complexity is O(N)
•  » » 14 months ago, # ^ |   +1 try fast io . ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
•  » » » 14 months ago, # ^ |   0 is there a soln to C using Binary search ?
•  » » » 14 months ago, # ^ |   0 it worked using this line struct {(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}_
 » 14 months ago, # |   +11 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 statesValidator '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?
•  » » 14 months ago, # ^ |   0 +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?
•  » » 14 months ago, # ^ |   +26 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.
 » 14 months ago, # |   0 7618473176186776and here are the cheaters of the day please take some action against such people
 » 14 months ago, # |   0 He's back. 76138708 , 76144561 , 76160631
 » 14 months ago, # |   +1 Going live on YouTube explaining A, B, C: https://youtu.be/FDbd_sYP7hM
•  » » 14 months ago, # ^ |   0 Great tutorials man. I like your style! I will watch if you have D-F tutorials :D
 » 14 months ago, # | ← Rev. 2 →   +103 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.
•  » » 14 months ago, # ^ |   -16 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.
•  » » 14 months ago, # ^ |   0 (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.
•  » » » 14 months ago, # ^ |   0 My dp solution passed :) 76192690
•  » » » 14 months ago, # ^ |   0 https://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_unique_permutations_of_wordsThink about how this problem is fundamentally the same.
•  » » 14 months ago, # ^ |   0 My B got hacked even though I did the same :(
•  » » 14 months ago, # ^ |   0 https://codeforces.com/contest/1334/submission/76120878 The link for problem B
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 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!)?
•  » » 14 months ago, # ^ |   0 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?
•  » » » 14 months ago, # ^ |   0 Yes. You want to waste the least.
 » 14 months ago, # |   -20 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
•  » » 14 months ago, # ^ |   +1 The problemstatement says there are up to 300000 monsters, each data on one line, each two integers.Fast IO is a really basic thing.
 » 14 months ago, # |   +2 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.
 » 14 months ago, # |   +11 Pretests for problem A are too weak..
•  » » 14 months ago, # ^ |   0 Yes..I Agree!
•  » » 14 months ago, # ^ |   +4 Particularly,Those codes were Hacked Who didn't check "c(i)-c(i-1) <= p(i)-p(i-1)" this condition
 » 14 months ago, # |   +12 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
•  » » 14 months ago, # ^ |   0 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 ac
•  » » » 14 months ago, # ^ |   0 You 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)
 » 14 months ago, # |   +6 Does Educational Codeforces Round has FST after hack?
•  » » 14 months ago, # ^ |   +3 Yes
 » 14 months ago, # |   0 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
 » 14 months ago, # |   +35 Today's $E$ was a bit tricky to prove.Firstly, let's represent any number $x$ by a sequence $x_i$ where $x = \prod_{i = 1}^{n}{{p_i}^{x_i - 1}}$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 $w(x, y) = \frac{\prod_{i = 1}^{n}{y_i}}{y_k}$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: $\text{score} = \prod_{i \neq j}{a_i} + ((a_j - 1) \cdot \prod_{i \neq j}{a_i} - \prod{b_i}) = \prod{a_i} - \prod{b_i}$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$.
•  » » 14 months ago, # ^ |   +74 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.
•  » » » 14 months ago, # ^ |   0 Wow. Short and beautiful
•  » » » » 14 months ago, # ^ |   +82 That's what she said.
•  » » » » » 14 months ago, # ^ |   +10 Yuki726 you just made my day. :D
•  » » » 14 months ago, # ^ |   +11 Wow! Now, my proof looks stupid :(
•  » » » » 14 months ago, # ^ |   +72 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 :-)
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 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 gcdhowever, 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 vwhy 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.
•  » » 14 months ago, # ^ |   +19 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).
•  » » 14 months ago, # ^ |   +32 Both these statements can be proven. That's what I'm always saying when I can't figure out any nice way to prove it :)
 » 14 months ago, # |   -15 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.76161270Is 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
•  » » 14 months ago, # ^ |   +2 Try to add these three strings in the beginning of main function: ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
•  » » » 14 months ago, # ^ |   0 Oh my god, it works! Thank you! Well, I will take this fact about I\O functions into account in the next competitions
 » 14 months ago, # |   -8 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.
•  » » 14 months ago, # ^ |   0 You can try using Fast IO in python.https://codeforces.com/blog/entry/47667I got TLE in C++ because I didn't use ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); at first.
•  » » » 14 months ago, # ^ |   0 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
•  » » » » 14 months ago, # ^ |   +9 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
•  » » » » » 14 months ago, # ^ |   0 Thanks for your help @pajenegod. I definitely learnt something new. Thanks again.
 » 14 months ago, # | ← Rev. 3 →   +12 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/76175619They 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/75907575Ahnaf.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 .
 » 14 months ago, # | ← Rev. 2 →   0 "Educational" is not in the process of solving problems, is in the hacking phase. Especially,in Problem A.
 » 14 months ago, # |   +29 [submission:https://codeforces.com/contest/1334/submission/76137503]I cannot understand any of DreamLolita submission. Someone please explain it?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +79 MikeMirzayanov Please review this account DreamLolita and its submissions.
•  » » 14 months ago, # ^ |   0 Is he a robot?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +70 I think it's a violation of Codeforces Contest Rules and the participant should be punished: 4. 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.
 » 14 months ago, # |   0 In C if i declare input arrays as global array it does n't give TLE.else it gives tle. TLE: 76195191 76196229
•  » » 14 months ago, # ^ |   0 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
•  » » 14 months ago, # ^ |   +3 for every test case, your array size is N, not n
•  » » » 14 months ago, # ^ |   0 I didn't get what you want to say ?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   +1 in the solve function, which is called every test case, it's allocate array with size N, which is 300007so the total is T*N = 150000 * 300007if it's only allocate the necessary size, which is n, it's guaranteed the total n in all test cases does not exceed 300000make it a global with size N is also ok, because only allocate it once, not every test case
 » 14 months ago, # |   0
 » 14 months ago, # |   +53 Solution to problem G:Similar to this problem, we define the distance between two strings A and B of length $n$ as follows: \begin{aligned} \operatorname{dist}(A,B)=\sum\limits_{i=1}^{m} (A_i - B_i)^2 \cdot (p_{A_i}-B_i)^2 \end{aligned}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: \begin{aligned} \operatorname{dist}(s,t[j:j+|s|])=\sum\limits_{i=1}^{m} \text{ } &t_{j+i}^4 - 2(s_i+p_{s_i}) t_{j+i}^3 + (s_i^2+4s_i p_{s_i} + p^2_{s_i}) t_{j+i}^2 \\ & - 2s_i p_{s_i} (s_i+p_{s_i}) t_{j+i} + s_i^2 p^2_{s_i} \end{aligned}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: 76170703Complexity: $O(n\log n)$
•  » » 14 months ago, # ^ |   +13 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.
•  » » 14 months ago, # ^ |   0 Here is a very simple bitset solution for G, that can pass with pragmas:76287369
 » 14 months ago, # | ← Rev. 2 →   0 Can someone please tell me why am I getting TLE on this code for E
•  » » 14 months ago, # ^ |   +13 You could've pre-calculated inv modulo before queries.
 » 14 months ago, # |   +54 Problem A systests are garbage!!!!
•  » » 14 months ago, # ^ |   +25 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
•  » » » 14 months ago, # ^ |   -8 i got hacked... still i m happy cz i got AC in C
•  » » » 14 months ago, # ^ |   0 actually pretests did contain this case. I failed pretest 2 when i didn't verify that increase in clears <= increase in plays
•  » » » » 14 months ago, # ^ |   +8 Well I got accepted in contest without checking for it there’s no magic going on.
•  » » » » » 14 months ago, # ^ |   0 weird, I also failed on pretest 2 because of that
•  » » » » » 14 months ago, # ^ | ← Rev. 3 →   0 Pretest had something like this 5 2 5 3 which you passed because of checkingif (p[i] != p[i - 1] && c[i] != c[i - 1]) { b = false; break; }But it fails for this case 5 2 6 4 
•  » » » » » » 14 months ago, # ^ |   +3 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.
 » 14 months ago, # |   +17 C is educational, taught us the importance of fast IO
 » 14 months ago, # | ← Rev. 2 →   0 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) 76183582UPD : Used fastio and got it accepted after contest :(
 » 14 months ago, # |   0 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);
•  » » 14 months ago, # ^ |   0 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.
•  » » 14 months ago, # ^ |   0 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
 » 14 months ago, # |   +1 cf predictor is not working for me anyone has the same issue?
•  » » 14 months ago, # ^ |   +1 I uninstalled it.
•  » » » 14 months ago, # ^ |   +1 Держи в курсе
•  » » » » 14 months ago, # ^ |   0 I like you rating graph.
•  » » 14 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 14 months ago, # ^ |   +1 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.
 » 14 months ago, # | ← Rev. 3 →   +9 Almost 1/6th of the submissions of A have been hacked and its not even been 2 hours yet.nice.
 » 14 months ago, # |   +33
 » 14 months ago, # | ← Rev. 2 →   +7 What is the hack case for C ?
 » 14 months ago, # |   0 For a unsuccessful hack attempt how much score reduce ? please help anyone..
•  » » 14 months ago, # ^ |   0 No reduce, no gain.
•  » » » 14 months ago, # ^ |   0 Then if i hack other solution , no effect on my score or gain rating + point ?
•  » » » » 14 months ago, # ^ |   0 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.
•  » » » » 14 months ago, # ^ |   +1 In this contest no fall and no gain . generally its +100 points for successful hack and -50 points for unsuccessful hack.
 » 14 months ago, # |   0 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".
•  » » 14 months ago, # ^ | ← Rev. 2 →   +3 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)
•  » » 14 months ago, # ^ |   0 are you using fast IO?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 My JAVA Submission for C 76160407 You should always use fast IO in JAVA. Timecomplexity: O(n)
 » 14 months ago, # |   +1 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
 » 14 months ago, # |   +8 How do i see div 2 ranking on standings page? It shows div1 participants as well, even if I untick 'show unofficial'
 » 14 months ago, # |   0 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.
 » 14 months ago, # | ← Rev. 2 →   +13 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.
•  » » 14 months ago, # ^ |   0 give me a test case only if u interested.
 » 14 months ago, # |   0 https://codeforces.com/contest/1334/submission/76160649This 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 ?
•  » » 14 months ago, # ^ |   0 Many codes written in c++ also got TLE due to large input/output. You can use Fast IO to avoid TLE!
•  » » 14 months ago, # ^ |   0 try using scanf and printf instead. Want to know the reason ? try to refer this.... https://www.geeksforgeeks.org/cincout-vs-scanfprintf/
 » 14 months ago, # |   +25 screencast of me trying to prove B and E for an hour
•  » » 14 months ago, # ^ |   0 nice
•  » » 14 months ago, # ^ |   0 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!
 » 14 months ago, # | ← Rev. 2 →   0 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?
 » 14 months ago, # |   +4 Why when I want to hack a problem a message is shown "Illegal contest ID"?
•  » » 14 months ago, # ^ |   0 If you click on "hack it" it will show you "illegal contest ID". Follow this way, Open his solution and click on '#' button (Right Corner) then there is button "hack it" click on that you can hack from there.
•  » » » 14 months ago, # ^ |   0 The method has worked, thank you very much
 » 14 months ago, # | ← Rev. 2 →   0 Why my solution in C gets tle in test 3 https://codeforces.com/contest/1334/submission/76201302
•  » » 14 months ago, # ^ |   0 you should have used fast input output metods.
•  » » » 14 months ago, # ^ |   0 scanf/printf??
•  » » » » 14 months ago, # ^ |   0 yes, or ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
•  » » » » 14 months ago, # ^ |   0 Yes scanf printf will work
•  » » » » » 14 months ago, # ^ |   0 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?
•  » » » » » » 14 months ago, # ^ |   +2 You can start by solving B problems or questions whose rating is between 1200 to 1500 in codeforces and has a tag greedy. From that, you can easily learn about how greedy works.
•  » »