Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

By BledDest, history, 8 months ago, translation,

Hello Codeforces!

On Oct/11/2020 12:05 (Moscow time) Educational Codeforces Round 96 (Rated for Div. 2) will start. Note that the start time is unusual.

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

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

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

The problems were invented and prepared by Adilbek adedalic Dalabaev, Alex fcspartakm Frolov 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 WZYYN 7 186
2 137_345_2814 7 194
3 jiangly 7 200
4 LayCurse 7 203
5 dreamoon_love_AA 7 258

Congratulations to the best hackers:

Rank Competitor Hack Count
1 ViciousCoder 100:-9
2 ManasG 45:-13
3 Valera_Grinenko 57:-40
5 fstzyh 38:-9

858 successful hacks and 2258 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A sevlll 0:01
B jkchen 0:03
C alireza_kaviani 0:03
D jkchen 0:12
E MagicSpark 0:05
F LayCurse 0:36
G MagicSpark 0:36

• +463

 » 8 months ago, # |   -14 This unusual time makes me unusual :(
 » 8 months ago, # |   -12 4AM for me :(
•  » » 8 months ago, # ^ |   +18 That's sad! Don't Sleep ;)
•  » » 8 months ago, # ^ |   +87 23 minutes to the contest.. Time to wake up bro
•  » » 8 months ago, # ^ |   +145 Good morning!
•  » » 8 months ago, # ^ |   +3 Wholesome-forces
•  » » 8 months ago, # ^ |   0 3:30 PM here.....good time for me tho
 » 8 months ago, # |   +55 notice the unusual time getting usual
•  » » 8 months ago, # ^ |   +1 which can be a good thing for many (and a very bad thing for some)
 » 8 months ago, # |   -43 Btw, not sure where to write this, I just noticed there is a testing round just before this contest. Personally I am already tired to do a contest for 2 hours, so i don't really want to do a testing round just before that. I am happy to do a testing round any other time actually.
 » 8 months ago, # |   -22 why unusual time for ECF...2AM
 » 8 months ago, # |   +4 Hmmm.... from Edu 46, every Announcement blog was authored by pikmike and he was always included in the problemsetters' tab. Did he get angry from all the downvotes from last round? The last round was pretty great problem-wise, learnt a lot, especially from problem G.
 » 8 months ago, # |   +11 Note that the start time is unusual, is getting usual to us :)
 » 8 months ago, # |   +45 No vovuh , Roms , Neon and awoo! Are they okay?
•  » » 8 months ago, # ^ |   +158 vovuh, Neon and pikmike are participating officially in the contest this edu is based on.
 » 8 months ago, # |   -9 my hope to return a cm
 » 8 months ago, # |   +9 Normally unusual timings is due to a live contest happening at the same time. Is there any reason this time?
 » 8 months ago, # | ← Rev. 2 →   -32 what happened to my rating graph its weird... how to solve it?? please look my profile?? @admin anyone can help??
 » 8 months ago, # |   0 Lunchtime for me :(
•  » » 8 months ago, # ^ |   0 Where do you live and what time will be in your country at the contest?
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 India. Its 2:35 pm, in afternoon
 » 8 months ago, # |   0 ECF and opencup are at the same time, not cool
 » 8 months ago, # |   +17 I will be doing online class and contest together. Shouldn't miss a single contest in this quarantine <3
•  » » 8 months ago, # ^ |   +15 do you have classes on sundays?
•  » » » 8 months ago, # ^ |   0 Yes, we have class everyday except friday in Bangladesh.
•  » » » » 8 months ago, # ^ |   0 on Sunday? strange
•  » » » » » 8 months ago, # ^ |   0 devilbro yup brother. We have prayer on friday . So that day is off day.
•  » » » » » 8 months ago, # ^ |   0 in all muslim countries friday = sunday
•  » » » » 8 months ago, # ^ |   +20 Friday is special day for Muslim. We are majority Muslim in our country. So government make Friday off day for us. Such as Sunday is Holiday in your country.
 » 8 months ago, # |   +1 The timing is great for me. Thanks :)
 » 8 months ago, # |   0 Can anybody explain me what does solution hacking means? Thanks in advance.
•  » » 8 months ago, # ^ |   +14 Once the 2-hour problem solving round is over, participants have the option, to see the solutions submitted by other participants and try to generate possible inputs, upon which these solutions might end up giving incorrect outputs. This is what hacking means. All of this has to be done in a 12-hour hacking phase just after the contest. Once this 12-hour phase is over, solutions are re-judged based on all the hacks generated. Hope this helps!
 » 8 months ago, # |   +8 Great start time for chinese participants:D
•  » » 8 months ago, # ^ | ← Rev. 2 →   +1 Same here in Korea. it's 18:05 (UTC+9)
•  » » 8 months ago, # ^ |   0 For Japanese too. :) (start at 18:05) Recently many contests were held at 23:35(UTC+9), in which is difficult for me to participate.
 » 8 months ago, # |   +2 2 days Back to Back Contests10 October 2020 HHKB Programming Contest 2020 Codeforces Global Round 1111 October 2020 Educational Codeforces Round 96 AtCoder Regular Contest 105Great for learning
 » 8 months ago, # |   +5 I think there should be more contests of this Asian timezone. Maybe there should be two types of contests for Europeans and Asians.
•  » » 8 months ago, # ^ |   -10 200% agree
 » 8 months ago, # |   +12 11 minutes left time to be ready : )
 » 8 months ago, # |   -17 Will BledDest be conducting the future rounds as well ? He's been conducting the last 2 EDU rounds too.
•  » » 8 months ago, # ^ |   +104 He has actually been conducting the last 79 edus.
•  » » » 8 months ago, # ^ |   -11 Sorry I meant if you will be away like this contest.
•  » » 8 months ago, # ^ |   +11 please graphforces
•  » » 8 months ago, # ^ |   -28 C and D without educational worth.C is just "try it, should work...somehow", D is kind of edgecase hunting.
•  » » » 8 months ago, # ^ |   +12 Nah, C was kinda cute. To minimise the end value, we had to keep as many smaller digits as possible was my conjecture (which I indeed took a few minutes to prove after a guess submission). The solution (I think) was to take the biggest two values and perform the ceiling operation and then continue. D was quite great too if we (at least I) didn't misinterpret what the problem statement. I thought E could be something to do with segment trees and inversions but that didn't end so well for me implementation-wise.I looked at your submission for C and it was kinda hilarious to see your struggle in comments. Well done though!
•  » » » » 8 months ago, # ^ |   0 In C , For any value of n , i always got answer as 2. It was more observation based ig
•  » » » » 8 months ago, # ^ |   -8 I just recalled those two problems, and still, I think I did not learned anything from them.In C you see the intended solution by coincidence, or you do not. If you do not come up with the idea to simply add the two biggest values you'll get stuck at this problem. Or find some other algo which coincidently works, too, like mine. But for somebody who did not solve C the thing you get is "There is nothing you can do. Solve more problems, mayby then someday you'll get the intuition to have the right idea at the right time."And problem D is basically the same. You find the right pattern by blindly trying some pattern. Or you do not find it. I found the three points given as hints in the tutorial within like 10 minutes. But still did not found a way to make it a working algo for like an hour. And afterwards, just like in C, absolutely no knowledge of what I could have done differently or better.That might be nice riddles, but from my point of view no problems to educate anything.
 » 8 months ago, # |   0 scoring?
•  » » 8 months ago, # ^ |   +3 all problems have equal weightage in educational round!
 » 8 months ago, # |   0 is there penalty on correct resubmission in educational round?
 » 8 months ago, # |   +14 I am eagerly waiting to see the test case no:2 of problem D,,,huh.
 » 8 months ago, # |   0 Idea behind E?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +4 Counting Reverse pairs (Inversions)
 » 8 months ago, # |   0 Contest Finished.Can we discuss the problem before system judge?I have not too much ideas about F&G
 » 8 months ago, # |   +7 How to solve D?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +4 Transform the string to an array of integers. Now traverse from left to right. When you meet one, you should delete some thing larger than 1 in the right. When you meet something that is not one, you just delete it.
•  » » » 8 months ago, # ^ | ← Rev. 4 →   0 95246189 same approach, but got wrong answer on pretest 2. Can you give me a sample test for which my code fails.
•  » » » » 8 months ago, # ^ |   +1 You should look at the verdict. It tells that you got WA on test 21 of test case 2.
•  » » » » » 8 months ago, # ^ |   +1 I had kind of same approach but not able to figure out which test case it fails : https://codeforces.com/contest/1430/submission/95251105It says test-525 of test-case-2, how do I figure out now where did it fail ?
•  » » » » » » 8 months ago, # ^ |   0 I have wa on 525 test case too. https://codeforces.com/contest/1430/submission/95253889
•  » » » » » » 8 months ago, # ^ |   +18 1 9 011101000 
•  » » » 8 months ago, # ^ |   0 You should have clearly mentioned about deleting the first right element greater than 1. Man, I was deleting the maximum one the right :(
 » 8 months ago, # |   +7 How to solve D????
•  » » 8 months ago, # ^ |   0 111011 -> [3, 1, 2]delete -> minus 1remove prefix -> delete first numberThen try best to maximize the operation
•  » » » 8 months ago, # ^ |   0 I used same logic but got WA Submission link : https://codeforces.com/contest/1430/submission/95229144but when i removed lowerbound and submitted again with same logic it was accepted.So please can you tell me what the issue is ?
•  » » 8 months ago, # ^ |   0 two pointer concept.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +9 Maintain an array of lengths of consecutive elements. If the first prefix length is greater than 1 (>1), then we can remove that prefix and increase the number of operations. Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it. If such length is not found, remove the last length from the array (maintain 2 pointers one left and one right and reduce the right pointer).Example :- 1 5 10111After 1st operation -> 011 After 2nd operation -> 1 Thus 3 operations are required.A counter example as to why we should reduce from the first large prefix instead of the largest one is here
•  » » » 8 months ago, # ^ |   0 Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it.Please tell me wouldn't that make the complexity n*n. It tried the same thing but got tle on test 4.
•  » » » » 8 months ago, # ^ |   +1 Just keep pointer to last element that is greater than 1 and shift it right if necessary (do not search for it from the start every time).
•  » » » » 8 months ago, # ^ |   +1 You don't have to search starting from the first element always. Suppose your at 2nd element in [1,2,2,3]. Now, after reducing that, you only need to move forward in the array because the previous entries will be <=1. This can be done using a variable to store the current reducing index and incrementing it accordingly.
•  » » » » » 8 months ago, # ^ |   0 Thanks :)
•  » » » » » 8 months ago, # ^ |   0 How can we know that the next value is >= 2?Example: [1, 2, 1, 3], if you are at the second elementthen you will decrement the 2nd element and it will be [1, 1, 1, 3] now if you increment it by one it will be on the 3rd element which is 1. But reducing 1 isn't correct, the correct one is to reduce 3.So how to increment it?Please I am stuck here for several hours.
•  » » » » » » 8 months ago, # ^ |   0 Suppose your pointer was on the 2nd element, now you have to increase until it becomes >=2. If it is not possible, then u just reach the end of the array.
•  » » » 8 months ago, # ^ |   +1 I used the sae concept but getting WA on 252nd test : https://codeforces.com/contest/1430/submission/95251105How do I figure out a test where it fails ?
•  » » » » 8 months ago, # ^ |   0 Try reading the comments to find any test cases that your solution may fail. I don't think there is a way to access that particular test.
•  » » » » » 8 months ago, # ^ |   +5 I got it. When the current value if "1", I was trying to make up for it by using the element which is the largest in range (i+1,N) which is not always optimal , better option is to use the element closest to the current index (on its right) . Thanks!
•  » » » » » » 8 months ago, # ^ |   0 Not largest, any number which is greater than 1 in range (i+1,N) is my approach. What's wrong in that?
•  » » » » » » » 8 months ago, # ^ |   0 Choosing any number in range (i+1,N) is not optimal , its better to always choose the first number greater than "1" in range (i+1,N) . Why ? Because, you are at index "4", and a[4]=1 , also, a[5]=1,a[6]=1,a[7]=3,a[8]=1,a[9]=1,a[10]=5 . Now, you have only two options, either select from a[7] or a[10] , but the best choice is to select from a[7] , because soon you are going to reach a[7] , and its all potential value will be destroyed , once it is destroyed by prefix technique ,so better completely use a[7] before destroying it.
•  » » » » » » » » 8 months ago, # ^ |   0 Oh yes, I got it. Thanks
•  » » » 8 months ago, # ^ |   0 Why is it necessary to find the first greater than 1 segment ... If I find the largest segment everytime and reduce it.. won't it work ?
•  » » » » 8 months ago, # ^ |   0 No. Check this out => Comment
•  » » » 8 months ago, # ^ |   0 In case of prefix length = 1, instead of looking for the first length > 1, I looked for the largest length substring of the same value and reduced it's length by one but I got WA using this approach. Can you help me? My submission
 » 8 months ago, # |   +12 Problems just awesome in this contest.
•  » » 8 months ago, # ^ | ← Rev. 2 →   -10 Yes,brother.thanks.
 » 8 months ago, # | ← Rev. 2 →   +3 How to solve E?
•  » » 8 months ago, # ^ | ← Rev. 4 →   +26 Have an vector of stack of size 26 where u push each character to respective bucket initially. Now we know that the first character has to reach the end. But the important thing to notice is that only the last occurence of the first character is required to reach end to save operations, that is why we maintain a stack to get last occurence.Now if we know that the last occurence of ith character is at position j, we also need to know how many of the characters from j to n-1 have already been push to right and for that we use segment Tree/BIT.So at each postion ans += n — 1 — (no. of char in [j,n-1] already pushed) — lastest position of that charHeres my Submission
•  » » » 8 months ago, # ^ |   0 Could you explain why do we need to know the number of char already pushed? And how about handling the chars that has index larger than n/2?
•  » » » » 8 months ago, # ^ | ← Rev. 4 →   +9 That is because set of character after the last character given in the input are already in reverse and we dont need to consider them. It would be better to explain with an example.Lets say we have the string: icpcsguruFirst move: We move the i at postion 0 to the end and get cpcsgurui. moves=9-1-0=8 Second move: We move the c at position 3 to end(after u) -> cpsguruci. moves=9-1-3=5Third move: This is the important one. Here we move the p at position 2 but the moves wont be 9-1-2, instead it would be 9-1-2-1=5.This is because the c ahead of p is already moved to end and this is exactly why we need a range query from j to n-1 to get how many are moved to end.
•  » » » » » 8 months ago, # ^ |   0 Oh I see it now. You were like try to bubble the chars from the left to right, one by one. Thanks.
•  » » » » » 8 months ago, # ^ |   0 Very nice solution . I have written the solution code based on the approach told by you . My submission : https://codeforces.com/contest/1430/submission/95353036
 » 8 months ago, # |   0 Why did you not bold 'prefix' in D :(delete the maximum length prefix consisting of the same characters...
•  » » 8 months ago, # ^ |   0 Ah, damn it... This is where most of us went wrong. Most of us did indeed solve a different version of this problem correctly.
•  » » » 8 months ago, # ^ |   0 I tried for over 1.5 hrs but couldn't come up with a solution for the "different version" of the problem.
•  » » 8 months ago, # ^ |   +5 wait, I missed that too... :(
 » 8 months ago, # | ← Rev. 5 →   0 I misread B and thought that only adjacent swaps were allowed.(Sorry for the edits)
 » 8 months ago, # |   0 Helps for Problem D please
•  » » 8 months ago, # ^ | ← Rev. 3 →   +4 precompute an array of sizes of chunks of 0s and 1s for [0, 0, 0, 1, 1, 0, 1, 0, 1, 1] -> [3, 2, 1, 1, 1, 2] now in each step first chunk would be removed anyway but we need to remove 1 other element before that, choose the chunk either after it or itself that has size > 1, if theres no such chunk remove the last elementSince we never delete a chunk of size 1 from middle, it is ensured that two chunks are never merged. Hence we will always get the optimal answer.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 I used nearly the same approach. But when there is no chunk of size >1 then I just add (remaining unprocessed elements+1)/2 Here is my submission.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 I actually did this exact thing .. You would see if you go through my last two submissions .. I now want to figure out where it went wrong Upd : I got the bug .. actually I thought to use the first non one value and hence used a priority queue to keep the minimum next indices avalaible for operation only to realize now that we get a maxheap as a default.. my bad.. Got the same code accepted Now. Thanks for replying and help anyways :)
 » 8 months ago, # | ← Rev. 2 →   +31 What on earth is Test Case 2 for D ?UPD : my greedy fails for 5 10111, ans should be 3, not 2. Optimal way is to take 5th character first.Damn, it seemed so obvious, the guy who set this problem is pure EVIL!
•  » » 8 months ago, # ^ |   0 Exactly...Here is my approach.....If prefix has more than 2 same characters then 1 operation consists of removing the first character and then the remaining prefix...this way we delete the minimum we can after every operation. Also if s[i]!=s[i+1] then we jump to s[i+2] after deleting si and s(i+1). This can be proved to be true by some casework...but I dont know why this greedy approach is failing.
•  » » » 8 months ago, # ^ |   0 well i understood why this approach is wrong in last second consider 101111according to ur algorithm answer is 2 ! where u can get answer 3 by erasing 3 on first operation and erasing 2 on second operation and then erase 1
•  » » » » 8 months ago, # ^ |   0 so 3 operations in total
•  » » » » » 8 months ago, # ^ |   0 My solution gives 3. Can you please have a look at it?
•  » » » » » » 8 months ago, # ^ |   0 I stress-tested my solution and got some tests where my code fails: Spoiler1001000 expected: 4, output: 3 1101000 expected: 4, output: 3 1000100 expected: 4, output: 3 1100100 expected: 4, output: 3 0010100 expected: 4, output: 3 1001110 expected: 4, output: 3 0010001 expected: 4, output: 3 there were few more tests, but I think it's enough
•  » » » » » 8 months ago, # ^ |   0 My solution idea is same but it fails on test-525 . Can anybody tell me which test if fails ?
•  » » 8 months ago, # ^ |   0 1 7 0100010You can try this case, my solution was giving wrong answer on this case. May be you might get your mistake. The correct answer is 4.
•  » » 8 months ago, # ^ |   0 I figure what's wrong when my first submissionI maintain two index, the head and the index of number bigger than 1.It's important to notice that the second index must >= the first index.
 » 8 months ago, # |   +36 this contest actually had a really good combination of problems ! neither too easy , nor extremely tedious . Thanks BledDest for the contest
 » 8 months ago, # |   0 What hurts more? aBREAKUP bGETTING TLE ON TESE CASE 41 DURING THE CONTEST
•  » » 8 months ago, # ^ |   0 If you use O(n^2), you will surely get TLE. I also copied code from GFG though and get TLE on test cae 41 :P https://www.geeksforgeeks.org/minimum-number-of-adjacent-swaps-to-convert-a-string-into-its-given-anagram/
•  » » » 8 months ago, # ^ |   0 What's the point of getting a positive rating when the code and logic aren't yours in the contest!?
•  » » » 8 months ago, # ^ |   0 You guys are copying? ://
•  » » 8 months ago, # ^ |   0 Getting TLE on test case 41 while simultaneoulsy on call with GF with she breaking up wid ya at the same exact moment or vice versa whatever minimizes your mood. My guess is you probably got lucky with both events not happening at the same time....If even luck did not favor you on that...then oh boy.... that oughta hurt (In Matthew Mccounaughey's voice)...good luck xD.
•  » » » 8 months ago, # ^ |   0 This is what happens when you are already overthinking and you start to overthink your overthinking. PS: You are funny!
•  » » » » 8 months ago, # ^ |   0 Yeah I am watching Sherlock these days, and my tone..be it in any chat..whatsapp,CF,CC,CSGO,twitch,among us(xD)... etc sounds so deductive and caseworkey lol. Thanks btw.
•  » » » » » 8 months ago, # ^ |   0 cringe ngl
»
8 months ago, # |
Rev. 2   -63

# include<bits/stdc++.h>

using namespace std;

int main(){

int t;

cin>>t;

while(t--){

int n,k;

cin>>n>>k;

int a[n];

for(int i=0;i<n;i++){

cin>>a[i];

}
int kk = sizeof(a)/sizeof(a[0]);

sort(a,a+kk);

int i=2;

while(k--){

if((n-i)>-1){

a[n-1]=a[n-1]+a[n-i];

a[n-i]=0;

i=i+1;

}

else{

break;

}

}

cout<<a[n-1]-a[n-2]<<"\n";
}


}

•  » » 8 months ago, # ^ |   0 I think if n=1 then your a[n-2] will become a[-1]. Maybe that might be the mistake. You should only write a[n-1] as the answer because a[n-2] is already zero.
•  » » » 8 months ago, # ^ |   0 n cannot be 1 according to given constraint in problem. (1<=k
•  » » 8 months ago, # ^ |   0 try using long long instead of int, integer overflow takes place if you take int.
 » 8 months ago, # |   0 Is there a greedy approach for D ?
•  » » 8 months ago, # ^ |   0 Used two pointer concept and it passed!
 » 8 months ago, # |   0 why my solution got accepted after changing int to long long https://codeforces.com/contest/1430/submission/95208979
•  » » 8 months ago, # ^ |   0 overflow may take place when int is used
•  » » » 8 months ago, # ^ |   +8 lol he already knows that xDDD...I guess he is asking there is no reason to overflow here and yet it is getting WA'ed.
•  » » » » 8 months ago, # ^ |   0 yes exactly xD
•  » » 8 months ago, # ^ |   0 are you using multiple accounts? because you do not have a submission using int, nor did you get a wrong answer on this problem.
•  » » » 8 months ago, # ^ |   0 please click on show unoficially you will see it xDD.
•  » » 8 months ago, # ^ |   +5 use this #define int long long would be life saving
•  » » » 8 months ago, # ^ |   0 thanks very much :)codingkshatriya
 » 8 months ago, # |   +5 Anyone can tell how to solve F & G ?
•  » » 8 months ago, # ^ |   +16 F is DP$dp[i][j]$ = minimum cost (in bullets) to beat $i$ rounds (and start the next round) with $j$ bullets remaining in your magazine.Note that since $j \leq 10^9$ you should use a map/associative array for that dimension.The initial state is $dp[0][k] = 0$. Each state can be the parent of up to two states, one with $j < k$ (no reload after round) and one with $j = k$ (reload after round; only transition to this state if you have enough time). A state may also "dead-end" if it is impossible to beat the current round from it; if all states dead-end the answer is $-1$.This fits in $O(n^2)$ or $O(n^2 \log)$ as the number of states increase by at most one each round (the $j = k$ state may create a new $j < k$ state, while the $j  » 8 months ago, # | 0 Can anyone tell me why this O(nlogn) solution for E gives TLE at test 41 solution link •  » » 8 months ago, # ^ | +9 vector insert is O(n) •  » » » 8 months ago, # ^ | 0 Okay. Thanks!!  » 8 months ago, # | +2 D was EVIL :( •  » » 8 months ago, # ^ | +31 DEVIL indeed!  » 8 months ago, # | ← Rev. 3 → 0 Is there any other way to solve E without using fenwick tree/ segment tree ? •  » » 8 months ago, # ^ | ← Rev. 2 → +10 count inversions any other way (merge sort , set -order_of_key) •  » » 8 months ago, # ^ | 0 use pbds if you are using c++, 95257988 •  » » » 8 months ago, # ^ | 0 codingkshatriya can you explain the logic of E. •  » » » » 8 months ago, # ^ | 0 For each position, we know what caharacter should come there, we have the initial string, so each time it is optimal to move that character which comes first, for example cdad, first position should be occupied by d, there are 2 d's but it's optimal to move the d in the second position to first, but string changes when we do that, it becomes dcad, if you notice all elements before the moved position, their index increments.So we can store the positions of all characters and every time we just have to know the changed position, which is just the number of elements greater than the current position that have been already moved, we can solve it using pbds ordered_set •  » » 8 months ago, # ^ | 0 It can be done without segment/fenwick trees. Because its a character string, we can keep prefix/suffix frequency arrays for both initial and reverse strings and maintain the answer. You can look at my code for reference. •  » » 8 months ago, # ^ | 0 adderall Very easy solution: https://codeforces.com/contest/1430/submission/95314914  » 8 months ago, # | +8 hi, can anyone tell me, what is hacking? and did it give score also? •  » » 8 months ago, # ^ | +8 not in educational and div.3 rounds. •  » » » 8 months ago, # ^ | +2 Does that mean an unsuccessfull hack would have no effect on your final score? •  » » » » 8 months ago, # ^ | ← Rev. 2 → +11 In Educational and Div.3 rounds neither successful nor unsuccessful hack gives you extra points. But in regular Div.2 and Div.1 you get +100 points for each successful and -50 for unsuccessful hack. •  » » 8 months ago, # ^ | 0 Once the 2-hour problem solving round is over, participants have the option, to see the solutions submitted by other participants and try to generate possible inputs, upon which these solutions might end up giving incorrect outputs. This is what hacking means. All of this has to be done in a 12-hour hacking phase just after the contest. Once this 12-hour phase is over, solutions are re-judged based on all the hacks generated. Hope this helps!  » 8 months ago, # | ← Rev. 2 → 0 Can C be solved using heap? This solution gave TLE but I just to know if there is any way to optimise it or if it can't be solved using a heap. This solution without heap worked correctly. •  » » 8 months ago, # ^ | 0 I would give u a better approach .. Just use the max 2 possible values each time and then work yourself on a case or two. You would get to know that you would always end up at 2 •  » » » 8 months ago, # ^ | 0 The second link is using the solution that you mentioned. But I never thought about it always ending at 2. In the cases that I tried it ended at 2 but I thought that it would increase for bigger cases. I just want to know if it can be done using a heap. •  » » » » 8 months ago, # ^ | 0 https://codeforces.com/contest/1430/submission/95294366 This solution uses heap taking the largest two elements every time and insert their ceil back into the heap for total of n-1 times . •  » » » » » 8 months ago, # ^ | 0 Thanks, I solved it using heap yesterday. •  » » 8 months ago, # ^ | ← Rev. 2 → 0 i believe x[2:] is costly operation(tell if i am wrong) and yes the approach is right here •  » » 8 months ago, # ^ | 0 Yes! i used a priority queue and got AC •  » » » 8 months ago, # ^ | 0 I solved it after I read your solution. My mistake was using a heap but not using the heap functions. I was using list operations and performing multiple heapify. Using heappush and heappush performs heapify on its own. Thanks a lot!  » 8 months ago, # | 0 First I convert 1000111000 to [1,3,3,3] then if the chuck is greater than one than i add one to my ans , if the chuck is equal to one than i remove one from the biggest chuck remaining , 95255021 can someone point out what's wrong with the approach •  » » 8 months ago, # ^ | +3 An example test case is -> 1 13 1010010101111Your approach gives 6 while the answer should be 7The problem is that we should not remove from the biggest chunk because we may exhaust it early. The ideal way is to remove from the first chunk which is greater than 1. That way we can optimally utilize the chunks. In the example, it exhausts (1111) which could have been used for 6th element while we could have reduced the (00) for the 1st element. •  » » » 8 months ago, # ^ | 0 thanks man. should have seen this. at this rate someday my rating will be lesser than the number of contests I participated.  » 8 months ago, # | +7 Prob C hurts me a lot. I even don't have time to catch up Prob D. •  » » 8 months ago, # ^ | +3 Dude I overcomplicated my C because I thought the solution to C should not be so obvious. Now I see that a brainless greedy works. -_- •  » » » 8 months ago, # ^ | ← Rev. 2 → 0 I also overcomplicated C .... took 1 hour.but what hurting me more is TLE on testcase 41 for problem E.so sad  » 8 months ago, # | +68 My screencast of getting 7th place [assuming I don't FST], along with solutions to all problems is being uploaded to my youtube channel. Youtube should finish processing it in 20-30 minutes or so. If you want to see it as soon as they finish processing, you can turn on notifications. Good morning and thanks to the authors for the cool problems! :) •  » » 8 months ago, # ^ | +16 I love the "Good morning everybody" you do at the beginning of your videos! •  » » 8 months ago, # ^ | 0 Sorry for asking, but what's FST? •  » » » 8 months ago, # ^ | +6 failed system tests •  » » » » 8 months ago, # ^ | ← Rev. 2 → 0 Thanks! •  » » 8 months ago, # ^ | ← Rev. 2 → +11 ur solution for E was just awsome or maybe how u teach.  » 8 months ago, # | ← Rev. 2 → 0 Nice Problemset. Was E a standard question of Fenwick Tree ? •  » » 8 months ago, # ^ | 0  » 8 months ago, # | -11 Why is this brute force wrong? (PROBLEM A) #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--){ int n, i, j, k; cin>>n; int flag=0; for(i=0; i<=334; i++){ for(j=0; j<=334; j++){ for(k=0; k<=334; k++){ if(3*i+5*j+7*k==n){ flag=1; break; } } if(flag) break; } if(flag) break; } if(flag) cout< •  » » 8 months ago, # ^ | 0 It is not wrong in a mathematical sense. It is just to slow. •  » » 8 months ago, # ^ | ← Rev. 2 → 0 when there's 1000 cases of n = 4, you will get TLE •  » » » 8 months ago, # ^ | 0 No I didn't get a TLE on this, I got hacked instead. •  » » » » 8 months ago, # ^ | 0 Yeah, you can get hacked if someone puts those test cases. •  » » » 8 months ago, # ^ | 0 I got hacked on that. Feels really sad.  » 8 months ago, # | ← Rev. 3 → 0 For some reason, I'm really bad at educational rounds... My last four ed-roundsAnd this one will be even worse (expected -64) •  » » 8 months ago, # ^ | +12 The problem for loosing rating in this contest has huge role of your mindset saying that "I will loose rating from previous pattern ,making you feel pressure and under pressure u don't do well". Thinking it to be any normal contest and being cool , you might have performed better.  » 8 months ago, # | ← Rev. 4 → +7 SweetSlightly over an hour since the end of the contest and already 500hacks.I'm not complaining though as it may seem. Just noticing a funny fact •  » » 8 months ago, # ^ | 0 yeah most of them are for problem A, people have forgotten to break their nested "for loops" (those who have used this looping concept). most hacks for TLE in that  » 8 months ago, # | +2 Anyone else used Dp for problem A? XD •  » » 8 months ago, # ^ | ← Rev. 2 → 0 I did the recursive sol exactly as yours •  » » 8 months ago, # ^ | +5 I thought about something like this initially. But decided that it is quicker and less error-prone to write brute-force that should converge quickly  » 8 months ago, # | +2 A lot of successful hacking attempts for A & B. It's sad. •  » » 8 months ago, # ^ | +3 My solutions got hacked in both. So sad. •  » » » 8 months ago, # ^ | +3 Do you have any reasons why we got tle in B Especially java users? while looping backwards*. •  » » » » 8 months ago, # ^ | 0 Trying to figure out the same as it happened to me too :( •  » » 8 months ago, # ^ | 0 for java users B — Arrays.sort() was the issue •  » » » 8 months ago, # ^ | 0 But many has used that method. Just the difference I found is that the accepted one is one in which they are looping from i=0 to k . •  » » » » 8 months ago, # ^ | 0 Idea is correct. but Whoever has used Arrays.sort() in java then you can hack that solution by$TLE$. Arrays.sort() is O(n^2) in worst case. google for that particular testcase and you can hack all java solution which uses Arrays.sort(); •  » » » » » 8 months ago, # ^ | 0 Thanks ..I came across this after reading your comment.  » 8 months ago, # | 0 Does anybody have proof for the fenwick tree solution of E. Why wouldn't there be a case where we need lesser number of moves than taking it to the last possible position. •  » » 8 months ago, # ^ | 0 So, here is my solution : First take the reverse of the given string and try to get all characters into position starting from the last.Some sort of proof for this : It is always optimal to choose the rightmost matching character in the original string to swap and get to the final intended position. Assume it takes X moves for rightmost character to get into final position. Now any other character Y will take X + dist(rightmost character, Y).Now, on why it is better to start fixing from the end of the string : When we try to fix some position before fixing the positions to the right of it, then this character might get displaced once again when some other to the left of the fixed character needs to go to the right of it. •  » » » 8 months ago, # ^ | 0 is it necessary to move from right to lefti reversed the string and tried moving from left to rightgetting wrong answer on test 41. •  » » » » 8 months ago, # ^ | 0 It should work. The logic may slightly change though like you must take the leftmost matching character instead of the rightmost etc., •  » » » » » 8 months ago, # ^ | 0 Hi thanks for the reply, actually i was using int instead of long long.  » 8 months ago, # | 0 I want to know D's solution, shouldn't it be traversal string simulation operation? I have seen a lot of AC codes, they all have found a certain pattern, can someone tell me this pattern? •  » » 8 months ago, # ^ | 0 Let's say there are various segments of same elements, so one thing that you can see clearly is that you don't want to merge two segments, right? Now if the segment at front has size 2 or greater you can simply delete one of its element and then delete this segment. But what if our segment at front has size 1. In the first operation you want to delete a number other than this segment, so you can do it by deleting from any segment after this and size greater than 1. It will basically create a suffix with ones only and you just want to find the size of this suffix. the answer will be number of segments initially — (suffix length/2). •  » » » 8 months ago, # ^ | ← Rev. 2 → 0 mafailure Can you please explain the solution w.r.t to 1000100 ?If I first take i = 7 string becomes 00010,Now if I take i = 1 string becomes 10Now if I take i = 1 string is empty ans is 3, but it should be 4, can you help me with that? •  » » » » 8 months ago, # ^ | 0 make a vector of lengths, in this case it will be v={1,3,1,2};now first length is 1 so we need a length>2 ahead in the vector or the last length==2 if any of the condition met then we can reduce that length by 1 if both these conditions are false then we have to forget about a lengthfor clarity see this https://codeforces.com/contest/1430/submission/95243326 •  » » » » » 8 months ago, # ^ | 0 what do you mean by "last length is 2" ? •  » » » » » » 8 months ago, # ^ | 0 if we encounter with length==1 then we need a length of 3 or more or the last length 2 or more •  » » » » » » » 8 months ago, # ^ | 0 so in 1000100 I can take i = 7 right? since last length is 2 •  » » » » » » » » 8 months ago, # ^ | 0 hmm •  » » » » » » » » » 8 months ago, # ^ | 0 but that would leaves us with string 00010, now when i just take i = 1, string becomes 10, and now the answer is only 3, but when I take i = 2 in the first operation it can become 4, so how does it work ? •  » » » » » » » » » 8 months ago, # ^ | ← Rev. 2 → 0 here our vector of length will be v={3,1,1} now first length is 3 so it is safe then we have 1 and none of the condition are met so we have to drop the last length that is so ans will be 2.. idk what do u mean by i •  » » » » » » » » » 8 months ago, # ^ | 0 pinged in DM  » 8 months ago, # | -16 Not noticing the unusual time made me miss the contest. •  » » 8 months ago, # ^ | -6 10 downvotes for expressing my mistake and feeling sad for missing a contest, ouch.  » 8 months ago, # | +8 Can someone explain the "flow" solution for G?I only know the bitmask dp solution. •  » » 8 months ago, # ^ | 0 Can you explain what the bitmask dp solution? •  » » » 8 months ago, # ^ | ← Rev. 4 → +6 Yes.You can find that the number you use can be convert into$0,1,2,3...k,(k\leq n)$.Then you can add node in increasing order of$a_i$.When adding a node you must check whether this node can be added.The time complexity is$O(n*3^n)$,but in fact the states are much less.This is the code during the contest: https://codeforces.com/contest/1430/submission/95237357However because of its huge constant, it's hacked after the contest by the test:18 0(time: 3000ms+)But we can reduce the enumeration of the maximum$a_i$.Then it can pass.Ac Code:https://codeforces.com/contest/1430/submission/95257898 (331ms)  » 8 months ago, # | 0 In fact, problem e is not difficult, but I don't have enough time to complete it. The slow hand speed is also one of my flaws. .  » 8 months ago, # | -22 My solution is a perfect O(N) solution. But it got hacked for TLE. Problem A of this Educational round 96. 1430A - Number of Apartments Kindly look for yourself and tell me why this happened @ BledDest adedalic fcspartakm Submission : 95203970 •  » » 8 months ago, # ^ | 0 python is too slow, change to c++ •  » » » 8 months ago, # ^ | 0 Bro I submitted in PYPY3, that's supposed to be faster than Python. And since the complexity is correct there shouldn't be any problem in the language right? Like the setters should make sure it gets submitted in all languages if the required complexity is fulfilled •  » » » » 8 months ago, # ^ | 0 Your code is taking 1247 ms for t = 1000 and n = 1000 for every t. Try it in Custom invocation. •  » » » » » 8 months ago, # ^ | 0 Exactly my point , given the complexity is correct which is O(N), It's showing TLE ie time taken is above 1 sec. Which shouldn't happen for the given values. •  » » » » 8 months ago, # ^ | 0 You should calculate dp once for the max value of n = 1000. But you do calculate it every time. •  » » » » » 8 months ago, # ^ | 0 Yes, I thought about ,but considering the situation for T = 1000 and N = 1000 , it should be quite evident that O(N) should work •  » » 8 months ago, # ^ | ← Rev. 2 → 0 This solution is O(tN) at best and on each iteration it creates at least six three-element dictionaries. Six million three-element dictionaries are not free •  » » » 8 months ago, # ^ | 0 Dictionary with 3 elements can be considered as constant, it occupies O(1) complexity , how does it matter?? •  » » 8 months ago, # ^ | 0 Hey, You can check out my PYTHON TEMPLATE for making your Python code run faster.Also, I have been a Python Coder for quite some time now, but sometimes even I have to submit a program in C++.Mentioned below are some areas for which you should not choose Python as a language to code your solution :(1) Recursion with a depth > 1000.(2) If you need to apply lower_bound or upper_bound on a set as Python doesn't support it.(3) String problems with the length of string > 1e5 and your solution is supposed to have a time complexity of nlogn.Hope this helps you. •  » » 8 months ago, # ^ | 0 I was a Python coder myself. Normally PyPy is faster, but once I submitted a problem in PyPy and it got TLE (the same code was later accepted in Python3). So I had to decide which to use where.Even though a solution is O(n) and optimal does not guarantees an AC in every language. Internally Python is slower than C++ and a more efficient solution in Python may get TLE whereas a less optimal solution may get an AC in C++. Even though there is a time relaxation in the background for some languages, that is not enough to get an AC.Therefore sometimes it is written that_ a solution is not guaranteed in every language_.  » 8 months ago, # | +3 Can somebody prove problem D solution ?  » 8 months ago, # | 0 In problem D :Why is it "always" optimal to pick just next chunk with more than one value and not any other chunk with more than one value , whenever we encounter 1 ? •  » » 8 months ago, # ^ | 0 If you don't choose, the just next valid chunk will be erased at some step, thus not better than the solution. •  » » » 8 months ago, # ^ | 0 Thanks. This makes sense.  » 8 months ago, # | 0 Can somebody prove the solution to D ?  » 8 months ago, # | 0 If someone has got a little free time, can they mind explaining to me dp approach for solving problem A. Thanks. •  » » 8 months ago, # ^ | 0 A dp solution for such a problem would be based on the observation that if we got a solution for some n, then we can simply construct a solution for n+3, n+5 and n+7, each by adding that number to the set of numbers in the soluttion.So start at zero and go up to n. Foreach number if there is a solution, construct the next three soulutions and store them.This will finish after n loops with solutions to all numbers in range 0 to n.  » 8 months ago, # | 0 where are the editorials?  » 8 months ago, # | 0 How to solve D using Binary Search ? It has BinarySearch tag.  » 8 months ago, # | 0 Is there a way for java users to solve problem B, because I used Arrays.sort() and got hacked. Collections.sort() is even slower. If we use a priority queue then it has insertion and deletion time complexity of NLog(n) and is a min-heap so it will only work for some cases. So what is the alternative?? •  » » 8 months ago, # ^ | +3 Use mergesort Or sort Array of Object instead of Array of Primitives. Arrays.sort() uses quicksort for which worst case time complexity can be O(n^2) (only in case of primitve data type). •  » » 8 months ago, # ^ | 0 HarnoorSta7 has already pointed out. So, we got a TLE because Arrays.sort(int[]) uses quicksort which can have a worst case complexity of O(n^2) when the array is almost sorted. Now Collections.sort(List) is indeed slow because of non-primitives but it is still O(nlog(n)) in worst case because it uses Tim-sort instead of quick sort. So, I think it would not be a TLE if we used Collections.sort(List) in this question. •  » » » 8 months ago, # ^ | 0 Thanks for the link. Java was a lie for me. All the java accepted solutions I saw are using Arrays.sort() for int. Let's see how many java users survive for question B after final testing is completed.RIP java users!! •  » » 8 months ago, # ^ | +3 To avoid worst case of Arrays.sort() function for primitive data types which is O(n^2), first shuffle randomly the elements in the array then use Arrays.sort() function. The function which I use to sort the array is-static void sort(int[] A){ int n = A.length; Random rnd = new Random(); for(int i=0; i  » 8 months ago, # | 0 Can somebody please tell me why my solution on problem A doesn't get TLE on a test with 1000 of 1's in input? This is kind of a max text and it's not even close to TLE (around 300ms). •  » » 8 months ago, # ^ | +5 Hi Max cases: 1000 & worst test: 1000. loop1: break at worst case 1000/3 = 330 loop2 break at worst case 1000/5 = 200  Your code at worst case: 330*200*1000 about 6e7 < 10e8 so it's fine. Note: Expected to be 10^8–10^9 simple operations per second, in C++ or Java. Less for Python, about 10^7. •  » » » 8 months ago, # ^ | 0 But if I have 1 as n, my fors don't break at all. •  » » » » 8 months ago, # ^ | +2 When u get the answer and b = false, the both loops will break coz of "&& B" in loops. •  » » » » » 8 months ago, # ^ | 0 Yes, but if the answer is -1 it wont •  » » » » » » 8 months ago, # ^ | +2 You 're right, My apologies I was wrong. Hope you get the correct answer soon. •  » » » » » » 8 months ago, # ^ | ← Rev. 2 → +2 When used "long long" instead of "int" in same code got TLE and don't know why. 95291943  » 8 months ago, # | ← Rev. 2 → +5 I'm almost sure the intended solution for problem G doesn't involve Simplex, but if you know this method and you prove (or assume :P) that the coefficients found by the algorithm are all integers, you can get a really quick accepted.Also, this solution should work fast enough even if$n<=100$and$m<=n*(n-1)/2\$
 » 8 months ago, # |   0 95241114 Why is this solution showing unsuccessful hacking attempt even though it shows compilation error in online IDEs?
•  » » 8 months ago, # ^ |   +4 just so you know, in hell exists a special place for A-problem hackers!
•  » » » 8 months ago, # ^ |   -14 Nd there are some dumb people like you whose A-problem gets hacked...lol
•  » » » » 8 months ago, # ^ |   +3 It saying the green pupil. just so you know it is infinity number of the way to hack every problem A solution.
 » 8 months ago, # |   0 95295302 Can someone tell me how to optimize it to have an AC. This gives TLE. I saw solutions of other people with the exact same method having AC. Please help! Thanks!
•  » » 8 months ago, # ^ |   0 The problem is Arrays.sort() I think. It uses quick sort, whose worst-case time complexity is O(n^2). Try using Collections.sort() instead.
 » 8 months ago, # |   0 After reading the first 2 problems, I am pretty sure the problem setter was watching the water jug scene of Die Hard 2 while writing these problems.
 » 8 months ago, # |   0 Can someone plz help me why my solution shows TLE for the Barrels problem of today's div 2 B Here's the link-https://codeforces.com/contest/1430/submission/95296320
•  » » 8 months ago, # ^ |   +3 Probably Arrays.sort(arr); is the problem there.
•  » » » 8 months ago, # ^ |   0 But i saw others code and they have done the same.The only difference between them and mine code is that they used a for loop to count the summation and I used a while loop. Can u plz tell why it's happening.
•  » » » » 8 months ago, # ^ |   0 https://codeforces.com/blog/entry/83538?#comment-709446Its a specific hack for the java sorting function. It makes it really slow, something like O(n2) if Im not wrong.https://pt.wikipedia.org/wiki/QuicksortYeah, it says that the worst case for Quicksort (java's sort) is O(n2)
•  » » » » » 8 months ago, # ^ |   +3 Ok..Thanks for your kind response.Will definitely look into it
•  » » » » 8 months ago, # ^ |   0 The worst case can be converted to average case if we shuffle the array before sort. All arrangements will have equal probability and worst case will be as rare as any other case. This might be helpful.
 » 8 months ago, # |   0 Me after using x / 2 + x % 2 in rounding up in the questions
 » 8 months ago, # |   0 Please, can someone proof C solution? Thanks.
•  » » 8 months ago, # ^ |   +7 We just need to proof that an answer less or equal to 1 cant exist. If (a+b)/2 rounded up is 1, then 1 <= a+b <= 2. Its impossible to get a+b <= 2 if n>=2, so the minimum possible answer is 2.
 » 8 months ago, # |   +67 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
•  » » 8 months ago, # ^ |   +2 As last contest. This way is really better. Thanks for improve CF continually.
•  » » 8 months ago, # ^ |   +1 Can I ask a question? What does it mean to remove cheaters? According to my understanding, cheaters should be counted as zero points and kept in the rating change list.
•  » » 8 months ago, # ^ |   0 wait removing cheaters ? are you removing them manually or what ?
 » 8 months ago, # | ← Rev. 2 →   +1 No idea why my submission for Problem B gives TLE (got hacked in the hacking phase) Can someone please check? UPD: Got it fixed. Arrays.sort() is the problem here. Aaah, this thing ruined my contest big time. Why you implement it via quick sort java. Whyyyyy? 
 » 8 months ago, # |   -24 In Problem A I used two pointer method.Like this lp(i,mx+1) { j=0,k=mx; while(jn) { k--; } else { j++; } } But still got WA .Why?
•  » » 8 months ago, # ^ |   0 That loop stops to early while(j
 » 8 months ago, # |   +11 editorial?
 » 8 months ago, # |   +11 Where are the editorials?
 » 8 months ago, # | ← Rev. 2 →   +11 Editorials Please BledDest
 » 8 months ago, # |   0 When will the tutorials be published?
 » 8 months ago, # |   0 Are some test cases intentionally left out for such contests?
 » 8 months ago, # |   0 Is there an available editorial?
 » 8 months ago, # |   0 Is it possible to get all the test Cases for the problem from Somewhere. My Solution for D fails on 149th input of test case 2. If not it would be great if someone provides some good cases for checking the fault in my code . I have tried all the cases given in the comment section and all the outputs(from my code) have matched with their expected output.
•  » » 8 months ago, # ^ |   0 yes , is there some way to download all test cases ?
•  » » 8 months ago, # ^ |   +2 It's a bit hacky, but you can sniff the test case by hardcoding something like if (test_case==149) and print it out in a submission.
•  » » » 8 months ago, # ^ |   0 It was a Cool Idea , I got the failing testCase and my error as well. Thanks a lot
 » 8 months ago, # |   0 Why editorial is not published yet?
•  » » 8 months ago, # ^ |   0 Look Carefully, it's there
 » 8 months ago, # |   +12 Very happy to get First-AC at problem E&G.
 » 8 months ago, # |   0 Problem E was awesome.