By awoo, history, 6 months ago, translation,

Hello Codeforces!

On Dec/18/2021 18:35 (Moscow time) Educational Codeforces Round 119 (Rated for Div. 2) will start. Please, note the unusual start time.

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

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

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

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

Good luck to all the participants!

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

Hello once again, Codeforces!

Almost 5 months have passed since we organized the Harbour.Space Scholarship Contest 2021-2022. It’s been quite a tough challenge with more than 15,000 participants. However, we were able to select the ones who were ready to take the opportunity and join Harbour.Space this year. In addition to the contest, we carefully reviewed all scholarship applications and awarded a total of 11 students.

We would like to introduce you our Competitive Programming Scholarship Winners who have already arrived to Barcelona:

aniervs, MaksymOboznyi, mhq, Meijer, bthero,windazz, DimmyT, Batrr

We are looking forward to achieving incredible results with our new ICPC teams. One of them, Harbour.Backspace (MaksymOboznyi, mhq, Batrr), has already finished in 3rd place during Moscow Workshops. We wish them the best in the upcoming contests.

As usual, we are always excited to see Codeforces participants as our students here at Harbour.Space

UPD: Editorial is out

• +206

 » 6 months ago, # |   +13 Excited for the contest, Wishing everyone high ratings in last Educational Round of 2021.
•  » » 6 months ago, # ^ |   -6 you to
•  » » 6 months ago, # ^ |   +230 > last Educational Round of 2021 he doesn't know
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -52 -_-
•  » » » 6 months ago, # ^ |   0 lol
•  » » 6 months ago, # ^ |   +4 No please don't say that
•  » » 6 months ago, # ^ |   +1 liar
 » 6 months ago, # |   -18 forward Kazakhstan
•  » » 6 months ago, # ^ |   -11 alga kazakhstan
 » 6 months ago, # | ← Rev. 2 →   -19 I just hope that I do not become Pupil again after this contest.
 » 6 months ago, # |   -45 why edu round
 » 6 months ago, # | ← Rev. 2 →   -36 hope everyone has a good contest
•  » » 6 months ago, # ^ | ← Rev. 2 →   -28 Hope i am able to solve 3 question
 » 6 months ago, # |   +28 Always love educational round.
 » 6 months ago, # |   +70 Please, note the unusual start time. ok at this point I got lost, what's the actual usual time!?
•  » » 6 months ago, # ^ |   +3 17:35(Moscow)
 » 6 months ago, # |   -20 unusual unusual time(you know,usual unusual time means before 17:35)
 » 6 months ago, # |   +9 The start time in China is too unusual!
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 .
 » 6 months ago, # | ← Rev. 2 →   +21 Shouldn't it be BYE BYE educational 2021 XD...
 » 6 months ago, # |   -76 cheaters who registered in this round: nitin_05 ashokesen02 will they cheat again in this round? if so, will they not be caught and be rated again?! who will cheat better and drain more ratings from other innocent users?!?
•  » » 6 months ago, # ^ |   +21 Why you just keep on posting same thing again and again in every contest's announcement.My advice to you is not to focus on others whether they are cheating or not rather you should practice more and more to surpass those cheaters. And for cheaters they can become expert or CM by cheating but ratings without having knowledge is of no use they can't use it anywhere be it in Online tests,interviews.So just focus on developing skill and you can see positive outcomes after sometime :D.
•  » » » 6 months ago, # ^ |   +43 He is a spammer posting about scammers
•  » » » 6 months ago, # ^ |   0 Seems like it is taking me too much long time .
•  » » » 6 months ago, # ^ |   0 well said.
 » 6 months ago, # |   0 There are so many educational rounds! I wonder how to create problems so fast like this.
 » 6 months ago, # |   0 best
 » 6 months ago, # |   0 SIUUU
 » 6 months ago, # |   -22 Wasn't this time the usual one now it became unusual
 » 6 months ago, # |   +7 Why so negative?
 » 6 months ago, # | ← Rev. 2 →   0 I hope this round will be excellent! (as usual <3)
 » 6 months ago, # |   +1 Hope this time my rating will increase and my contribution rating will not go more negative.
 » 6 months ago, # |   -34 the round is shit
 » 6 months ago, # |   -26 speedforces
 » 6 months ago, # |   -26 C should not exist
•  » » 6 months ago, # ^ |   +4 A was harder than C, change my mind lmao
•  » » » 6 months ago, # ^ |   0 I was out of my mind watching people soved A within 5 min and i was still grinding on it at 45.
 » 6 months ago, # |   +19
•  » » 6 months ago, # ^ |   0 I can feel your pain.
 » 6 months ago, # | ← Rev. 2 →   0 I m not able to understand the 3rd test case of the C problem we can at max replace all '*' with 'bbb' and then also the rank will be 16 but it is asking for 20? Help me understand it. Be merciful on me.
•  » » 6 months ago, # ^ | ← Rev. 4 →   +6 If I am not wrong for the third test case of C 6 3 20 **a*** output -- babbbbbbbbb The strings are -- - a - ab - abb - abbb - abbbb - abbbbb - abbbbbb - abbbbbbb - abbbbbbbb - abbbbbbbbb - ba - bab - babb - babbb - babbbb - babbbbb - babbbbbb - babbbbbbb - babbbbbbbb - babbbbbbbbb btw was not able to solve it.. RIP
•  » » » 6 months ago, # ^ |   0 Thanks for the help i realized it when 2 minutes where left. and was not able to solve.
•  » » » 6 months ago, # ^ |   0 Why is the ordering not like this? What am I missing?a ab ba abb bab bba abbb babb bbab bbba abbbb babbb bbabb bbbab bbbba abbbbb babbbb bbabbb bbbabb bbbbab bbbbba abbbbbb babbbbb
•  » » » » 6 months ago, # ^ |   0 take the strings in a vector, sort it, the string will be lexicographically arranged.
•  » » 6 months ago, # ^ |   +9 The number of possibilities is not 16. In the first group of asterisks, we can have at most 6 'b'. In the second group of asterisks, we can have at most 9 'b'. So, the total number of possibilities is (6 + 1) * (9 + 1) = 70.You can fix the first group of asterisks with some number of 'b'. Then, you can have 10 different strings as you can adjust the number of 'b' in the second group of asterisks.
 » 6 months ago, # |   0 C is in a difference lever :v
 » 6 months ago, # |   +21 Back at it again :')
 » 6 months ago, # |   +3 Please any one give me a hint to solve E ??
•  » » 6 months ago, # ^ |   0 linked list
•  » » 6 months ago, # ^ |   +13 its actually just basic implementation [too easy for position E, I think]. For each query of type-1, find the nearest to the right query of type 2 which has the same $x$ and add an edge between these two indices. For each query of type 2, find the nearest to the right query of type 2 which has $x$ as the $y$ of current query and add an edge.this structure forms a forest.Then the value of each type 1 query in the final array is just the value of the root of the tree this index is a part of.
•  » » 6 months ago, # ^ |   +4 Try to build array by performing actions given in input in reverse order and store some useful information.
•  » » 6 months ago, # ^ |   +6 You can store for each x, all indices that have value equal to x in a vector, let's call it v[x].For the queries: set all elements equal to x to y, you can move all the elements from v[x] to v[y], use small to large to do this.
•  » » » 6 months ago, # ^ |   0 So it will be O(n^(3/2))?
•  » » » » 6 months ago, # ^ |   +3 No, it will be $O(N\cdot\log{N})$, each time you merge two vectors, the resulting vector will be at least two times the size of the small vector, so each element will be moved from a vector to another at most $\log{N}$ times.Note that you swap the vectors if needed to move always from the smaller to the bigger, just using swap is $O(1)$ for most stl containers, like vectors, sets, maps.
•  » » » » » 6 months ago, # ^ |   0 Wow, interesting, thanks. And in this problem we could kinda do it in O(n) using deque instead of vectors, right? Since merge of deque is O(1).
•  » » » » » » 6 months ago, # ^ | ← Rev. 3 →   +6 Are you sure that deque's merge is O(1)? cppreference doesn't mention it, and considering how deques work, I think it is complicated to do it in O(1), I am not sure tough.With a conventional double linked list you can do that, but I think deques are something more complex.
•  » » » » » » » 6 months ago, # ^ |   0 Crap, I thought deque in c++ IS a conventional double linked list. Thanks for pointing out. Now I need to go and check if deque id double-LL at list in my python... :)
•  » » 6 months ago, # ^ |   +19 I think simplest solution is to iterate the queryies from last to first. We maintain a transision table, no tree or something complecated needed.see 139792544
•  » » 6 months ago, # ^ |   +1 My solution uses array of linked lists.For query of the form 1 x, we add index of x (which is equal to current number of appended elements so far) to the end of the linked list located at array[x].For query of the form 2 x y we move all elements of the linked list located at array[x] to array[y].At any given point, array[val] stores all the original indices which ended up holding the value of val. https://codeforces.com/contest/1620/submission/139814623
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 If you execute the operations from the last going backwards you can keep&update a mapping for each number quite easily. At the start, mapping[x] = x for every x. Then: type 1, append mapping[x] to the result type 2, update mapping[x] = mapping[y] then print reversed(result)
 » 6 months ago, # |   +7 I didn't have time but I think problem G can be solved using inclusion-exclusion for each mask of subsequence [where the value of each mask represents the number of strings which are subsequences of all strings which have bit set in the mask]. Is it the right idea?
•  » » 6 months ago, # ^ |   +6 Yes, I solved it in this way.
•  » » » 6 months ago, # ^ |   0 I tried to do it using inclusion-exclusion.Struggled with MLEUsed vector of size 1<<23 * 26. Got MLE https://codeforces.com/contest/1620/submission/140442689Changing vector to arr(local variable) didn't work. Again changed the vector to global array. It got acceptedhttps://codeforces.com/contest/1620/submission/140443390
 » 6 months ago, # |   +17 Can E be solved with some modification to dsu?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 SpoilerYes, you can solve the queries in reverse by storing the most recent parent of each integer $x$, then whenever you find a query of $type$ $1$ you should add the parent of $x$.Solution code: 139832507
•  » » » 6 months ago, # ^ |   +1 thamks so much. what does this mean: if(~qr[i].second) what does '~' do?
•  » » » » 6 months ago, # ^ |   +1 if (~qr[i].second) is equivalent to if (qr[i].second != -1)
 » 6 months ago, # |   0 Can I improve my delta by hacking someone else's solution?
•  » » 6 months ago, # ^ |   0 No
•  » » 6 months ago, # ^ |   +9 Actually, you can , if you hack someone else's solution whose ranking above yours.
•  » » » 6 months ago, # ^ |   +3 OK... If predictor is right I need 5-7 more delta to become expert. Roughly, how many solutions should I hack to get it?
•  » » » » 6 months ago, # ^ |   +19 all of them :)
 » 6 months ago, # |   +11 I eagerly wait to know the author of problem D
•  » » 6 months ago, # ^ |   0 I just needed one more minute to submit my solution.. ://///
 » 6 months ago, # |   0 I didn't get AC for B until there was exactly 1 minute left because I used int instead of long
•  » » 6 months ago, # ^ |   0 It's because Base*Height may exceed int range.
 » 6 months ago, # |   +13 HELP nitin_05 cheated again!!!!!
•  » » 6 months ago, # ^ |   0 The attempt was so blatant lol, Dude commented the block of code and then wrote the same code and thought that he wouldn't be caught by the CF plag system. The first thing any plag tool does is to wipe off all the comments, spaces and indents and read the code as one single line. How dumb can one be.
 » 6 months ago, # |   +6 Was I the only one who found E much easier than both C and D.
•  » » 6 months ago, # ^ |   0 No.
 » 6 months ago, # |   +6 12 wrong submissoins on C. I just want to die
•  » » 6 months ago, # ^ |   +45 please don't die
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 metoo.. still don't know why the 4th test case doesn't work out -.-
•  » » » 6 months ago, # ^ |   +3 My 4th test case is wrong due to integer overflow.I am doing suffix product of an array which lead to runtime errorhttps://codeforces.com/contest/1620/submission/139859032Handled the overflow here
•  » » » » 6 months ago, # ^ |   0 Thanks, it was helpful.
•  » » 6 months ago, # ^ |   0 I learned that lesson ones or twice (or more?) and now I try to avoid the guess game — today (again) I had to write a tests with brute force function that generates all possible strings for a small templates, that can be easily understood. Sorted them and compared to my solution for every X. 15 extra minutes was enough to find I had >= instead of > in some place. Some times I search for this 30 — 45 — 60, but it is definitely giving me more than wild guessing.
 » 6 months ago, # |   +3 My approach for Problem E: Replace the NumbersThe idea is pretty similar to 365A: Knight TournamentSuppose an element $x$ is appended to the end of the array at the $j^{th}$ query. We can make the following 2 observations: The final value of this element would not depend on any Type-1 or Type-2 query strictly to the left of the $j^{th}$ query. If we have two Type-2 queries strictly to the right of the $j^{th}$ query, say at indices $k_1$ and $k_2$, (such that $k_1 < k_2$), and they both operate on $x$, i.e they both instruct to change the value of $x$ to $y$ or $z$ respectively, then the first query takes precedence. So, if we process the queries in reverse order, then by the time we reached the $j^{th}$ query (counting from zero), we would have all the information to restore the value of $x$, if we keep overwriting the values of $x$ in case of overlapping Type-2 queries.So, if we define $sink[x]$ as the value that $x$ should be currently converted to, we can process the queries as follows: Type-1 Queries: Just append $sink[x]$ to the result. Type-2 Queries: Update $sink[x] = sink[y]$. Finally, reverse the $result$ vector.Implementation
•  » » 6 months ago, # ^ |   0 I tried using DSU (along with a hashmap and a pointer array), but am getting WA on Test 4 itself. What could be wrong with my code? My Submission. Thanks.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Try this simple testcase11 5
•  » » » » 6 months ago, # ^ |   0 The output's 5, as expected...
 » 6 months ago, # |   0 How to solve E?? is there any way to pass test case 5??
•  » » 6 months ago, # ^ |   +75 no, there is no way to pass test case 5
 » 6 months ago, # |   +3 I took more than an hour to solve C but only 7 minutes for E.
 » 6 months ago, # |   0 Please, help me. Why I get WA on C: https://codeforces.com/contest/1620/submission/139816488 ?
 » 6 months ago, # |   +18 I think many people passed G with $O(26*n*2^{n})$, but it wasn't intended right?
•  » » 6 months ago, # ^ |   +41 Unfortunately, it was hard to cut all of them off. The model solution works in $O(2^n \cdot (n + A))$, but its constant factor is kinda big so I couldn't set $n = 24$. In retrospect, perhaps it would be better to swap F and G and set something like $n = 20$ instead of $23$.
•  » » » 6 months ago, # ^ |   +28 Yeah, my complexity is the same. Yes, swapping F and G could have been better.
•  » » 6 months ago, # ^ |   0 How do you do it with that complexity? Is it even easier than $O((n + 26) 2^n)$? I can't imagine a solution where it is not immediately clear how to optimize.
•  » » » 6 months ago, # ^ |   +10 Lol me too, but I think what some people did was to calculate for each mask, the contribution of each alphabet by iterating on all set bits instead of using the precomputed values and taking the low bit of mask.
•  » » » 6 months ago, # ^ |   +18 One of the approaches I tried to cut off was based on the following dynamic programming:$dp[i][mask]$ — the number of different strings consisting of the first $i$ characters of the alphabet such that they are subsequences of every $s_i$ from the mask, and are not subsequences of any other $s_i$, with $O(A \cdot 2^n)$ states and $O(n)$ transitions from each of them.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -16 I used dsu like you in E but m getting mle and I have no idea why can anyone look into this .This would be a great help I encountered such thing first time my submission
•  » » » » 6 months ago, # ^ |   +2 For starters, you can look at this testcase Input3 1 1 2 5 2 2 1 5  Expected Output5  Your Output2 
•  » » » » » 6 months ago, # ^ |   0 thts ok but I was getting mle constantly , I dost know its reason
•  » » » » 6 months ago, # ^ |   0 same here. my solution. https://codeforces.com/contest/1620/submission/139812356
•  » » » » » 6 months ago, # ^ |   0 Not entirely sure about the reason for MLE, but your code does produce SIGKILL runtime error on the following input. Input6 1 1 1 5 2 3 3 2 4 1 2 1 4 2 3 9 I see a lot of contestants getting MLE on TC4, I wonder if they are making a similar mistake or it's the nature of the test-case. Do let me know if you figure out the reason.
•  » » » » » » 6 months ago, # ^ |   +4 infinite recursion in happening which is leading to stack overflow which is the reason for mle ig
•  » » » » » » » 6 months ago, # ^ |   0 Thank you. That makes sense.
•  » » » » » » 6 months ago, # ^ |   0 thnku very much
 » 6 months ago, # |   +9 Getting ready for a -100 LOL :p
 » 6 months ago, # |   0 I don't understand the gap
 » 6 months ago, # |   0 I'm curious what's test 2 here that's causing WA.https://pastebin.com/41BJXM9H
 » 6 months ago, # |   0 how to solve A?
•  » » 6 months ago, # ^ |   -10 Please don't ask me :((
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 Let $cnt$ is the number of $N$ between $s_i$ and $s_{n-1}$. $cnt = 0$ means $a_1 = a_n$ or $s_n = E$. $cnt = 1$ means $a_1 \neq a_n$ or $s_n = N$. Otherwise, there always exists a solution. SpoilerTry to simulate some test cases to figure out why this solution works:)
 » 6 months ago, # |   0 Why so tight constraints! :/
 » 6 months ago, # |   0 solved D after contest ended 3min :D
•  » » 6 months ago, # ^ |   -8 Same dude, 1 minor mistake let maxx be the biggest element in array i didnt check if there were any maxx-1 — s elements in the array if maxx%1=3
 » 6 months ago, # |   0 No greedy,that I cannot solve any problems.
 » 6 months ago, # |   0 can someone tell how to solve c?
 » 6 months ago, # |   0 One Doubt , I submitted 1st Accepted Solution to C at 1:08 and second at 1:18 if the first one gets hacked or FST , the second one's final verdict will decide my rank ?
•  » » 6 months ago, # ^ |   +3 The second one will contribute, the first one is kind of nullified by your second submission.
•  » » » 6 months ago, # ^ |   0 Thanks , In non educational Div 2 Rounds , Penalty for multiple submission (correct or incorrect ) is added in the standings while here no additional penalty is showing currently .
•  » » » » 6 months ago, # ^ |   0 I would have expected 10 minutes penalty per submission, the first one is free. But not sure.
 » 6 months ago, # | ← Rev. 2 →   0 Why is there TL on 5 test? Submission: https://codeforces.com/contest/1620/submission/139803575
•  » » 6 months ago, # ^ |   +22 Because your complexity is not good?
•  » » » 6 months ago, # ^ |   0 can you tell me what is the time complexity link of this solution, according to the constraints shouldn't this give solution gives tle?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +12 It's $O(q \log q)$.It uses small-to-large merging, unlike the person I replied to. Basically this line is very important: if (y.size() > z.size()). It can sound unintuitive but in total, every element gets copied from one vector to another only $O(\log q)$ times (it's similar in the idea to HLD and union-by-size in DSU). Proof sketchIf an element gets copied from y to z and y has $k$, then after copying z must have at least $2k$ elements. If this element is later copied from z to x, then after copying x must have at least $4k$ elements and so on. Basically every time an element is copied from one vector to another, the size of its container at least doubles, which means that it is impossible for it to be copied more than $\log q$ times.So in total it's $O(q \log q)$. Also y.swap(z) takes constant time (I didn't know this) so no worries there.
•  » » » » » 6 months ago, # ^ |   0 Ok I understand now, Thanks for such a clear explanation
•  » » 6 months ago, # ^ | ← Rev. 2 →   -11 never use unordered_map anti-hashing testcases existstill your complexity is bad as -is-this-fft said
•  » » » 6 months ago, # ^ |   0 Bad advice... If you want to pass anti-hash tests -> use your own hash function, genius
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   -11 or just use map instead of implementing your own hash functions(in this problem array is better)
 » 6 months ago, # |   +1 Really hard test case 3 in problem C for my small brain :(
 » 6 months ago, # |   -90 WORST round EVER!Emplemetionforces and speedforces combinedbruh
•  » » 6 months ago, # ^ |   +49 Actually this is more or less the defintion of educational rounds. If you do not like this you should not participate in them.
•  » » » 6 months ago, # ^ |   +37 lmaoo, no bad comments today because you performed well, sucker!
•  » » » » 6 months ago, # ^ |   +8 I love you, too, idiot :)
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 bruhthat was my third educational round for the last year or so
 » 6 months ago, # |   0 I didn't get D... Somebody please explain the third and fourth case
•  » » 6 months ago, # ^ |   +3 4th test case: 2 * 3 + 3 * 257=777
•  » » » 6 months ago, # ^ |   0 Why not 3*259=777
•  » » » » 6 months ago, # ^ |   0 That way you can't buy 7
•  » » » » 6 months ago, # ^ |   0 Then you can't buy the bag that costs 7 or the one that costs 77
 » 6 months ago, # |   +3 C has an overflow issue.. I got too many WAs because of overflow issue
•  » » 6 months ago, # ^ |   0 Same :( I spend like an hour trying to find what to issue was, only to realize after the contest that it was overflow :(
 » 6 months ago, # |   0 D drove me mad...qwq
 » 6 months ago, # |   +1 Why my solution got Memory Limit error? I couldn't see what is the problem. https://codeforces.com/contest/1620/submission/139812356
 » 6 months ago, # |   0 very cool problems! managed to solve A,B and C, and it somehow felt like A stumped me the most. thank you for a good round.
 » 6 months ago, # | ← Rev. 2 →   0 I'm surprised nobody mentioned a solution using DSU for E yet. It's the first thing I thought of, could there be something wrong? Initialize DSU to size equal to number of final array elements. Maintain two mappings: (DSU leader -> value) and (value -> DSU leader) Processing the queries seems straightforward..? The only things to be wary of are that when you need to merge values, the DSU leader of a component may change, and you need to make sure that only leaders are present in the mappings. In the end, the value for index i, processed in increasing order, is the value of its leader.
•  » » 6 months ago, # ^ |   0 I solved using DSU. But somehow my solution got Memory Limit error. And i don't know why. Here is my solution. https://codeforces.com/contest/1620/submission/139812356
•  » » » 6 months ago, # ^ | ← Rev. 3 →   0 I processed the queries online with DSU. https://codeforces.com/contest/1620/submission/139790412
 » 6 months ago, # | ← Rev. 2 →   0 I misread problem A and wasted 2 hours thinking about completely different problem :)
 » 6 months ago, # |   +8 I think D and E should have been swapped. E was as simple as simulating the process backwards.
 » 6 months ago, # |   0 Is there an etalon solution for problem E in Python3? My solution is O(n) but it exceeds time either on test 13 or sometimes on test 17 sometimes, even with fast IO
•  » » 6 months ago, # ^ |   0 Tried it in Python first too, got 2 TLEs, wrote the same code in C++, got AC.
•  » » » 6 months ago, # ^ |   0 Damn Python :)
•  » » 6 months ago, # ^ | ← Rev. 8 →   0 There is a lot — check out submission stats for a problem — and you can just switch to pypy3 sometimes it helps. is yours code AC in pypy3.PS. And to add: you are creating a lot of objects (lists) to encode input. Try to simplify it and get rid of them.P.P.S. Or maybe not and I am wrong (about creating a lot of objects) — cause your solution is faster than my when I run it on PyPy :)PPPS. Oh, no, I was right, but you have reall-really-really good "fast-input". My solution become twice faster with it — thank you very much!
 » 6 months ago, # |   0 Can someone help with this submission?https://codeforces.com/contest/1620/submission/139828156
•  » » 6 months ago, # ^ |   0 I think you have overflow issue.
 » 6 months ago, # | ← Rev. 2 →   0 Why is my code for C TLEing? 139829242 I think my complexity is O(n*k), where n<=2000, k<=2000
•  » » 6 months ago, # ^ |   -10 A given string may have b, but your program did not consider it.
•  » » » 6 months ago, # ^ |   0 "...that consists only of characters 'a' (a lowercase Latin letter) and '*' (an asterisk)."
•  » » 6 months ago, # ^ |   +6 You are overflowing LLONG_MAX (9e18) on the line temp *= (v[i]*k)+1;. This is undefined behaviour and you are TLEing because of this. Be sure to make sure that temp is not overflowed.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 Thanks, took care of it and it passed. My dumb ass wasted too much time on this foolish mistake during the contest ;_;
 » 6 months ago, # |   +11 This "hack" is borderline hilarious.
•  » » 6 months ago, # ^ |   0 haha~
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Check out Yugi.Hacker Submissions.
 » 6 months ago, # |   +3 C >> D
 » 6 months ago, # |   0 I don't know if the intended time complexity of the solution for D is $\mathcal{O}(N)$, but checking only 7 possible patterns for cost of each bag receives AC verdict. The patterns are:(maxm, 0, 0), (maxm, 1, 0), (maxm, 0, 1), (maxm, 2, 0), (maxm, 1, 1), (maxm-1, 0, 2), (maxm-1, 1, 1) where maxm is value of the maximum element divided by 3 and each tuple represents the number of coins of denomination 3, 1 and 2.Can anyone hack this solution? Submission:
•  » » 6 months ago, # ^ | ← Rev. 2 →   +1 That is correct, in the optimal answer you get at most one 1-token and at most two 2-tokens. That is because you can always break two 1-tokens into one 2-token and break three 2-tokens into two 3-tokens thus getting a better answer always: 1) (1+1) -> (2) 2) (2+2+2) -> (3+3)
•  » » » 6 months ago, # ^ |   0 Also, whenever cost of any bag is 1, we need to ensure atleast one 1-token is present.
 » 6 months ago, # | ← Rev. 2 →   0 Can anybody tell what I am doing wrong in C. solution link — c
•  » » 6 months ago, # ^ |   0 1 6 1 1 a*a*a* Your answer gives abaa. Correct answer should be aaa.
•  » » » 6 months ago, # ^ |   0 Thanks bro.
 » 6 months ago, # |   0 Can someone explain why my memory limit is exceeding in my solution for C 139817111
 » 6 months ago, # |   0 can anyone help me with this code : 139843473
 » 6 months ago, # |   0 How to solve problem F?
 » 6 months ago, # |   +1 I passed C after the contest when i used unsigned long long rather than long long. Codeforces doesnt support cry emojis
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/contest/1620/submission/139915280bro, can you help? I am stuck at this solution. I cant do anything to solve this :( please help. I think I too was facing the same issue. Please do see once.
 » 6 months ago, # |   +4 Thank you, too good to goodbye for 2021.
 » 6 months ago, # |   0 Am I the only one who found C much easier than D and E?
 » 6 months ago, # |   -16 nitin_05 cheated again!!!!!
 » 6 months ago, # |   +10 Why are contestants with ratings greater than 2100 being shown as official participants? will they be removed from the official list and then acc. our rating change will be calculated?
•  » » 6 months ago, # ^ |   +1 yupp.
 » 6 months ago, # | ← Rev. 2 →   0 E can be simply solved by small to big technique. just merge. here is my submission 139852514
•  » » 6 months ago, # ^ |   0 Oh great i didn't knew that it is some technique. Well i discovered already discovered technique.
•  » » » 6 months ago, # ^ |   0 Well, it only becomes "technique" when you prove it's complexity.
 » 6 months ago, # |   +1 The Rating Result?
 » 6 months ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 6 months ago, # | ← Rev. 2 →   +3 looks like problem A was the only problem nitin_05 could solve without buying solutions. XDhe got skipped except A
•  » » 6 months ago, # ^ |   +5 That problem not being skipped has worked to his disadvantage.If all the solutions would have been skipped then he would have no valid submission and the round would become unrated for him. However the solution for problem A not skipping means that the round is rated for him and due to only 1 correct submission , there's a huge negative delta.
 » 6 months ago, # | ← Rev. 2 →   0 HelloI was suspected to cheat on the problem A with Shanto65 and atau004.As you can see in this problem, it is very probable the everyone use this idea(and use a variable called cnt).Dear codeforces please review this again(by the way i didnt use ideone or something like that).
 » 6 months ago, # |   0 Fake Plagiarism check to ban me from my own account. TheThinker_08. This has now happened several times. What you cant even write your own code now. And The other guy @Paul_Liao_1457 got no penalty just cause his score is greater than mine. please just look into this I didn't do anything wrong or copy from anywhere still got a plagiarism check and got banned just what is this
•  » » 6 months ago, # ^ |   -6 I can see your account.
•  » » 6 months ago, # ^ |   0 Why I didn’t get penalty is because I solved the problem earlier than you.
 » 6 months ago, # |   -24 I am not able to log in to my account ushmitadutta but I am able to view it. Whenever I am wishing to log in it is showing the user disabled by the administrators. Whereas, I can see points have been added to the educational round. MikeMirzayanov Please Help.
 » 6 months ago, # |   -24 Hello awoo and MikeMirzayanov. This side ushmitadutta. I could see my account is there but I am not able to log in. It is showing disabled by the admins. Whereas, I can see my points getting added to the round. Please help.
 » 6 months ago, # |   -24 MikeMirzayanov Please reply to our queries. I am not able to login into my account even though I am able to see the page. My account is ushmitadutta
 » 6 months ago, # |   0 I have a question about E. in my opinion i have O(n) solution, but it gets TL at 5th test, can someone tell me what's wrong? Is it solution or it's just Python can't make it.https://codeforces.com/contest/1620/submission/139826532
•  » » 6 months ago, # ^ | ← Rev. 5 →   0 You are right about time complexity of your solution. What you are missing is that using input() for 500_000 of entries is too long. Look into other solutions to see "fast input" for python. Here is your solution with 1 variant of fast input: 139998877PS. And this fast-input: 139999694 I have just found in sur's solution is even better — it just made my solution twice faster. Thought, you should be careful with what you get — there will be unprintable symbols in your input.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 Thanks a lot, really appreciate it!...missclicked upvote(