By awoo, history, 5 weeks 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 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!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 tourist 6 82
2 LayCurse 6 158
3 LJC00118 6 159
4 mtsd 6 207
5 kefaa2 6 212

Congratulations to the best hackers:

Rank Competitor Hack Count
1 DreamingLeaf 20:-4
2 tzc_wk 12:-5
3 ooooxxxx 9
4 SSerxhs 9:-1
5 fireblaze777 10:-6
84 successful hacks and 270 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Ormlis 0:01
B rasengans 0:01
C gleb.astashkin 0:05
D tourist 0:12
E tourist 0:21
F Potassium 0:23

UPD: Editorial is out

• +281

 » 5 weeks ago, # |   -39 Hoping this to be a Successful Contest unlike previous one, Good Luck to all the Participants & May you get Positive Delta, cheers :)
 » 5 weeks ago, # | ← Rev. 2 →   -151 So Mike fixed the problem and found out the cause ?So many assholes downvoting these days like do you feel important when you downvote ? get a life retards we haven't seen any information about the problem yet
•  » » 5 weeks ago, # ^ |   +43 Very bad words for the community
•  » » » 5 weeks ago, # ^ |   -101 That's what haters deserve it's not for the community i don't see any problem in the question i asked
•  » » » » 5 weeks ago, # ^ |   +22 ok SupaHotFire, voting these days is unfair! but this isn't a reason to say bad words.
•  » » » » » 5 weeks ago, # ^ |   -83 I have seen worst it's not a big deal once a guy wrote to the authors **** you and your contest he got upvotes and his comment didn't get deleted and nothing happened anyway these bad words aren't for who's downvoting now they're right but it's for Who downvoted the 1 rev of my comment
•  » » 5 weeks ago, # ^ |   +11
•  » » 5 weeks ago, # ^ |   +30 Join the club bro. Literally everyone has been downvoted before its not a big deal.
•  » » » 5 weeks ago, # ^ |   +21 it's annoying when it gets repetitive everytime someone ask or say something i got downvoted alot before but not that repeatedly
•  » » 5 weeks ago, # ^ |   0 Sometimes maintaining silence also solves lot of problems.
•  » » » 5 weeks ago, # ^ |   -7 That's what I always do but sometimes say what you want I don't care about the downvotes after what i said
 » 5 weeks ago, # | ← Rev. 2 →   0 it's on mondayyy when we have school :'(
 » 5 weeks ago, # |   0 Good luck to everyone!
 » 5 weeks ago, # | ← Rev. 2 →   -22 Educational rounds are usually very good, hopefully this one too. Good luck to all!
•  » » 5 weeks ago, # ^ |   +44 I thought you would never post again.
•  » » 5 weeks ago, # ^ |   0 Ok liar.
 » 5 weeks ago, # |   -19 Is it rated?
•  » » 5 weeks ago, # ^ |   -14 Yes, it is.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +36 I thought you said you would never post again :p
•  » » » » 5 weeks ago, # ^ |   +7 Well, contribution is a tricky business
•  » » » 5 weeks ago, # ^ |   +14 I just troll, waiting for some downvotes :).
•  » » » » 5 weeks ago, # ^ |   +8 I see how it is. You get downvoted by asking for upvotes, and upvoted by asking for downvotes.
 » 5 weeks ago, # |   +57 thanhchauns2 go big or go bald...
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Definitely... Spoiler
•  » » 5 weeks ago, # ^ |   +2 For those who don't know
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 No matter what happens but for sure, he gained a lot of contribution points with this blog.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 He will get positive delta (cf predictor) but not enough for being cm numberofbaldpeople++;
 » 5 weeks ago, # |   +12 Thank you for this competition, it gives me a chance to advance.Tomorrow is China's Mid-Autumn Festival. happy mid-Autumn Festival!
•  » » 5 weeks ago, # ^ |   -7 ckmkb
 » 5 weeks ago, # |   -42 So, Codeforces is back Bigger Better Stronger you must check out the blog How to grow in CP
 » 5 weeks ago, # | ← Rev. 3 →   -30 Why people have time to dislike people's comments -_- , edited : OK
 » 5 weeks ago, # | ← Rev. 3 →   +9 Tomorrow is Mid-Autumn Festival, which is one of the Chinese traditional festlval. I wish all Chinese participants a Happy Mid-Autumn Festival!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +9 Wishing you a very blessed Mid-Autumn Day!中秋节快乐顺便一提我不是中国人。😅
 » 5 weeks ago, # |   0 Just became pupil in the last contest I gave hopefully I can maintain that today :)
 » 5 weeks ago, # | ← Rev. 2 →   0 DELETED
 » 5 weeks ago, # |   0 Excited for this round! Hope I'll increase my rating today :)
 » 5 weeks ago, # |   +16
 » 5 weeks ago, # |   -8 It seems like I'm facing my greatest fear in my first contest. Spoilerdiv3_master < div2_noob
 » 5 weeks ago, # |   0 usually comments start after the round ....
 » 5 weeks ago, # |   +4 i have always got negative delta in edu rounds lol hope to break the streak
•  » » 5 weeks ago, # ^ |   0 update negative again lmao:( b was a nightmare c saved my a*s from nosediving into pupil
 » 5 weeks ago, # |   +18 I feel dumb reading D from last 45 minutes and not even understanding how the answers for test cases are being constructed
•  » » 5 weeks ago, # ^ |   0 same here. today i am able to understand problem D.
 » 5 weeks ago, # |   +3 Don't understand why my code of problem C works less than 0.2s on local machine with 2*10^5 & 2*10^5 data while TLE on testcase 6...
•  » » 5 weeks ago, # ^ |   0 can you tell me how do you test for such large test cases?
•  » » » 5 weeks ago, # ^ |   -10 there are different methods just go into google you will find stack overflow articles according to each language..
•  » » » 5 weeks ago, # ^ |   0 Hello , in B : 2 3 4 . So why max pair is 6 . I just see AABBBCCCC , and max pair is 4 Can you explain it for me ? Thank you so much
•  » » » » 5 weeks ago, # ^ |   0 AAA --> there are two pairs (0,1) and (1,2) AAAA --> there are three paris (0,1), (1,2), (2,3) for n --> there are n-1 pairs. 2 3 4 --> (2-1) + (3-1) + (4-1) = 6 pairs!
•  » » » » 5 weeks ago, # ^ |   0 A block of n consecutive letters contains n — 1 pairs of equal characters; so AABBBCCCC contains 1 + 2 + 3 = 6 pairs of equal letters. If a letter coincides with two of the same type, it is counted in both pairs.
•  » » » » » 5 weeks ago, # ^ |   +8 Ah i already have the answer , but thanks guys
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 Maybe you didn't use ios_base::sync_with_stdio(false); cin.tie(0); I got TLE twice because of that...
•  » » » 5 weeks ago, # ^ |   0 i got 6 TLE...
 » 5 weeks ago, # |   +2 Hey! Is weightage for every question the same in Edu rounds?
•  » » 5 weeks ago, # ^ |   +5 Yes
 » 5 weeks ago, # |   0 Hope I can return to the candidate master.
 » 5 weeks ago, # |   0 Finally reaching to Pupil. Hopefully will reach the Specialist too soon.
 » 5 weeks ago, # |   +2 i don't understand how 4700 people solved C.
•  » » 5 weeks ago, # ^ |   0 It's easy, but I don't know why I always get TLE...
•  » » » 5 weeks ago, # ^ |   0 Yep, I also got a weird TLE verdict, but after placing the "Fast C++ I/O" stuff I got AC.
•  » » » » 5 weeks ago, # ^ |   +3 Thanks very much for this "Fast C++ I/O"... I got AC after adding it. But I'm really disappointed that this becomes the key point of AC or not...
•  » » » 5 weeks ago, # ^ |   0 the time complexity is about O(nlog(N) + mlog(n) )
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 .
•  » » » » 5 weeks ago, # ^ |   +5 Thanks. This is much faster. I never know it impacts so much.
•  » » 5 weeks ago, # ^ |   0 just because i didn't added fast I/O i couldn't solve C :"(
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 It's as simple as x+y — (sum of strength of all hero's) ,but since the values may over flow on addition, you need to do subtractions first. There will be two cases you just take min of both. Got accepted without fast I/O too.
•  » » 5 weeks ago, # ^ |   0 It was a just a implementation problem, it did not involved any particular algorithm. I and most people got stucked in choosing minimum condition else 7-8k submissions was not a big deal.
 » 5 weeks ago, # | ← Rev. 2 →   0 {deleted]
 » 5 weeks ago, # |   +1 How the heck we generate the 'M' sequences in D ? given that we have taken the difference between last element and every element for each item and sort it in increasing order ?
•  » » 5 weeks ago, # ^ |   0 I am sorry to be "that guy" but I think your question isn't very clear. I'd happily help (I solved D) but I can't if I don't understand the question!
•  » » 5 weeks ago, # ^ |   +8 i tried to use some priority_queue strategy. Start with a vector which contains all the last element of each array and on each step decrease one from a spot and recalculate the sum. think about (x,y,z,SM) -> (x-1,y,z,SM1),(x,y-1,z,SM2) (x,y,z-1,SM3) (and the priority queue is sorted by the SM) (i dont know if its correct but that was my idea)
•  » » 5 weeks ago, # ^ |   +10 I used a BFS ( sort of ) with a priority queue. Initially, i inserted the max sequence in the queue with its cost. After that, i kept on processing the top of the queue ( max cost ) and inserting its possible children ( i.e. 1 position different from the parent ) into the queue. Ultimately, since we are using a priority queue, we will visit the nodes in decreasing order. If we ever hit an unmarked node, we can return.However, we need to be careful about TLE and MLEs. In order to avoid those, i trimmed the priority queue ( used a set ) from the lower end, if we exceed a MAX LIMIT ( 1.5 mil in my case )
•  » » » 5 weeks ago, # ^ |   +9 Oh Geez!!! Is it that simple ? Thnx.
•  » » » 5 weeks ago, # ^ | ← Rev. 5 →   +3 Did a very silly mistake in D. Nice contest btw AC solution: https://codeforces.com/contest/1574/submission/129422495
•  » » » » 5 weeks ago, # ^ |   0 Use set of Vectors
 » 5 weeks ago, # |   +18 The only thing problem C educated me about was that even 1e18 is not enough to keep as infinity in your template
•  » » 5 weeks ago, # ^ |   0 In what cases the answer can exceed 1e18?
•  » » » 5 weeks ago, # ^ |   +2 You've got just 2 warriors of strength 1, the dragon has 10^18 atk and 10^12 def. The answer is 10^18 + 10^12 — 2.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 just use const int inf = numeric_limits::max(); It will work fine even with #define int long long
 » 5 weeks ago, # | ← Rev. 3 →   -12 Do I deserve them? Thanks for so many downvotes! Its make me feel happy.
•  » » 5 weeks ago, # ^ |   0 Im really bad man. Do you think so?
 » 5 weeks ago, # |   0 In C, my O((m+n)logn) solution gave TLE on the 6th test case. Any idea why?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 Perhaps you have a logic mistake in your algorithm. I thought I had it too but it turned out that I made a mistake and had to think of a different way to save myself from checking all exponentially many possibilities.Edit: oh, derp. I misread and thought that the question was about problem D. Sorry!
•  » » 5 weeks ago, # ^ |   +3 same but i somehow passed it by using fast I/O and "\n" instead of endl.
•  » » 5 weeks ago, # ^ |   +3 cin/cout are slow operators. Better use scanf/printf (cstdio library), or add ios_base::sync_with_stdio(0) In the beginning on your program, which boosts iostream performance (but beware of combining iostream/stdio in one program!) Just google "how to boost iostream", you should find some tips easily.
 » 5 weeks ago, # |   +4 How to solve D?. I thought of using max heap but was getting the wrong answer in test case 5.
•  » » 5 weeks ago, # ^ |   0 Me too, I was using a max heap too but also get a WA on test 5
•  » » » 5 weeks ago, # ^ |   0 I did a very silly mistake
•  » » » » 5 weeks ago, # ^ |   0 thx and I also did a very silly mistake(ACed now
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +4 View a build as a vertex in a graph (or rooted tree), there is an edge between two builds (vertices) if they only differ in one slot by 1, and the edge's weight is the strength difference of the two builds, then we can perform something like Dijkstra on the source, which is the optimal solution if there are no banned builds (the build consisting of the last item in each slot). we iteratively find a nearest (with lowest strength loss) new vertex (build) like what Dijkstra's algorithm does, and as soon as we find a valid build, print it.
 » 5 weeks ago, # |   +23 Meaningless F with the easiest gf knowledge
•  » » 5 weeks ago, # ^ |   +2 What is "gf"?
•  » » » 5 weeks ago, # ^ |   +1 I think it is generating function.
•  » » » 4 weeks ago, # ^ |   0 something I don't have :(
•  » » » 2 weeks ago, # ^ |   0
•  » » 5 weeks ago, # ^ |   +51 well… it would be easier if one observe that there are at most O(k^0.5) kinds of length.
•  » » » 5 weeks ago, # ^ |   +16 Yeah, this is how I've seen this problem solved before. I'm interested in how you would do it with GF, is the complexity better?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Removed.
•  » » » » 5 weeks ago, # ^ |   +15 I'm weak in GF, so you can ask alpha1022 for more information.Let $A(x)=\sum\limits_{i=1}a_ix^i$ be the OGF of subarrays, $a_i$ is the number of valid subarrays whose length is $i$.Let $B(x)$ be the OGF of ways to make the whole array and $[x^m]B(x)$ is the answer.It's easy to show that $B=1+A+A\times A+A\times A\times A+\cdots=\sum\limits_{i=0}A^i=\frac{1}{1-A(x)}$, so you can compute the inverse of $1-A(x)$ in $O(n\log n)$.
 » 5 weeks ago, # |   0 nice problems but i'm wondering why my f is wrong answer on test 13 QAQ
 » 5 weeks ago, # |   0 In problem D, I was stuck on this approach and was getting WA on test 11. Here is my approach: We can see that $4^{10} > m$. Initially we can consider the case where we take all the last elements. We define a variable $p=1$, denoting total number of ways with current elements. Then we can greedily add elements to our set from each row until $p \leq m$, each time we add element from such row which has largest latest element (from end). Then we can generate all sets and maximize our answer. But I can't understand why this approach is wrong. :(
•  » » 5 weeks ago, # ^ |   0 If I understand your solution correctly it is similar to the one I thought at first.Why do you think adding the element from the row which has the largest latest element produce the next bigger permutation? I believe this is not always the case.
•  » » » 5 weeks ago, # ^ | ← Rev. 6 →   0 I think I did not make it clear. Let's say we take $x_i$ (number of elements that are available for us) elements from $row_i$.Also we take all the elements that are equal to the last element we entered. Then we stop when $x_1 * x_2 * ... * x_n > m$. Now, my claim is that any other combination which contain some element from some row $i$ such that it is out of reach of $x_i$ elements, then it would definitely give smaller answer than the minimal combination that we can form if we do not take elements outside of $x_i$. But I am not entirely sure about this claim.: Well I found a testcase which prove my claim false. Test case4 1 2 5 5 7 8 13 16 4 3 5 10 12 3 3 4 6 1 1 5 4 3 
•  » » » » 5 weeks ago, # ^ | ← Rev. 4 →   +1 My solution is similar to yours which was getting WA on test 13. Now I know why I was wrong.Please see the test data below—— 101000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements 1) ... 1 1 1 1 1 1 1 21000 ...(992 elements) ...993 994 995 996 997 998 999 1000We can then ban all combinations of the last element in the first nine lines and the last 5 (or any other element greater than 4) elements in the last line to hack your solution51000 1000 1000 1000 1000 1000 1000 1000 1000 10001000 1000 1000 1000 1000 1000 1000 1000 1000 9991000 1000 1000 1000 1000 1000 1000 1000 1000 9981000 1000 1000 1000 1000 1000 1000 1000 1000 9971000 1000 1000 1000 1000 1000 1000 1000 1000 996you will get Wrong Answer because you have to take the element —— 995 but you don't.I'm sorry. My English may be poor.
•  » » » » » 5 weeks ago, # ^ |   0 Thanks :)
 » 5 weeks ago, # |   +4 How to solve B?
•  » » 5 weeks ago, # ^ |   +25 Find minimal and maximal number of adjacent equal letters, everything is possible in between.
•  » » » 5 weeks ago, # ^ |   0 I saw almost everyone solved the problem as you've said. Is there any theory related to the problem? I want to study the topic in a bit more detail. Thanks in advance.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I guess the theory you are searching for is Greedy Algorithms and Math.That's because the concept behind "find min and max number of ..." is that we can always arrange the letters in a greedy way (you can consider how you might arrange (a, b, c) = (10, 2, 2) to get the max/min possible adjacent equal pairs)After figuring out the above, you may also realize that you don't need to simulate the process but rather can solve it by some Math properties.
•  » » » » » 5 weeks ago, # ^ |   0 Thank you so much !
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 WLOG assume a >= b >= c so the max possible same pairs will be in case like aaaabbbbccc => such pairs can be counted as ( a-1 ) + (b-1) + (c-1) = (a+b+c-3) so m<= a + b + c -3 and the min possible pairs will be in case like abacabac in such a case the possible same pairs can be counted as (a-b-c-1) so m >= a-b-c-1 so if m is in between this range we can always have an answer or else no answer
•  » » » 5 weeks ago, # ^ |   0 actually the min possible pairs should be abacabac... rather than abcabcabc...
•  » » » » 5 weeks ago, # ^ |   0 Thanks for the correction
•  » » » 5 weeks ago, # ^ |   0 How did we derive the min (a-b-c-1)??
•  » » » » 5 weeks ago, # ^ |   0 if u see the minimal case 'b' no of a's will be utilised 'c' no of a's will be utilised so we will be left with a-b-c number of a's so the no of pairs that can be formed is (a-b-c-1)
•  » » 5 weeks ago, # ^ |   0 Simulate the problem. Try taking only 1 number of a,b,c. Then check for which value of m we can get "YES"... Then try with 2,3,4 numbers of a and rest if them are 1 b and 1 c.... Now check for different values of m.Note: If we have 1 1 1 and m = 20.. Is it possible to achieve something like this? So we can conclude that there must be some range or largest value of m for which we can't find valid string. Now try to find out the maximum range ( upper value). Similarly we can say we must have some lower value of m for which we can get valid string. So the problem requires you to find the range. If m lies in the range then you should print "YES" otherwise "NO"
 » 5 weeks ago, # | ← Rev. 2 →   0 It was my first time when I soved a problem immediately after a contest finished. What a weird feel...
 » 5 weeks ago, # |   -9 terrific terrific terrific terrific terrific terrific terrific sample cases
 » 5 weeks ago, # |   +51 I can't believe I forgot how to do knapsack with items appearing arbitrarily many times and sum of weights a small number >_>At least I'll remember it now in the future, very educational round :)
•  » » 5 weeks ago, # ^ |   0 +1But you can still solve the problem by using FFT or polynomial inv if you haven't oberseved that
 » 5 weeks ago, # |   +5 How should I improve myself to solve problems like B?
•  » » 5 weeks ago, # ^ |   0 Solve B problems on a2oj ladders
•  » » 5 weeks ago, # ^ |   0 Just keep on practicing the questions of the rating that you are targeting from the problemset try doing at least 30 problems of that rating and also try to give every contest either live or virtually for getting the feel of solving problems in contest. Hope you will soon be able to solve B in contests :)).
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 i don't have a good solution but when I get stuck on problems like that I generally open paint and try to visualize the information that's provided, and that really helps me out. edit: practice of similar questions through ladders helps for sure
 » 5 weeks ago, # |   +5 Could someone explain the first sample of F? The way I'm interpreting the problem, the answer should be 0. Since any valid array a needs to have as many [occurrences of $A_1= [2, 1, 2]$] in it as [occurrences of any non-empty sub-array of $A_1$], in particular it seems that our array can't contain the number 2. Since $A_1$ itself has 1 occurrence of $A_1$ but two occurrences of [2], which is a nonempty sub array of $A_1$. And then we are banned from using the number 1 as well since it's contained in $A_1$ and we can't make $A_1$. And then similarly since $A_2=[1,3]$ we are banned from using the number 3 and it's impossible. What's the right way to read this?
•  » » 5 weeks ago, # ^ |   +16 First number is the size of an array.
 » 5 weeks ago, # |   0 I really liked the problem C (cool implementation of binary search + some key observations). However I did not like the difference in constraints of attack and defense upper limit ( the attack can be as high as 1e18 and defense up till 1e12).When I first read the problem , I read only the defense constraints (1e12). I reasoned that since was n was also only till 2*10^5 , the answer can never exceed 1e18. So I took 1e18 as INF. I submitted my solution with INF set as 1e18 only to receive a WA . I reread the problem , couldn't figure out a problem until I saw the constraint on attack. Quickly changing some code I submitted again and got AC.In hindsight I should have been more careful while reading the problem and there was no fault of the authors , however if possible from the next time this can be avoided.
 » 5 weeks ago, # |   0 Hi everyone, any pointers on how we can solve B? wasn't able to come up with any approach for it.
•  » » 5 weeks ago, # ^ |   +3 Think in the maximum amount of adjacents with the same letter and the minimum amount of adjacents with the same letter. Then check if m is in that range.
•  » » » 5 weeks ago, # ^ |   0 Hello , in B : 2 3 4 . So why max pair is 6 . I just see AABBBCCCC , and max pair is 4 Can you explain it for me ? Thank you so much
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 Of course, A-AB-B-BC-C-C-C. The - means each adjacent with the same value, so is 6
•  » » » » » 5 weeks ago, # ^ |   0 Ohhh, thanks man
•  » » 5 weeks ago, # ^ |   0 Find the minumum and maximum number of pairs you can make with given values of a,b,c and if m is lies between maximum and minimum then print YES otherwise NO.
 » 5 weeks ago, # |   +11 How to solve E?
 » 5 weeks ago, # | ← Rev. 2 →   +1 Can someone explain what does the following line mean in tourist's submission 129351289? I'm literally this line away from solving D :( if (v[i] < c[i] - 1) { break; } EDIT: seems this line is not very crucial, my original implementation was not fast enough.
 » 5 weeks ago, # | ← Rev. 2 →   0 Nice problemset, specially loved problem C but I think it was a little imbalanced. Personal opinion, there was a clear gap between problems C and D . If I were to set points for this set, I'd set: 500 - 750 - 1250 - 2000 - IDK - IDK 
•  » » 5 weeks ago, # ^ |   0 I think people messed up c ,which making a choice for minimum among lower bound and previous to it, other than that it was pretty straight-forward
•  » » » 5 weeks ago, # ^ |   0 Phoenix_021, exactly! I made the same mistake first time around, did not consider the value left to the lower bound. Cost me ~10 minutes to debug and correct, but it was fun.
•  » » » 5 weeks ago, # ^ |   0 Last line of problem C. I need to keep this in my mind. This silly mistake cost me very much I am going to kill myself.
 » 5 weeks ago, # |   +18 Write lots of weird stuffs on problem D and suddenly realized that I had just "invented" trie again.
 » 5 weeks ago, # |   0 Is there any easier approach for problem A than this one? I couldn't come up with idea immediately. codeint n; cin>>n; char open='(',close=')'; for(int i=0;i
•  » » 5 weeks ago, # ^ |   0 I took embarrassingly long too! I had it slightly differently. Here's howInstead of generating a sequence of i nested parentheses and then another sequence of n-i nested parentheses, I did first, a sequence of i nested parentheses and then i sequences of the string "()" haha.Yours is better. And, well, you must admit, this is a very simple few lines of code. It's just that problem A was probably not the usual stuff you'd expect and that's why it took so long to think of!
•  » » 5 weeks ago, # ^ |   0 You can use next_permutation function with the base string of all opening and then all closing brackets for example n=3 ((())).
 » 5 weeks ago, # |   0 i using cout_cin in contest = TLE 6 https://codeforces.com/contest/1574/submission/129409353 i using printf_scanf after contest = Ac https://codeforces.com/contest/1574/submission/129417724lol
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Just add ios_base::sync_with_stdio(0); cin.tie(0); at the beginning of the main function. This boosts iostream, but makes using both iostream and stdio dangerous, as the two are now desynchronised (as the name of the invoked method implies).
•  » » » 5 weeks ago, # ^ |   0 it's work thanks
 » 5 weeks ago, # |   0 C tests are bigger than 1e18? :|
•  » » 5 weeks ago, # ^ |   0 Yes.Otherwise it will be WA on 3.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 yes. think about strengths are all 1 and x and y are 10^12 and 10^18. so just make it x + y.
 » 5 weeks ago, # |   0 I used MAP , HASH , priority_queue and greedy in Problem D.But I haven't solved it. So I'd like to know whether Problem D has a high point of about 2000? I think it is much more difficult than Problem C.
 » 5 weeks ago, # |   +12 I want to kill myself . Missed AC on D by a stupid mistake $if(z >= ans)$ AC SolutionWrong Solution
•  » » 5 weeks ago, # ^ |   +3 This is the moment when we can start questioning about our existence.
•  » » 5 weeks ago, # ^ |   0 Just do it. — Nike
 » 5 weeks ago, # |   0 https://codeforces.com/contest/1574/submission/129407156 nice submission from alt to hack by yourself
 » 5 weeks ago, # |   0 https://codeforces.com/contest/1574/submission/129419462 Hey Guys, noobie here.I thought I solved c in (m+n)logn but getting TLE on test case 4. Kindly help
•  » » 5 weeks ago, # ^ |   0 Hi, so I have a question for the community as well, the answer to which influences your case.I see that the limits for a solution are the same regardless of the language in which the solution is written. Does that mean, that using Python (without extensive Python optimization knowledge) instead of a much faster (in common use) language like C++ can greatly influence scores on CodeForces?I am asking this, because this is exactly what happens on another competitive programming website on which I am a regular organiser (instead of participant) and thus, we don't allow Python there.
•  » » » 5 weeks ago, # ^ |   0 got AC after changing input :(
•  » » 5 weeks ago, # ^ |   0 Try adding this template: Spoilerfrom sys import stdin, stdout input = lambda: stdin.readline().rstrip() and use stdout.write(str(ans)+'\n') instead of print (important if you print more than 100000 times).But yeah this problem had a tight time limit for python. Had to switch from pypy to regular python 2 to get AC.
 » 5 weeks ago, # |   +4 nice last time solved B C and couldn't solve A , now i solved A C and couldn't solve B >:(
 » 5 weeks ago, # |   -6 does any one coded A using swap function!! codeint t;cin>>t; while(t--) { int n;cin>>n; string s (2*n,'0'); fo(i,0,2*n) { if(i%2==0) { s[i]='('; } else { s[i]=')'; } } cout<
 » 5 weeks ago, # |   0 Just replaced cin and cout in problem C with scanf and printf, and it worked. Just wish I had tried that earlier (>﹏<）
•  » » 5 weeks ago, # ^ |   0 If you want to keep using cin and cout add these two lines at the beginning of the main function: ios_base::sync_with_stdio(0); cin.tie(0); As far as I can remember these lines desynchronise iostream and stdio and perhaps do something more which makes using both input methods dangerous, but as long as you are using only cin and cout and these two lines, you shouldn't run into any time limit problems caused by input/output.
•  » » » 5 weeks ago, # ^ |   0 thank you.. ill look into this
 » 5 weeks ago, # |   +4 The fact that the last round had an unexpected (unknown) error, and this round just after 2 days went flawless is one of the reasons I love cf. Great work.
•  » » 5 weeks ago, # ^ |   +6 The Pretest runs for the first 2 problems actually seemed smoother than usual, with almost instantaneous results.
 » 5 weeks ago, # |   0 I think it should be a hint in problem c to use fast input output but it was a good contest many thanks for problem setters for clear requirements!
 » 5 weeks ago, # | ← Rev. 2 →   0 B. Combinatorics HomeworkInput:11 1 3 2Judge output: YESI think the output should be: NOBecause you can't make 2 pairs in the context.[abccc] How can you make 2 pairs? Can you please specify your string that satisfies?A brief explaination would be appreciated. Thank you. if(you think comment should be downvoted) continue; //keep thinking but don't downvote :-) 
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 'ccc' is 2 'cc' pairs, they just share the middle 'c'edit: 'adjacent' was probably technically incorrect...
•  » » » 5 weeks ago, # ^ |   0 Yes bro.exactly m such postitions i that the i-th letter is equal to the (i+1)-th one.I could have put more attention to this line. I think CP isn't for me and i should leave now. :-(
•  » » » » 5 weeks ago, # ^ |   +5 For what it's worth, this contest was still meant for div2 despite whatever connotations 'edu' might entail. I wouldn't sweat some brick-y outcomes.As for quitting, I'm a fan of people doing things they find intrinsically rewarding rather than pushing themselves due to extrinsic reasons or ego. There are also other cp sites besides codeforces if you want to try atcoder ABC's for instance. Either way, I can only hope you find what works for you.
•  » » 5 weeks ago, # ^ |   0 in the string abccc the chars at pos 3 and 4 make a pair and the chars at 4 and 5 make a pair
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Thank you... I am a noob.
 » 5 weeks ago, # |   +5 When io issues aren't just affecting python users...
 » 5 weeks ago, # |   0 I don't know why my program with same time complexity as others which passed don't work. Can anybody please explain why this is happening. This is the link to the code.
•  » » 5 weeks ago, # ^ |   +5 Your getmin function takes a vector a directly, so it makes a copy (which takes $O(n)$) each time you use it, if you change it to take the vector by reference (just adding an &a) you'll get AC.Here is the corrected code 129426111.
•  » » » 5 weeks ago, # ^ |   0 Thank You very much. It was really helpful.
 » 5 weeks ago, # |   0 Why did this did not worked for C? https://codeforces.com/contest/1574/submission/129409251 I have seen few submissions which follow the same approach and they got passed. Can anyone plz help?
•  » » 5 weeks ago, # ^ |   +8 If you use cin/cout for input/output, ios_base::sync_with_stdio(false); cin.tie(0) should be your best friend.Here you are 129426352.
 » 5 weeks ago, # |   0 Can someone hack my C 129392269
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anybody tell me why my solution to D is failing?I iterate over all the sums I can get with those numbers, but in order from maximum to minimum. As soon as I have a solution which is not 'banned' I print it out. I guess it should work.In priority queue I keep two values (sum, chosen items).EDIT: I had a little bug but now after fixing got TLE. But why? I think I should find the solution in $m$ operations.Solution
•  » » 5 weeks ago, # ^ |   0 You are adding repeated states to the PQ. If a build is already in the queue you can skip it.
•  » » » 5 weeks ago, # ^ |   0 Yep, fixed it, silly mistake :(. Thank you by the way.
•  » » » » 5 weeks ago, # ^ |   0 Nice, btw you can only store the build (in the set of visited), the sum is not necessary since it can be deduced from the build
•  » » » » » 5 weeks ago, # ^ |   0 So you mean to change the pq comparator?
•  » » » » » » 5 weeks ago, # ^ |   0 That would indeed force you to change the comparator and I think it wouldn't be worth it because:You'd have to recompute the sum of the values every time you need it, which increases the time complexity constant, which isn't good, andYou'd lose time on writing a custom comparator which is not exactly the easiest thing to do and can easily go south, so unless you've already done similar stuff, it's risky, and even if you've got experience with that, it's still a waste of time during the round.The only "pro" of this approach would be to save some memory, which is negligible. Much more so than the time you would otherwise save.
•  » » » » » » 5 weeks ago, # ^ |   0 No, I mean that the set you added can be only of vector. Instead of pair> :)
•  » » » » » » » 5 weeks ago, # ^ |   0 Oh, got it. But I feel like my approach is better. Even if we are in CP, I think that vector or any kind of collection should hold the values from the same context.
•  » » » » » » » 5 weeks ago, # ^ |   0 This would then require a custom comparator, though. Unless you do another funky thing and let the strength be the first (zeroth?) element of the vector.
 » 5 weeks ago, # | ← Rev. 2 →   0 Can Anyone help me find error in my code i'm getting wrong output format Unexpected end of file — int32 expected in Test 6.My approach is: I'm starting with the vector having the highest build(i.e, all the last elements of all rows say top layer) in the priority queue then for each top element of the priority_queue I'm pushing all the new vectors with a new element in one of the rows that can be formed from the next lower layer with the build value of the vector at the beginning of vector.I'm pushing popping until i get a vector which is not in the our set of bad vectors.(soory for bad explaination >_<) Code#include // Common file #include #include // for less #include #define ll long long int #define ull unsigned long long #define pb push_back #define PI 3.141592653 #define pll pair #define V vector #define F first #define S second #define INF LLONG_MAX using namespace __gnu_pbds; using namespace std; typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; ll lcm(ll a, ll b){ return (a / __gcd(a, b)) * b;} void solve(){ ll n; cin >> n; V> v(n); V vec(n+1); for(int i = 0; i < n; i++){ ll m; cin >> m; v[i].resize(m); for(int j = 0; j < m; j++) cin >> v[i][j]; vec[i+1] = m-1; vec[0] += v[i][m-1]; } ll m; cin >> m; set> ban; for(int i = 0; i < m; i++){ V vv(n+1); for(int j = 1; j <= n; j++){ cin >> vv[j]; vv[j]--; vv[0] += v[j-1][vv[j]]; } ban.insert(vv); } priority_queue> q; q.push(vec); while(q.size() <= 2e6){ auto a = q.top(); q.pop(); if(ban.find(a) != ban.end()){ for(int i = 1; i <= n; i++){ V vv(a); if(a[i] == 0) continue; vv[i]--; vv[0] += (v[i-1][vv[i]]-v[i-1][a[i]]); q.push(vv); } } else{ for(int i = 1; i <= n; i++) cout << a[i]+1 << " "; cout << endl; return; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T = 1; //cin >> T; for(int i = 1; i <= T; i++){ //cout << "Case #" << i << ": "; solve(); } return 0; } UPD: I was storing some same vectors multiple times. Accepted Code.
 » 5 weeks ago, # |   0 Problem C has taught me that qsort TLEs and std::sort doesn't
•  » » 5 weeks ago, # ^ |   +9 Yes, because the Quicksort algorithm, while having "quick" in its name is not that quick after all.Firstly, its O(n log(n)) complexity is just the average case, although admittedly by randomizing the pivot, the only thing stopping your case from being "average" is EXTREME bad luck, so this is negligible. But...Secondly, std::sort is a wicked hybrid algorithm optimized for all kinds of stuff and well... it's faster.
 » 5 weeks ago, # |   +40 Seems like tests for problem F were super weak, I hacked many reds without even knowing the question Spoiler
•  » » 5 weeks ago, # ^ |   0 how can you prepare test cases without knowing the question???p.s. i have never hacked so no idea
•  » » » 5 weeks ago, # ^ |   +8 Knowing constraints is enough info
 » 5 weeks ago, # |   +9 My solution to problem D using trie data structure. First of all construct a trie of the banned combinations. Now we will be iterating over each banned prefix(using a dfs on the trie) and take the remaining values the maximum possible. Here is my submission. Hope it helps someone. Submission:- https://codeforces.com/contest/1574/submission/129429122
•  » » 5 weeks ago, # ^ |   +3 "and take the remaining values the maximum possible"could you please explain this?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Basically ,what I am trying to do is that go to every prefix which is banned. Now let's assume till index x-1 you have taken the banned prefix. Now, for the index x, you will choose the largest possible value which can be taken for that particular index, such that that the prefix upto index x is not banned. Once you have taken that, for the remaining indices, from x+1 to n,you can just take the maximum value among all possible values for each of the indices (x+1 to n).
•  » » » » 5 weeks ago, # ^ |   0 Nice idea, thanks!
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Based on how you explained it here, I think I have the same! Pretty interesting to think of it as a trie. Then again, I only "know" trie in theory and never consciously used it.
•  » » 5 weeks ago, # ^ |   +3 Can you please explain your dfs function?
•  » » » 5 weeks ago, # ^ |   0 In the dfs function, what I am doing is that I am going to each node of the trie. Now, this node represents a banned prefix. Now for this banned prefix I will choose the maximum value for the next index such that the sequence doesn't become banned(in my code it is done using the x variable inside dfs function). For the remaining indices ,I am just taking the maximum (stored in the suff vector).The now vector stores the current prefix(banned obviously). Hope it helps.
•  » » » » 5 weeks ago, # ^ |   0 Thanks.
•  » » 5 weeks ago, # ^ |   0 Almost the same approach but used hashing in place of trie ( as I dont like pointer much ). MY_SOLUTION
 » 5 weeks ago, # |   +13 I think my solution for problem D is kind of different. I passed pre-tests by using the pigeonhole principle， brute force and a trick.At first, I got a wrong observation: if $\prod_{i=1}^n x_i > m$, then we can only consider the top $x_i$ equipments for the $i$-th slot, because according greedy and the pigeonhole principle, the answer must be already considered. And $\max_{i = 1}^n x_i$ can be calculated easily by using binary search. Now, we can enumerate all possible builds and get the "answer".After getting WA on test 13 for a lot of times, I find out a case that the observation did not work. For example: 3 6 1 2 3 4 5 6 6 1 2 3 4 5 100 6 1 2 3 4 5 100 3 4 6 6 5 6 6 6 6 6 And I think out a trick: for a banned build $b$, for the $i$-th slot, replace the $b_i$ with $b_{i} - 1$, and then take $b$ in to consider. The trick appear to cover cases that the observation did not work, and I do pass all pre-tests.(Hope that I will not get FST
 » 5 weeks ago, # |   0 129449581 got accepted But 129414197 didn'tThere is difference in only one line of program.When i used (long long) 9e18, it passed. But when i used LONG_MAX i failed. Can anyone say me what happened? Thanks in advance!
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 long max is actually the maximum integer that can be represent in type int which is 2147483647. This number is clearly not large enough for your solution.
•  » » » 5 weeks ago, # ^ |   0 Yeah! Thanks man!in codeforces LONG_MAX is 2147483647 LONG_LONG_MAX is 9223372036854775807
 » 5 weeks ago, # |   0 Yayy I finally have a chance to become a pupil, also I want to ask if it's normal for someone to reach pupil after 18 contests?
 » 5 weeks ago, # |   -14 Where is the official editorial...
•  » » 5 weeks ago, # ^ |   0 hi
 » 5 weeks ago, # |   0 How to solve D?
•  » » 5 weeks ago, # ^ | ← Rev. 5 →   +6 You can use a max priority queue ordered by build strength to generate the most powerful builds in decreasing order.First push the max build on the queue, then loop. On each iteration, pop from the queue, check if the build is banned (with a map of banned builds). If it isn't output and stop. Else generate new builds by decrementing at each index of the popped build (so at most n<=10 new builds are generated) and push these builds on the queue ordered by their strength (if they haven't been pushed already — can be checked with a map of seen builds). Since the all the popped build are different at most m+1 builds are popped and at most m*n builds are pushed which is fast enough.
•  » » » 5 weeks ago, # ^ |   0 Dijkstra vibes.
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anyone please help me with a test case where my solution for B is failing? My solution: 129451176 My approach seems almost the same as mentioned in other comments but still it fails.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 For test case: 1 4 4 3Your code outputs "NO" while the correct output is "YES"
•  » » » 5 weeks ago, # ^ |   0 Thanks! I also got WA on this test case, couldn't figure this case myself though.
 » 5 weeks ago, # |   0 nice problems, I love problem D.
 » 5 weeks ago, # | ← Rev. 3 →   0 I got the min-max range logic for B.But I can't figure out what is wrong with my first approach. Can some help me debug it? Spoiler: Codeif (a > 1 && m>0) { int pair = (a-1); // Maxm possible pair by a // Leftout a if (pair > m) a = a-(m+1)+1; // +1 at last because we are considering AAAAAA..(group of A generated) as 1 else a = 1; m = (pair > m? 0: m-pair); // Leftout m, which cannot be fulfilled by a } if (b > 1 && m>0) { int pair = (b-1); if (pair > m) b = b-(m+1)+1; else b = 1; m = (pair > m? 0: m-pair); } if (c > 1 && m>0) { int pair = (c-1); if (pair > m) c = c-(m+1)+1; else c = 1; m = (pair > m? 0: m-pair); } int[] arr = {a,b,c}; Arrays.sort(arr); if (m > 0) { System.out.println("NO"); }else if (arr[2]-arr[1]-arr[0]-1 > 0) { // Minimum pairs possible from leftout a,b,c > 0 System.out.println("NO"); }else { System.out.println("YES"); }
•  » » 5 weeks ago, # ^ |   0 Getting WA on testcase 2, 80th. Can't see the actual case: a,b,c,m values though.
•  » » 5 weeks ago, # ^ |   0 Try to put your code in a spoiler tag. It's less rude that way.
•  » » » 5 weeks ago, # ^ |   +4 Got it, Done.
•  » » 5 weeks ago, # ^ |   0 For this input your solution outputs NO, should be YES 1 2 2 5 1 
•  » » » 5 weeks ago, # ^ |   0 Yeah, I see thanks! The max-min range is the best way to go for this one.
 » 5 weeks ago, # |   0 I wasted 4 submissions because of using int in problem C :(
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -21 .
•  » » » 5 weeks ago, # ^ |   0 That's not a good idea sometimes the time limit won't be enough with long long
•  » » » » 5 weeks ago, # ^ |   0 Oh! Sorry I didn't knew about it. Thanks for correcting!
•  » » » » 5 weeks ago, # ^ |   +3 Does CodeForces compile into 32-bit executables? I'm asking because long longs are slower only in that case. Another competitive programming site changed compilation to 64-bit and now there is no difference besides memory use.But additional memory use is not something completely unimportant. Usually it doesn't matter, but problems can easily be made to require better memory use. I've seen a problem (not on CodeForces) which actually required the use of short ints!Also, having templates with a couple of useful things like #define st first may be good (I personally don't use that), having multiple dozen lines of code (more than fits on a screen) as a template is most definitely a bad practice, especially at the lower levels. And it's not like templates help much besides obfuscating your code to protect against potential hacks. You can take a look at the submissions of some of the top people on CodeForces and all of the ones I've seen fit on one screen. Some of them are even a very modest couple of lines. And they most definitely don't have bullshit like #define int long long.
 » 5 weeks ago, # |   0 can anyone help me why am i getting tle in D?129459481
•  » » 5 weeks ago, # ^ |   +1 You need to add some sort of "visited" logic to the queue. Otherwise you will end up trying out the same configuration multiple times.I modified your solution using a set of vector of ints to implement the visited logic- you can see the modified solution here: https://codeforces.com/contest/1574/submission/129462075
•  » » » 5 weeks ago, # ^ |   0 thank you so much
 » 5 weeks ago, # |   0 It says that this contest will be rated for div 2 participants but my rating hasn't changed after the contest. My rating previously was 1099 and still is the same. Can anyone please tell me why is it so?
•  » » 5 weeks ago, # ^ |   0 same issue
•  » » 5 weeks ago, # ^ |   +1 See after the contest there was hacking phase. After that within 2-3 hrs you can see the changes.According to indian time I would say by 3PM
•  » » » 5 weeks ago, # ^ |   0 Oh I see. I didn't know that. Thanks a lot.
•  » » 5 weeks ago, # ^ |   0 Have a testing time after hacking. Please wait.
 » 5 weeks ago, # |   +7 Why isn't the system testing started yet? It's been 3hr since the hacking phase ended.
•  » » 5 weeks ago, # ^ |   0 The system tests were ran from the very beginning. Notice, how submission status was never "Pretests Passed (3)" or something like that, but straight up "Accepted". I was surprised when I saw that!
•  » » » 5 weeks ago, # ^ |   +6 Oh, sori sori, I actually meant when will they run all the hacks over the submissions? It had been too late now :/
•  » » 5 weeks ago, # ^ |   0 Still, don't start yet.
 » 5 weeks ago, # |   -39 I think D is not difficult for someone who know how to use heap,maybe it only can get 1300.
 » 5 weeks ago, # |   0 My rating is not increased yet, why??
•  » » 5 weeks ago, # ^ |   +8 Great things come out of patience.
 » 5 weeks ago, # |   0 Have the ratings been published?
•  » » 5 weeks ago, # ^ |   0 not yet
•  » » » 5 weeks ago, # ^ |   0 I wonder why it shows me the game is unrated.
 » 5 weeks ago, # |   +51 Since every contest ends up with questions like "when my rating changes" it would be great if stage "System Tests" will be followed by stage "Rating calculation". It would calm down a lot of people.
•  » » 5 weeks ago, # ^ |   0 then there will be questions about why rating is being calculated so slow
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 Adding percentage of progress (like in system tests) could partially solve this issue too.
•  » » » » 5 weeks ago, # ^ |   +1 I guess rating changes applying is manual work, automatic calculations should be pretty fast. But I might be wrong. Correct me if someone is more familiar with system
•  » » » » » 5 weeks ago, # ^ |   0 I do not beleive in manual rating calculation for 20k members. No way.
•  » » » » » » 5 weeks ago, # ^ |   0 Yeah, that will be automatic. Any idea by when can we expect the rating changes?
•  » » » » » » 5 weeks ago, # ^ |   0 I meant only applying changes is manual, calculation is for sure automatic
 » 5 weeks ago, # |   0 Question D made me very sad. In the process of the competition, in order to avoid the single hash being hacked, I used double hash, which passed normally during the competition and took 1.6s. However, the retest after the competition was timed out due to the new data, but I passed all the samples after changing to single hash. (In the single hash case, obviously, it's easy to create a special sample hack when you know the hash value.) TLE-CODE:129383238 AC-CODE:129474392
•  » » 5 weeks ago, # ^ |   +5 So you used some form of hashing and then stored whatever data you needed on a set either way? At that point I'd use std::unordered_set...That being said I used a set> (because std::vector by default compares itself lexicographically) and didn't have any problems with time limits.
•  » » » 5 weeks ago, # ^ |   +3 "unorder_set" is really much faster, and I've never used "set" before, thanks for your advice, it's all new to me!
•  » » » » 5 weeks ago, # ^ |   -10 Yes, std::unordered_set and std::unordered_map are two STL containers one should always keep in mind when dealing with algorithmics. They use hashing to provide constant time access! However, in a very pessimistic scenario one could potentially encounter data which has a lot of collisions and then the access would have linear complexity. But understandably -- that simply doesn't happen.One another note, std::vector does not have a built-in hashing function, so it's not compatible with the two aforementioned containers straight off the bat. That is why, during the round, I wondered if vectors are compatible with regular sets and that would be if their operator< was built-in. Just like you, I didn't know, but I opened cppreference.com and looked it up.Another bit of advice: your way of hashing (don't worry, it's pretty much the only popular way of hashing) by taking elements and multiplying them by a constant and then taking the remainder modulo another constant is rather slow, because the modulo operation is slow. So I wouldn't be surprised if using hashing is still slower than using the logarithmic std::set` structure. In fact, looking at your newest submission, that is the case, since it still performs around 3 times slower than mine.Better luck with all this new knowledge next round!
 » 5 weeks ago, # | ← Rev. 2 →   +3 awoo at least provide us, editorial.
 » 5 weeks ago, # |   +3 Editorial much-awaited!!!!
 » 5 weeks ago, # |   +1 I am new here, How much time taken by codeforces to update rating ?
•  » » 5 weeks ago, # ^ |   0 It's taking a lot of time today usually 2 3 hrs at max
 » 5 weeks ago, # |   0 when will we get the editorial of the problems?
•  » » 5 weeks ago, # ^ |   0 SoonTM
 » 5 weeks ago, # | ← Rev. 2 →   +7 Eagerly waiting for editorial and updated rating !!
•  » » 5 weeks ago, # ^ |   +1 Someone please shoot me, I can't wait anymore.
•  » » » 5 weeks ago, # ^ |   0 2 !!! Ouf.. wait for the next contest
 » 5 weeks ago, # |   +1 when is editorial published?
 » 5 weeks ago, # |   0 Is this contest was rated for div 2 participent.
 » 5 weeks ago, # |   0 Because Till now there is no update in ratings.
 » 5 weeks ago, # |   0 Are there any chances of publishing the editorial?
•  » » 5 weeks ago, # ^ |   +8
 » 5 weeks ago, # |   +21 me waiting for rating change and editorial
 » 5 weeks ago, # |   0 for the B problems we check whether the given m ranges between minimum possible pairs and maximun possible pairs , but i dont get the intution behind it , can anyone explain it to me , and also does this approach work with similar kind of problems ?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 For me B was similar to A, it is slight variation of that here we can have let mx be the max amount of equal adjacent pairs now we can change the orderging to decrease the no of such pairs by 1 to mx-1 and so on... , similarly going till certain value after which you cannot decrease that value of mx , which will act as your minimum value. Yes it works with similar kind of problems .
•  » » » 5 weeks ago, # ^ |   0 thanks , got it
 » 5 weeks ago, # |   +6 awoo: please post editorials. For rating changes take your time. but please atleast post editorial....
 » 5 weeks ago, # |   0 Dont understand why editorials are so slow. -1
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   -18 why editorials are so slowBz it takes efforts ans time which you must have not ever gone through,orz awoo for such beautiful problems
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 Lol there have been editorials published in a few hours after the contest.orz awoo for such beautiful problems how about u solve them first before writing genric nonesense in the comment to get contribution or whatever
•  » » » 5 weeks ago, # ^ |   0 Yes, editorials take a lot of time to create, but I think they should be created before the contest is released.
 » 5 weeks ago, # |   +3 I got +0 delta :")
 » 5 weeks ago, # |   0 For C, I understand that we would have to check for the lowerbound and lowerbound-1 as candidates for beating a defense of x, but why stop there? why not check lowerbound-2? or lowerbound-3? I get that they increase the cost with attacking against the dragon, but they do the job of reducing the cost while defending against an attack of y right? without this I'm not able to prove the greedy approach. any help will be appreciated ! Thanks!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 So assume we have $n$ knights with strengths $a_1 \leqslant a_2 \leqslant \cdots \leqslant a_n$. Now assume that the dragon has defense $x$ and attack $y$, and let's say that $i$ is such, that $a_i$ is the smallest of the strengths greater or equal to $x$. Now I will show why we only need to check $a_i$ and $a_{i-1}$ (if they exist).First, we do not have to check any $a_j$ for $j>i$ because using greater attack than necessary will not give us any advantage, but may cost us defense points, and thus gold. I think this is fairly straight forward.Second, we do not have to check any $a_j$ for \$j
•  » » » 5 weeks ago, # ^ |   0 Thanks for this, and after I pondered upon the problem I was able to prove that for i
 » 5 weeks ago, # |   +3 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).