Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By pikmike, history, 10 days 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 Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Geothermal 7 130
2 ksun48 7 143
3 300iq 7 147
4 vepifanov 7 168

Congratulations to the best hackers:

Rank Competitor Hack Count
1 EduPeres 40
2 Grey_Matter 39:-3
3 lx430621 26:-1
4 killa_vanilla 25:-5
5 checkingagain 17:-1
351 successful hacks and 375 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Geothermal 0:01
B ksun48 0:01
C ksun48 0:03
D Noureldin 0:09
E Geothermal 0:22
F ElOrdyh 0:15
G dario2994 0:29

UPD: Editorial is out

• +535

 » 10 days ago, # |   +335
•  » » 10 days ago, # ^ |   +72 The best educator of them all!
•  » » » 8 days ago, # ^ |   -14 Check out video solutions to A,B,C,D
•  » » » » 8 days ago, # ^ |   -8 Thanks, it is helpful <3 :)
•  » » » 8 days ago, # ^ |   0 Check out the detailed explanations of:Problem EProblem DProblem CProblem BProblem A
•  » » 10 days ago, # ^ | ← Rev. 2 →   -46 edited : I dont know why this comment got so many dislikes.. Anyways, hope u are having a nice day
•  » » 10 days ago, # ^ |   +33 Unfortunately, I am not sure that vovuh is back :(This group of people is always the creators of Educational Codeforces Rounds. For example, you can check the last one -> vovuh was among them, but was not mentioned in the tutorialHe also said he would return with a div 3 round in this comment
•  » » » 9 days ago, # ^ |   +26 He is coming with a DIV.3 round :)
•  » » » » 9 days ago, # ^ |   +12 why vovuh is popular ?
•  » » » » » 8 days ago, # ^ |   0 For standard Div.3 rounds :)
•  » » » 9 days ago, # ^ |   +203
•  » » » 8 days ago, # ^ |   0 (From this contest editorial)
•  » » 9 days ago, # ^ | ← Rev. 2 →   -31 I'm done with memes. No more memes from now!
•  » » 8 days ago, # ^ |   +22 Still waiting for official Editorials. Problem setters should make editorials along with problems.
•  » » » 8 days ago, # ^ |   -7 Hey vivek21Check out the detailed explanations of:Problem EProblem DProblem CProblem BProblem AI am sure you will like the explanations
 » 10 days ago, # |   -38 oh! Vovuh back!!
 » 10 days ago, # |   -60 yeahhh!! vovuh....big fan...so much excited!!
 » 10 days ago, # |   0 can somebody explain me the way of scoring in educational rounds? I think you will only get scores due to the number of solved problems regardless of their difficulty. am I right?
•  » » 10 days ago, # ^ |   +8 Yes. How many AC, then how many minutes (penalty).
•  » » » 10 days ago, # ^ |   0 And bye how many minutes do you mean the total time spent to achieve the score or in some other way?
•  » » » » 10 days ago, # ^ |   +7 If you solved any problem in 40 minutes.Then your penalty+=40.and every wrong answer penalty+=10 Generally..If both solved same no of problem then standing will be sorted with penalty.
•  » » » » » 9 days ago, # ^ |   -20 algorithmic reply...lol
•  » » » » » » 9 days ago, # ^ |   +1 I did not find any "lol" thing here
•  » » 10 days ago, # ^ |   0 Good to know, I have participated in a few educationals but did not know this one. :O What I noticed about them is that they tend to be harder than normal Div2 rounds.
•  » » » 10 days ago, # ^ |   0 Yes.I thought that too
•  » » » 9 days ago, # ^ |   -8 Can you please tell what's the difference between educational and div-2 round? I'm new here.
•  » » » » 9 days ago, # ^ |   +10 **Educational round 1.Here only have penalties.here a wrong submission give you +10 penalty.you solved a ques in 20 minutes with 1 wrong submission .then penalty is (20(in 20 minutes you solved that)+10(for 1 wrong submission))=30. 2.Standing firstly sorted by no of problem solved..if that same then penalty(whose penalty less he/she go up than others) . **Div 2 1.Every problem have a score and you can gain the score by solved that.Time going and every problem score slightly(2/4/6 per minutes) decrease..and a wrong submission decrease of that problem score by 50. 2.Standing sorted by your gained score. 
 » 10 days ago, # |   0 codeforces is the best
 » 10 days ago, # |   +385
•  » » 10 days ago, # ^ |   +120 which means
•  » » 8 days ago, # ^ |   0 Same condition for the Tutorials too!!
 » 10 days ago, # | ← Rev. 2 →   -131
•  » » 10 days ago, # ^ |   +101 ![ ]()a
•  » » 10 days ago, # ^ |   +25 Seem like an Educational round's announcement is incomplete without someone reposting this meme.
 » 10 days ago, # | ← Rev. 2 →   +4 Just curious, in educational rounds announcement, why its mostly written like "6 or 7 problems". Is the number of problems and problems itself not decided till few hours before the contest? Or is there something, which I am unaware of?
•  » » 10 days ago, # ^ |   +17 I think entire blog is almost copy pasted, maybe so
 » 10 days ago, # |   +605
•  » » 10 days ago, # ^ |   +67 Typical Indian households
•  » » » 9 days ago, # ^ |   -26 fucked up my contest today, couldn't solve even one question.
•  » » » » 9 days ago, # ^ |   +3 Sonic_Master Everyone has their bad days. :) What matters most is you upsolve those problems.
•  » » 10 days ago, # ^ |   +25 True AF
•  » » 10 days ago, # ^ |   +32 That's why it seems peaceful to do contest in hostel room.
•  » » » 9 days ago, # ^ |   +38 If you feel peaceful to do a contest in hostel room, you got no hostel life probably.
•  » » » » 9 days ago, # ^ |   +27 Possible if and only if all roommates are contest programmer.
•  » » 10 days ago, # ^ |   +10 Damn, right in the feels.
•  » » 9 days ago, # ^ |   +1 It's way better than what I experience almost every time.
•  » » 9 days ago, # ^ |   +25 Or when they don't talk to you for the entire day, but the moment your contest starts, they decide to hold a party in your room.
•  » » 9 days ago, # ^ |   +1 So true, XD
•  » » 8 days ago, # ^ |   0 xswl
 » 10 days ago, # | ← Rev. 2 →   -30 :D
•  » » 9 days ago, # ^ |   -12 HTML IS A PROBRAMMING LANGLUAGE!
•  » » » 9 days ago, # ^ |   -14 It's a hyper text MARKUP language.
•  » » » 9 days ago, # ^ |   +59 Nikita will leave you
•  » » » » 8 days ago, # ^ | ← Rev. 2 →   0 ha ha ha
•  » » » » » 8 days ago, # ^ | ← Rev. 2 →   0 we should have HTML in code forces.
•  » » » 7 days ago, # ^ |   +5 and the earth is flat
 » 10 days ago, # |   +6 Pretty excited for this contest !!
 » 9 days ago, # |   +176 ![ ]()
 » 9 days ago, # |   +121
•  » » 9 days ago, # ^ |   -14 hhhhhhhhhhhh, Let's become a Legendary Grandmaster :v ;)
 » 9 days ago, # |   -18 hope to get a decent rank this time
 » 9 days ago, # |   +25 I have one question!, Know the Educational rounds are more than the div1 and most of the Educational rounds have 6 or 7 problems It is a good idea to add one hard problems and make educational to div1 ? :)
•  » » 9 days ago, # ^ |   -25 Good idea, but they wont accept. We are doomed =(
•  » » » 9 days ago, # ^ |   +5 But there may be room for discussion. :|
•  » » » » 9 days ago, # ^ |   -15 Of course. I would be so happy if they accept.
•  » » 9 days ago, # ^ |   -24 pikmike please get a answer
•  » » 9 days ago, # ^ | ← Rev. 3 →   +16 Educational round is nice but div1 contest is rated for 2100 <= and it is a Competitive for 2100 <=
 » 9 days ago, # | ← Rev. 3 →   +57 When I find People Cheating in Rated Rounds
•  » » 9 days ago, # ^ |   +6 But after seeing that there code are same even comments are same my heart like "OOOH LALA";)
 » 9 days ago, # | ← Rev. 2 →   -26 Excited for vovuh div2 round after a long time.
 » 9 days ago, # |   +10 Good luck everyone
 » 9 days ago, # |   -17
 » 9 days ago, # |   -6 More than 20k people registered for this contest! Looks like it will be a fun contest.
•  » » 9 days ago, # ^ |   +11 Having fun? :p
•  » » » 9 days ago, # ^ |   0 No. Spent too much time in C and still couldnt figure out simple logic. Then moved to D and solved it. Rating will go down steeply :(
•  » » » » 9 days ago, # ^ |   0 how to solve D?
•  » » » » » 9 days ago, # ^ |   0 (https://ideone.com/NT3pbQ) This is my code for D which got accepted
•  » » » » » 9 days ago, # ^ |   0 Main Logic is quite similar to Kadane's Algorithm of Max Sum Subarray. Just a small modification.
•  » » » » » 8 days ago, # ^ |   0 Hey AdnanShamsiCheck out the detailed explanations of:Problem EProblem D
•  » » » » » » 7 days ago, # ^ |   0 thanks
 » 9 days ago, # |   +4 Who is this vovuh and why are people so excited about him?
•  » » 9 days ago, # ^ |   +8 Spend some time on cf giving contests regularly and you will be able to answer this yourself.
•  » » 9 days ago, # ^ |   +17 He is the chosen one who sends all undeserving people like me from specialist to expert.
 » 9 days ago, # |   0 If I get WA1 on A and I can't proceed with the contest, will my rating drop?
•  » » 9 days ago, # ^ |   +17 Yes
 » 9 days ago, # |   +6 Nobody:Problem A in every Educational Round ever: 1 < t < 1000 1 < a, b, c, x, y, z < 10⁹ Seriously?
•  » » 9 days ago, # ^ |   +7 
•  » » 9 days ago, # ^ |   0 I thought that A was counting the number of such x :3
•  » » 9 days ago, # ^ |   -10 Of all bad and misworded As, today's A was the worst.
 » 9 days ago, # |   0 Again B is easy than A -_-
•  » » 9 days ago, # ^ |   -8 Actually, in Educational round it doesn't matter at all)
•  » » » 9 days ago, # ^ |   0 matter brother..If a,b swap then my penalty only for A B will be (6+17)=23..But now it was (11+17)=28.
•  » » » » 9 days ago, # ^ |   +9 If everyone finds A difficult than B, than it is actually difficult, and if everyone else finds it difficult, then all would take time to do that question and eventually your rank would be good even though you had more penalty
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   +5 And currently, mine is $(6 + 7)$ = $13$, but if they would have swapped $A$ and $B$, it would have been $(1 + 7)$ = $8$. But that doesn't matter much, rating would have been affected by $1$. Focus on improving skills brother!
•  » » 9 days ago, # ^ |   +6 idea was simple but problem statement could have been worded better
 » 9 days ago, # |   +7 OK, E is above my level. Go to bed instead.
•  » » 9 days ago, # ^ |   0 I would suggest don't give up and keep trying :)
•  » » » 9 days ago, # ^ |   +16 and what are you doing ?
•  » » » » 9 days ago, # ^ |   +7 Trying to motivate others. That's a good thing to do I guess. What are you doing?
•  » » » » » 9 days ago, # ^ | ← Rev. 2 →   +63 I am also trying to motivate others.If you read my comment properly, I was trying to embrass you so that you go and focus on your work.XD
•  » » » » » » 7 days ago, # ^ |   0 Bruh
•  » » 8 days ago, # ^ | ← Rev. 2 →   -9 Hey xiaoshizhanIt's just a smart brute force approach Check out detailed explanation: Link
 » 9 days ago, # |   +14 I am feeling that nowadays competiton is increased so much, not able to secure rank under 2k from past 3-4 contest.Contestant now even solving problem D like B, please tell me what do you think.
•  » » 9 days ago, # ^ |   +1 i feel the same way, contestants are doing much better recently
•  » » 9 days ago, # ^ |   +20 todays div2D<
 » 9 days ago, # |   +1 I wonder how people solved C that easily :/ it was really hard for me
•  » » 9 days ago, # ^ |   0 Off-topic:suddenly notice , after a long time you change your profile picture..
•  » » » 9 days ago, # ^ |   0 I wanted to put it after I reach expert but I guess that will take a long time .. I'm so disappointed about my performance
•  » » » » 9 days ago, # ^ |   0 don't worry brother..be continue your practice your desired day come quickly.Wished you Good luck <3
•  » » 9 days ago, # ^ |   0 I'd be much obliged if you could share the solution logic of C here.
•  » » 9 days ago, # ^ |   0 set answer, low , n to 0 iterate the string if '+' n++, else n-- if n < low, answer += string.position, low = n print answer + string.length i got WA and spent so many times to realize ans can't be store in int
•  » » » 9 days ago, # ^ |   0 Thats were im wrong too but i changed the int to long long in the last 8 minutes of the contest
•  » » 9 days ago, # ^ |   +4 I think with enough practice on this types of problems, it would become intuition. I used to find these types of problems really hard, and after solving and understanding them they become easy to solve.
 » 9 days ago, # |   +15 How to even think about the problem E.
•  » » 9 days ago, # ^ |   +7 Yeah man, the difference between D and E was huge today.
•  » » » 9 days ago, # ^ | ← Rev. 2 →   +1 Yeah true I was trying to apply digit dp for 1 hour in the contest .XD and than after the contest i saw that people did it with brute force ...facepalm.And so it became typeforces for most experts.
•  » » 9 days ago, # ^ | ← Rev. 4 →   +6 My solution for problem E: https://codeforces.com/contest/1373/submission/85070127The key insight is that K<=9 so you can only overflow at most once. For example if you pick the last digit to be x%10=7 with K=5, then it must look like this: (front ) 7 (front ) 8 (front ) 9 (front + 1) 0 (front + 1) 1 (front + 1) 2So for every fixed starting digit and K, the sum of all digits is: sumOfOnesPlace + numNoOverflow * sumOfDigits(front) + numOverflow * sumOfDigits(front + 1) = NWhere front is the variable we want to solve for and the rest are constant.If numOverflow is 0, you can solve for: sumOfDigits(front) = (N - sumOfOnesPlace) / numNoOverflowIf front doesn't end in a 9, you also know that sumOfDigits(front) + 1 == sumOfDigits(front + 1), which again lets you solve for sumOfDigits(front) = (N - sumOfOnesPlace - numOverflow) / (numOverflow + numNoOverflow)Once you know a target for the sum of digits of front, you can greedy it.This isn't complete because I didn't cover all the cases, but I am guessing other cases are impossible via proof by AC. :)
•  » » 8 days ago, # ^ |   +13 You can check out how to come up with the solution here :D
 » 9 days ago, # |   -19 Did 0 based indexing ruined time in anyone's D?
•  » » 8 days ago, # ^ |   0 Yeah bro I also initially wrote code for 1 based indexing and after checking for test case 1 I felt something is wrong & and read the question again and realised that it is 0 based indexing
 » 9 days ago, # |   0 I had a hard time trying to crack C, can anyone please explain me their approach?
•  » » 9 days ago, # ^ |   -7 void solve() { int n,i,j=-1; ll ans=0; string s; cin>>s; n=s.size(); vector pre(n,0); pre[0]=s[0]=='+'?1:-1; for(i=1;i
•  » » » 9 days ago, # ^ |   0 Why the prefix sum array? Just maintain a variable.
•  » » » » 9 days ago, # ^ |   0 Got it thanks for correcting me.
•  » » » » » 9 days ago, # ^ |   0 You are not wrong! It is just a tip!
•  » » 9 days ago, # ^ |   0 Lets take an example --++----+--Assume after each '+' sign good sequence start (good sequence = +++--- or +- or ++-- i.e. +++....---...)Break it in good and bad sequence(continuous '-' without + before)For above example you can break it like [-- (++--) -- (+-) -] (where inside () its good sequence.)Suppose good sequence A = (++--) {- sign after that is 3 excluding in good sequence}. good sequence B = (+-) negative sign after B i.e 1After analysing it you will see we are incrementing bad sequence 1 by 1 and iterating good sequence in one go.so ans due to bad sequence = (n (n + 1) / 2) {i.e 1 + 2 + 3...} = 15 (as n = 5)ans due to good sequence = good sequence length * no of '-' after that i.e. ans due to A good subsequence = (4(length of A) * 3(no of '-')) = 12ans due to B good subsequence =. (2 * 1) = 2Overall ans = (15 + 12 + 2) + (length of string) {because we will iterate our string fully once just before breaking out of infinite while loop}= 15 + 12 + 2 + 11 = 40
•  » » » 9 days ago, # ^ |   0 This is very smart, thank you!
•  » » » » 9 days ago, # ^ |   0 Sorry I overkilled it, better solution is given by tushar and others.
•  » » » 8 days ago, # ^ |   0 good explanation!
 » 9 days ago, # | ← Rev. 2 →   +3 How to solve E?Thanks in advance
•  » » 8 days ago, # ^ |   +3 Here is a detailed explanation for the problem
 » 9 days ago, # |   +9 Test case 3 for E?
•  » » 9 days ago, # ^ |   +3 Nevermind, figured it out:Sometimes it is optimal to put an 8 as the first digit after the 9s and 1s digit, rather than the remainder of the excess sum divided by 9.
 » 9 days ago, # |   +3 How to solve problem D?
•  » » 8 days ago, # ^ |   0 The video editorial for the D problem . Please subscribe to our channel :)
 » 9 days ago, # |   +190 $O(1)$ solution for E.
•  » » 9 days ago, # ^ |   +3 How did you generate those values?
•  » » » 9 days ago, # ^ |   +1 For $k = 0$ greedy algorithm. For other $k$ just check all $x$ from $0$ to $10^{9}$.
•  » » » » 9 days ago, # ^ |   0 That means you checked for all values in your laptop, really clever idea
•  » » » » » 9 days ago, # ^ |   +28 Yea. Precalc took ~$1$ minute.
•  » » » » » » 9 days ago, # ^ | ← Rev. 2 →   0 Wow, I couldn't find $ans(150, 1)$ for twice as long XD1e9 operations per second or what?
•  » » » » » » » 9 days ago, # ^ |   +5 You can iterate by $x$ from $0$ to $10^{9}$ with fixed $k$ and store the sum of digits of numbers. If this sum appears first time, you found the answer for this sum and our $k$. This huge brute forse is needed only for $k=1$, for other $k>1$ it is enough $10^{6}$ candidates.To speed up the whole brute force, you can do transition from $x$ to $x+1$ by $O(1)$ instead stupid $O(log(x))$.
•  » » » » » » » » 9 days ago, # ^ |   0 So, it's only 1 loop from $0$ to $10^9$, I get it. At first I thought you did that for all $k$, hence the question..
•  » » » 8 days ago, # ^ |   -8 For those following the threadCheck out the detailed explanation of how to construct that number: Link
•  » » 9 days ago, # ^ |   0 How did you map all the values, did you get any online tool to calculate that ?
•  » » 9 days ago, # ^ |   0 How did you generate values?
•  » » 9 days ago, # ^ |   +51
•  » » 9 days ago, # ^ |   -21 Is that allowed? Or would it be considered cheating
•  » » » 9 days ago, # ^ |   0 'Allowed' 
•  » » » 9 days ago, # ^ |   0 I mean it isn't technically cheating, more of a hacky solution
•  » » » » 9 days ago, # ^ |   +47 It is not cheating at all.
•  » » » » » 9 days ago, # ^ |   +12 Why do i hear your comment in petyr baelish voice in my mind XDXD
•  » » 9 days ago, # ^ |   +16 Meanwhile setters: Am I a joke to you.
•  » » 9 days ago, # ^ |   +3 FBI wants to know your location
• »
»
9 days ago, # ^ |
+51

# Codeforces be like :

•  » » 9 days ago, # ^ |   0 Can you prove it?
•  » » 8 days ago, # ^ |   -24 Those who are wondering about how to construct the numbers?Check out: Link
 » 9 days ago, # |   0 How to solve E?
•  » » 9 days ago, # ^ | ← Rev. 2 →   +3 I used — if (k >= 2) then apply brute to find an optimal answer, and greedily solve for k = 0,1 but got stuck at T-3
•  » » 8 days ago, # ^ |   +1 you can find a detailed explanation here in the video
•  » » » 8 days ago, # ^ |   +3 nice explanation brooo
 » 9 days ago, # |   0 I ended up using Kadane's for both D and F; I feel like it made sense for D, but was there an alternate solution to F that I missed?
•  » » 9 days ago, # ^ |   +1 Or prefix sums while maintaining min
•  » » » 9 days ago, # ^ |   +1 Isn't that exactly what Kadane's is?
•  » » » » 9 days ago, # ^ |   +4 Yes same thing but i used different implementation as Kadane's requires max and current sum
•  » » 9 days ago, # ^ |   0 Can you help with some intuition on, how to solve F with kadane's ? Thanks
•  » » » 9 days ago, # ^ | ← Rev. 3 →   +21 So, not sure if it is correct, but this was the idea I had: if you consider the bipartite graph of households and connections (NOT cities and stations, i.e. the first sample has 9 households and 9 connections), and have an edge between a household and a connection if their city and station are adjacent, then the problem becomes finding whether or not this graph has a maximum matching equal to number of households.The problem is that this graph is way too big to construct (it can have 2e15 nodes), so you need to use some general arguments. First observation is that if there is any subset $S$ of households such that its neighbor set is smaller than $|S|$, then it is not possible. If all subsets $S$ of households have neighbor sets that are greater than or equal to $|S|$, then we claim that it is possible. I didn't prove this, but it sort of feels like the proof will be similar to Hall's Marriage Theorem if it is true. Someone can correct me if I am wrong about this.Now, we obviously cannot check all subsets. However, we notice that if we are trying to find a subset $S$ such that the size of the neighbor set is smaller than $|S|$, we will always be able to use all the households from some contiguous set of cities (why? go through the proof, it's a good exercise).So, we are trying to find some contiguous group of cities such that the sum of their households is less than the sum of corresponding network connections that cover those houses. I'll leave this as another exercise to make the connection to Kadane's. You have to do quite a few modifications to the algorithm.
•  » » » » 9 days ago, # ^ |   0 I will definitely try to use the hints and to solve this problem. Thanks
•  » » » » 8 days ago, # ^ |   0 How did you know it is guaranteed that the sum over all connections is equal to the sum over all households? I mean, the samples do match the argument but how were you so sure so as to proceed?
•  » » » » » 8 days ago, # ^ |   0 Not sure I totally understand your question. The sum of all connections isn't necessarily equal to the sum of all the households; in test 3 on the sample case the sum of connections is greater than the sum of all households, and it is still not possible.
•  » » » » » » 8 days ago, # ^ |   +8 Oh, I misread your comment earlier. I thought it was perfect matching you were talking about. Now it makes sense, thanks.
•  » » » » 8 days ago, # ^ |   0 Using you hint i tried to solve this with kadane's kind of approach, But its getting TLE on test — 9. Can you please help me figure out why is this getting TLE ? https://codeforces.com/contest/1373/submission/85147824Thanks in advance for the help.
•  » » » » » 8 days ago, # ^ | ← Rev. 2 →   +3 I fixed your solution by adding one nifty line at the beginning of main:85152881The idea is that cin is actually quite slow at reading in input, and this only really matters when you are reading in something on the order of ~1e6 elements. It's generally accepted practice to include this line at the beginning of main, or otherwise use scanf for all your reads. If you look at the top 5 people in the standings you'll see they did this.If you add this line, though, you should NOT use scanf/printf while also using cin/cout. Choose one and stick to it, because the addition of this line essentially allows these operations to occur asynchronously and it will totally mess up your program in certain instances.
•  » » » » » » 8 days ago, # ^ |   0 Thanks a ton for the help. I will remember this from now own. Feels so good to to see it getting accepted.
•  » » 9 days ago, # ^ | ← Rev. 3 →   +1 my solution: i simply assigned all of the capacity of the i-th edge to the i-th node and greedily give the next node the cumulative excess capacity while paying attention to the capacity of the edge. i traversed through the graph twice since it is a cycle and checked for validity on the third pass. 2 passes might be enough but i was being safe and did not want to waste time on checking for correctness. in all honesty i am surprised this simple solution worked.edit: fst :(
 » 9 days ago, # |   0 What was test case 4 in problem D? ;-;
•  » » 9 days ago, # ^ |   0 i also got stuck in testcase 4 of D, but it is just integer overflow, i did't realize it until the last fifteen minutes.
•  » » » 9 days ago, # ^ |   0 oh sorry it was testcase 3
•  » » 8 days ago, # ^ |   -6 you can find a detailed explanation here in the video
 » 9 days ago, # | ← Rev. 2 →   +5 I almost took 90 min to solve A question. Soo confusing.
 » 9 days ago, # |   0 My brain: 30 minutes on A and 20 min on B+C -_-
 » 9 days ago, # |   +21 did anybody get a flow solution to pass for F?
•  » » 9 days ago, # ^ |   +10 I completely ignored flow because the limit was so large. Is it possible to pass?
•  » » » 9 days ago, # ^ | ← Rev. 2 →   -7 worst case runtime of Dinic is very bad, but it's very often misleading, since it can run wayyyy faster on certain types of graphs. On bipartite graphs, Dinic runs in O(sqrt(|V|)|E|) time in the worst case (edit: jk this is wrong, it still runs quick though), so I thought it was worth a shot. I think you can derive a solution by analyzing the augmenting paths of the graph.
•  » » » » 9 days ago, # ^ |   +8 I know that when Dinic's algorithm is applied to bipartite matching, the time complexity reduces. Its called Hopcroft-Karp algorithm. However, I have no idea when it comes to just finding a maximum flow on bipartite graph, not matching. AFAIK, the major reason why such bound holds is because the capacities are unit, which is not the case for this problem.
•  » » » » » 9 days ago, # ^ | ← Rev. 2 →   -10 https://en.wikipedia.org/wiki/Dinic%27s_algorithmin bipartite matching, you have both unit capacity edges and a bipartite graph. each of those restrictions individually can speed up Dinic, since each allows you to find blocking flows very fast, which reduces the number of iterations you have to do on the graph.edit: oh i see what you mean, the runtime i posted above doesn't always apply. AFAIK it still is true that it runs fast on bipartite graphs though.
•  » » 9 days ago, # ^ | ← Rev. 3 →   +15 Its memory limit gets exceeded anyways with Push Relabel (with gap heurestics). https://codeforces.com/contest/1373/submission/85062675 (Total 2 * n + 2 nodes are needed to model the problem into flow, with capacity taken in long long).
 » 9 days ago, # |   -39
 » 9 days ago, # |   +1 Is think explation in C and D can be useful in figuring Problems more easily.
 » 9 days ago, # |   0 How to solve D ? give some hints
•  » » 9 days ago, # ^ |   +5 Hint kadane's algorithm.
•  » » 8 days ago, # ^ |   -6 you can find a detailed explanation here in the video
 » 9 days ago, # |   +9 For me today B < A and D < C.
•  » » 9 days ago, # ^ |   0 Really D < C?
•  » » » 9 days ago, # ^ |   0 D was easier to think than C. I wasted all of my time on C.
•  » » 9 days ago, # ^ |   0 No way C is more difficult than D, unless you coded some weird solution.
•  » » 9 days ago, # ^ |   0 It took me more time to figure out correct solution for C than D.
•  » » 9 days ago, # ^ |   0 According to me  b < c < a < d problem A just ruined my contest ;(
•  » » » 8 days ago, # ^ |   0 How was it so hard? I was tring a*x< ceil(b/x) + c, which is not easy to solve!!
 » 9 days ago, # |   +4 Always 'A' makes me so Panick...Was staring at problems for 1hr 12 minutes. Zero solved! And then solved D->C->B->A. Honestly This was the difficulty for me. As soon as I saw D I got the solution.
•  » » 9 days ago, # ^ |   +8 I wonder how are you still green?
•  » » » 9 days ago, # ^ |   0 One rule of thumb- you must practice if you want Ratings... and that's what I lack :(
 » 9 days ago, # | ← Rev. 2 →   0 .
 » 9 days ago, # |   -50 F*uck int, F*uck integer overflow, int data type should be removed from C++, got AC on D just after the contest
•  » » 9 days ago, # ^ |   +26 #define int long long 
•  » » » 9 days ago, # ^ |   +3 You better think before writte int or long long.
•  » » » » 9 days ago, # ^ |   -10 Yes sometimes long long can lead a just passing soln to TLE
•  » » 9 days ago, # ^ |   +19 But isn't 'overflow' in your name?
•  » » » 9 days ago, # ^ |   +1 Hahaha I did not notice it.
•  » » 9 days ago, # ^ |   0 I always use long long no matter whether it should be.Though long long is slower than int and some kinds of problems will return TLE when you use long long instead of int, but the timelimit on CF is far more loose, so I just use long long every time to avoid the integer overflow.BTW, I'm very sympathetic to you, I can understand your feeling because I had many times when some stupid mistakes blew my whole contest up just for dropping 50+ ratings.
•  » » 9 days ago, # ^ |   0 I have same feeling with you
•  » » 9 days ago, # ^ |   0 Also, I got WA in D because of int. Yes, data types can cause havoc.....
 » 9 days ago, # |   0 Was not able to solve C..any help?
•  » » 9 days ago, # ^ |   +3 maybe you need long long
•  » » 8 days ago, # ^ |   0 Check out the detailed explanation of C: Link
 » 9 days ago, # |   0 How do you solve D? I came up with O(N*N) DP but it will TLE and I have no idea how to optimise. One observation I have is that there is no point in reversing a subarray of odd length as it'll yield the same sum. My DP solution was to go through all possible lengths of even subarrays and find the maximum value that can be obtained as sum at even positions upon reversing that subarray (which I do in squared time). Also, E seemed very interesting but apart from a few basic observations I found nothing. So, any suggestions on E are welcome too!I found the problems very interesting, thanks for the round!
•  » » 9 days ago, # ^ |   +7 The problem can easily be reduced to maximum subarray problem
•  » » » 9 days ago, # ^ |   0 Crap, yes.... I feel really stupid now. I solved this in squared time and didn't recognise the similarity smh... Thanks!
•  » » 9 days ago, # ^ |   0 We can solve D simply by building (sum of odd indices — sum of even indices) for every prefix, and some simple calculations.
•  » » » 9 days ago, # ^ |   0 Me bro. Feeling guilty after seeing kadane solution
•  » » 8 days ago, # ^ |   0 Here is my dp solution to problem D which is very different from Kaden's algorithm.
 » 9 days ago, # |   +3 Problem D was really cute.
•  » » 9 days ago, # ^ |   0 Can you share how you solved it?
•  » » » 9 days ago, # ^ |   0 This is the link to my solution... First observation is that the array that you want to reverse has to have even length in order to get the elements swapped. And you can start considering that the initial array is the best..and then you can use kadane's algo for finding the best subarray to reverse. Reversing an even length array means in fact subtracting from the result the elements that were previously in the sum and adding the others.
•  » » » » 9 days ago, # ^ |   0 Can it be solved using two pointers ?? considering the largest even subarray such that the sum of elements at odd position is greater than sum of elements at even position and adding the remaining even sums at both ends ??
•  » » » » » 9 days ago, # ^ |   0 I don't really know. Maybe it is possible. That was the only idea i had..and thankfully it worked
•  » » » » » 9 days ago, # ^ |   0 I tried to implement the same idea during the contest but failed. If you find someone's code using this method, let me know.
•  » » » 8 days ago, # ^ |   +3 you can find a detailed explanation here in the video
 » 9 days ago, # |   +8 How to solve F?
 » 9 days ago, # |   0 I was not knowing that in Educational round, there is no point system. So I skipped A and solved B, C, D. I got a rank below 6500.:(
 » 9 days ago, # |   +9 Toughest Most confusing A ever.
 » 9 days ago, # |   +50
•  » » 9 days ago, # ^ |   0 Actually for n = 150 and k = 0 answer is much bigger than 10^10
•  » » » 9 days ago, # ^ |   -10 It is 150.
•  » » » » 9 days ago, # ^ |   0 It's not
•  » » » » 9 days ago, # ^ |   +6 1 + 5 + 0 = 6 != 150
•  » » » 9 days ago, # ^ |   0 Right my mistake.
•  » » » 9 days ago, # ^ |   0 Yes, but not difficult to understand that it's a number with a lot of 9 at the end and first digit n % 9, if n % 9 != 0, and simply many 9 else.
•  » » » » 9 days ago, # ^ |   0 Well, yes you're right, it seems for k >= 1 answer is bruteforcable and k = 0 is not difficult to guess
•  » » » 8 days ago, # ^ |   0 but its less than 10^18
 » 9 days ago, # |   0 Video Tutorial A https://www.youtube.com/watch?v=YfhnZbKdquU
 » 9 days ago, # | ← Rev. 2 →   -35 Why NlogN TLE'd on D?After seeing the constraints, I assumed it should have passed.Submission
•  » » 9 days ago, # ^ |   0 You mean why $O(n^2)$ TLE while $O(n)$ passes?
•  » » 9 days ago, # ^ | ← Rev. 3 →   -10 Your solution isn't NlogN it is O(N^2) . Since number of even length subarrays is (N * (N + 1))/4 -> O(N^2)
•  » » » 9 days ago, # ^ |   -18 Can you explain why? I was thinking it is NlogN, so wasn't optimizing during contest.
•  » » » » 9 days ago, # ^ |   +4 you have commented in your code that " so we can check every len of 2, 4, ... , n using tc = Nlog2N."it would have been Nlog2N if it was 2,4,8,16...N but here it is 2,4,6,8,10....N
•  » » » » » 9 days ago, # ^ |   0 damn.. Thank you brother. I didn't consider that.
 » 9 days ago, # |   0 How to solve D??
•  » » 9 days ago, # ^ |   +3 check this. It's a link to my comment where i explained a little
•  » » 9 days ago, # ^ |   +3 СпойлерFirst, we calculate the answer without changing the array (we just sum the elements at odd positions). Then create an element in which we will store the maximum by which we can increase the response. Next, we go through the array, first from the zero element through one, then from the first element through one and consider the difference between them. At each turn, we update the maximum. If the current difference is less than zero, we reset this difference, we no longer need the old sub-segment. Difficulty 2 * N
•  » » 9 days ago, # ^ |   +6 I solved D without kadane. My approach is that store prefix even -prefix odd in one vector and prefix odd indexed values -and prefix even indexed sum values in another vector. and then try reversing maximum difference of odd indexed -even indexed sum values sum even length subarray if the array ends at odd index and vice versa for subarrays ending at even index. Try thinking on building intuitions. My submission link is :- 85056177Hope I would be hacked!
•  » » 8 days ago, # ^ |   0 Check out the detailed explanation for it here, you can read more about Kadane's algorithm if you have further doubts :)
•  » » 8 days ago, # ^ |   0 You can check out my video editorial here
 » 9 days ago, # |   0 I stuck on c for one and a half hour because of forgetting using long long...
•  » » 9 days ago, # ^ |   0 same.. got no time try D
•  » » » 9 days ago, # ^ |   0 Tough day for us pal. At least we could learn from this and avoid making the same mistake.
•  » » 8 days ago, # ^ |   0 me too
 » 9 days ago, # |   0 85052253 is ...weird. Who would if(a==165) that deliberately, if not for other accounts to hack?!Also some of the other A problem Hacks too. Weird.This one
•  » » 9 days ago, # ^ |   0 lol..
•  » » 9 days ago, # ^ |   +5 And for his first try on problem A he wrote (a==7) but it didn't work :D. I also accidentally reviewed these two solutions in hacks section and was confused :DD
•  » » 9 days ago, # ^ |   0 Guess it's the same person with two accounts
•  » » 9 days ago, # ^ |   0 Here's another one
 » 9 days ago, # |   0 Fuck it , I need a urgent editorial. Hell yaaa..
 » 9 days ago, # |   0 Could anyone please confirm, Shouldn't the verdict for this would have been Runtime Error signed integer overflow? Instead it gave Wrong Answerhttps://codeforces.com/contest/1373/submission/85049895
•  » » 9 days ago, # ^ |   0 Same with long long got accepted. https://codeforces.com/contest/1373/submission/85056498
•  » » 9 days ago, # ^ |   0 Most languages do not error on arithmetic overflow.
•  » » » 9 days ago, # ^ |   0 But sir, it gave here https://codeforces.com/contest/1373/submission/85054448 :(
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   +1 Oh I actually didn't know about the diagnostics. Apparently they were introduced here? https://codeforces.com/blog/entry/55902Looks like the diagnostics only run in some cases: "If your solution: written in C++, finishes with a verdict "wrong answer" or "runtime error" on this test worked extremely quickly and consumed a little memory," from the blog post.
•  » » » » » 9 days ago, # ^ |   0 Thanks for the info sir, but it seems https://codeforces.com/contest/1373/submission/85049895 (Wrong) https://codeforces.com/contest/1373/submission/85054448 (Overflow)consumed same time and memory, and the other 2 points are correct for the first link.Anyways, I will always use long long from now on.
•  » » » » 8 days ago, # ^ |   0 From experience, the overflow error only shows when solving problems out-of-contest. For some reason they're disabled inside.
•  » » 9 days ago, # ^ | ← Rev. 2 →   0 If I rmb correctly, integer overflow will just produce wrong answer. Like, if you said int a = 2147483647; a++; cout << a; It will print perfectly fine, but will print -2147483648 instead. (Overflow to the back)
 » 9 days ago, # |   0 Can someone point out the mistake in my submission for D? 85049220 I used maximum subarray approach. Don't know where its going wrong. Test case is too big to understand.
•  » » 9 days ago, # ^ |   +1 Is it because you are casting ad to int32_t at the end?
•  » » » 9 days ago, # ^ | ← Rev. 2 →   0 Mistakes like these are always remembered :( Just changed that part and Boom 85058120 Thanks a lot. Would have never figured that out. Also, a silly question, I use: define int long long int because of which I have to use int32_t and stuff. How do you use library functions then? Because when I use max with just ad, it says no matching function calls. So, how do I use (any)library functions on long long int variables?
•  » » » » 9 days ago, # ^ | ← Rev. 2 →   +5 Just ensure that you typecast the other value to long long int as well. For example long long int x = 100; vector a = {1, 2, 3, 4, 5, 6}; int y = max((long long int)a.size(), x); 
•  » » » » » 9 days ago, # ^ |   +3 Yeah, its working. Thanks mate :)
 » 9 days ago, # |   0 when will the official analysis ?
 » 9 days ago, # |   -10 vovuh I'm curious, was the following solution intended for E: If $k = 0$, greedy. If $k = 1$, notice some patterns, come up with a rule. If $1 < k <= 9$, write a brute force up to something on the order of 1e6 (possibly, with optimizations). I also noticed many users did precalc (calculated all the answers offline). However, the vast majority did something totally different (idk what), so I wonder, whether the straightforward solution was intended or not. Thanks.
•  » » 9 days ago, # ^ |   +103 Iterate over the last (rightmost) digit Iterate over the number of 9s before it. Calculate the needed sum of left digits, check it to be non-negative and integer. Construct left part greedy to fit that sum. And find the minimum value among them. No special cases.
•  » » » 9 days ago, # ^ |   +1 Wow, that's totally elegant, thanks a lot!
•  » » » 9 days ago, # ^ |   0 In your code, how did you know to insert an 8 in the middle when lft is greater than 8?
•  » » » » 9 days ago, # ^ |   +18 I need to put as large digit as possible, but I can't put a 9 there since I fixed the number of 9s. So here comes an 8.
•  » » » » » 9 days ago, # ^ |   +5 I see, thanks!
•  » » » 9 days ago, # ^ |   0 As far as I can tell, you don't even need to iterate over the number of 9'sIf the rightmost digit would wrap around from 9 to 0 in your sequence, then the number of 9s before the last digit is always 0else the number of 9s is as large as possible
 » 9 days ago, # |   0 If someone want a poorly coded and inefficient DP solution for E : 85057205
 » 9 days ago, # |   0 Fucking D . Any solution? Waiting for help.
•  » » 9 days ago, # ^ |   +9 Here's one solution — 1.Standard problem to be used. Maximum sum subarray of even size (you can google and first geeks link can help). 2. Observation : reversing an odd sized subarray is useless. Problem is reduced to find a subarray of even size, where sum of odd indices elements are more than even indexed elements . 3. Actual solution - sum all even indexed elements , call it sum_1 , multiply all even indexed value by -1. Find the maximum sum of even sized subarray in this modified array, call it sum_2 . Ans = sum_1 + sum_2
•  » » » 9 days ago, # ^ |   0 thk you
•  » » » 9 days ago, # ^ |   0 by the way thank you for aur sharing your approach . but can please explain why "multiply all even indexed value by -1" is done (how is it helpful??).
•  » » » » 9 days ago, # ^ |   +1 If after this modification, there exists a even sized subarray with positive sum, that means of you reverse this array, you will get most benefited.
•  » » 9 days ago, # ^ |   +1 Some Hints: Spoiler See the differences between sum at odd positions vs sum at even positions. If for a range, overall difference between sum of odd positions and that of even positions, reversing that range will help in increasing overall sum at even positions. Find the range (using linear algorithms like Kadane), to get the range with maximum(negative) sum. Replacing that range will lead towards maximum sum at even positions My AttemptSubmission to D:85025959
•  » » » 9 days ago, # ^ |   0 thk you guy
•  » » 9 days ago, # ^ |   0 I think after see the solution you understood all.Just Using prefix count solutioncin>>test; while(test--){ ll n; string s; cin>>n; ll ar[n+5],ans=0; for(int i=0;i>ar[i]; if(i%2==0) ans+=ar[i]; } ll mx=0,now=0; for(int i=0;i
 » 9 days ago, # |   +16 Hello!I am MrPupsik. Help me to solve problems pls.
 » 9 days ago, # |   +3 Can anyone help me understand where my attempt to problem C goes wrong?I think that this might be due to some overflow error, but i am unable to see where it occurs, as almost everything is long long.
•  » » 9 days ago, # ^ |   +4 I guess that ans = ans+it-vc.begin()+1; causes pointer overflow which leads to undefined behavior? As changing the line to ans = it-vc.begin()+ans+1; (submission 85085422) or ans += it-vc.begin()+1; (submission 85085571) solve the issue.
•  » » » 8 days ago, # ^ |   +1 Thanks bro
 » 9 days ago, # |   0 What was the complexity of intended solution of F?
•  » » 9 days ago, # ^ |   0 I solved it in O(n)
 » 9 days ago, # |   +1 It's really annoy :(
 » 9 days ago, # | ← Rev. 4 →   -20
 » 9 days ago, # | ← Rev. 4 →   +37 My solution for the E:If k = 0 we can build the number, we simply put the largest digit to the left whenever we can.If K = 1 and n is an odd number, we simply put an 8 at the end of the number, so when putting it together it would be:XXXXXX9XXXXXX8But if N <17 we can check with brute force.If K = 1 and n is an even number, we simply put 89 at the end of the number, so when putting it together it would be:XXXXX90XXXXX89But if N <26 we can check with brute force.The last case is when we have k> = 2 in this case we can search for it with normal brute force, because at most it will have 6 digits
 » 9 days ago, # |   0 Did a semi brute-force solution for E and it worked. https://codeforces.com/contest/1373/submission/85047398. Precalculate the answer for all numbers that are I9JK, I99JK, I999JK etc.. Where I,J,K can be any digit and there is a bunch of 9s in between (0 up to 20). Then do lookups,
•  » » 9 days ago, # ^ |   +7 At the first glance I read the last line as "Then do hookups".
 » 9 days ago, # | ← Rev. 3 →   +17 I saw the tags for problem F, and I did not see the greedy tag. My solution is only based on a greedy approach. I do not know how to prove its correctness. If it is wrong, feel free to hack it.The solution is here: https://codeforces.com/contest/1373/submission/85035196PS: They added the greedy tag.