By awoo, history, 13 months ago, translation,

Hello Codeforces!

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

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

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

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

Good luck to all the participants!

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

Calling on all Codeforces,

Harbour.Space University is offering a unique opportunity to study in Barcelona for those who are interested in joining our young and dynamic competitive programming team. We accept medalists and top performers of IOI, IMO, ICPC, and participants with Codeforces rank above 2000.

Harbour.Space has a single, key requirement: be passionate and motivated to learn and/or work in the field of competitive programming in the long term. Even if you have already exhausted all your ICPC attempts, you are still welcome.

Join us to help build a comprehensive system of preparation for IOI and ICPC for the next generations! We believe that if you have the talent and determination to succeed, you can. We want to help you make it happen.

In addition to courses taught by some of the world's foremost experts in their fields, Harbour.Space offers these benefits upon acceptance for this scholarship:

• A full tuition fee waiver (Bachelor and Master degrees)
• Student visa
• Private health insurance
• Monthly living allowance*

In return, we demand dedication to learning and improving yourselves:

Study three hours per day
Train continuously for ICPC, if you are still eligible for participation
Intern four hours per day

Ready to formally submit your application? Please register on our website, attach your latest CV, and pay a non-refundable €125 application fee. The fee guarantees we can process every single application in a fair and timely manner, and maintain the highest possible standards of assessment.

Register→

Our admission process is a holistic review of each candidate's abilities, achievements, and potential to create something exceptional.

You may choose to study in the following areas of specialization:

1. Computer Science
2. Data Science
3. Cyber Security
4. Front-End Development

*The exact living allowance level throughout the entire duration of studies depends on the performance during the interview and on the overall performance. As a guidance, it is in the range of 500-1500 EUR.

Harbour.Space University Team

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 risujiroh 7 233
2 Maksim1744 7 243
3 noimi 7 253
4 fastmath 7 278
5 mango_lassi 7 288

145 successful hacks and 1221 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Maksim1744 0:01
B SSRS_ 0:03
C BrunoFMUFC 0:06
D SSRS_ 0:10
E AmShZ 0:08
F SSRS_ 0:51
G Potassium 0:45

UPD: Editorial is out

• +223

 » 13 months ago, # |   +8 In return, we demand dedication to learning and improving yourselves:— Study three hours per day— Train continuously for ICPC, if you are still eligible for participation— Intern four hours per day Is this a hard and fast rule or can be slack. As the above three activites consumes around 10 hours of day. Where is life?
•  » » 13 months ago, # ^ |   +35 You guys getting lives?
•  » » » 13 months ago, # ^ |   0 GooD One
•  » » 13 months ago, # ^ | ← Rev. 2 →   -43 .
•  » » 13 months ago, # ^ |   0 what about online classes?
•  » » » 13 months ago, # ^ |   0 what about non cs engineers lol
 » 13 months ago, # |   -10 Three contest in a row in consecutive days. This is really awesome! That's why codeforces is best.
•  » » 13 months ago, # ^ |   +3 So you're going to say the opposite thing when there is no contest in 3 consecutive days?
•  » » » 13 months ago, # ^ |   +32 No, not at all. I am just talking about frequency as compared to other sites.
•  » » 13 months ago, # ^ |   -17 @kisser :/
•  » » 13 months ago, # ^ | ← Rev. 2 →   -18 Actually, while this is generous of CodeForces, I think it would be ideal if contests were spread out a little more evenly. I had prior commitments for the weekend and Monday and will miss 3 contests (that would typically be spread over 2-3 weeks instead of 3 days).
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +1 So you're saying that there should be less contests so you compete in more contests? I don't get your point.5 contests over 2 weeks is worse than 3 contests over 3 weeks?
•  » » » » 13 months ago, # ^ |   +14 Nope, that's not what I'm saying. Rather than have 3 back-to-back contests over a single weekend, and then wait for 10+ days for the next one, it may be better to spread them a little (say over a week) so people who are occupied (over a weekend in this case) don't miss all 3 and have a chance to attend at least 1-2 of them.
•  » » » » » 13 months ago, # ^ |   0 Yeah ok but the next contests is in 3 days (a 5-day gap, not 10+) and the one after that is in 2 more days.
•  » » » » » » 13 months ago, # ^ |   0 It's great that there's some more right around the corner. My suggestion was not to reduce the frequency or number of contests (the more the merrier), but to distribute them in an optimal way.
 » 13 months ago, # |   +54 Codeforces rank above 2000. I think you mean rating, not rank
 » 13 months ago, # |   -6 Do you do dynamic programming in the dynamic competitive programming team?
 » 13 months ago, # |   +8 hope I remain expert after the contest :(
•  » » 13 months ago, # ^ |   +8 same here
•  » » » 13 months ago, # ^ |   +5 i am on the edge
•  » » » » 13 months ago, # ^ |   0 yup me to just a little above
•  » » » 13 months ago, # ^ |   0 he succeeded but we failed brother :'(
•  » » » » 13 months ago, # ^ |   0 next time man it feels bad
•  » » 13 months ago, # ^ |   +21 You are giving the contest that's the best thing.
 » 13 months ago, # |   +3 A humble request, just try to recheck the problem statement before uploading the question, for example, the last line of the first problem ( which was rectified later ) was incorrect and made the whole problem statement wrong. I was planning to give the contest but was confused reading the last line and by the time it was rectified over 6000 people had already solved it.
•  » » 13 months ago, # ^ |   +23 Yes, it was a typo in the notes, but it was fixed just about 5 minutes into the contest. We are sorry for that issue, but sometimes typos happen, and we almost always fix them quickly.
 » 13 months ago, # |   +2 Any idea how to fix WA on test-10 for problem D?
 » 13 months ago, # |   +4 How to solve D ?
•  » » 13 months ago, # ^ |   +31 Eulerean tour of the letters
•  » » 13 months ago, # ^ |   +43 a + ab + ac + ad .. + az + b + bc + bd + be + ...
•  » » » 13 months ago, # ^ |   +26 I feel so stupid now
•  » » » » 13 months ago, # ^ |   +5 same
•  » » » » » 13 months ago, # ^ |   +2 same
•  » » » » 13 months ago, # ^ |   0 same
•  » » » » » 13 months ago, # ^ |   0 same
•  » » » » » » 13 months ago, # ^ |   0 sam
•  » » » » 13 months ago, # ^ |   +7 About 5000 people feel the same way.
•  » » » 13 months ago, # ^ |   +2 It was harder for me lol cuz i did the same thing in a weird way...aa + ba + ca + da ... + z + bb + cb + db + ... + z + cc + dc...
•  » » » » 13 months ago, # ^ |   0 I done this way only check my submission
•  » » » » 13 months ago, # ^ |   0 same !
•  » » » » 13 months ago, # ^ |   0 One more possible sequence. ab + bc + cd + da (difference=1) + ac + bd + ca + db (2) + .. + (diff=k)
•  » » » 13 months ago, # ^ |   -8 what to after "zz" but string size still less than n ?
•  » » » » 13 months ago, # ^ |   +4 The series will again start from "a" as it cannot be done better than this.
•  » » 13 months ago, # ^ |   0 if k = 7, we can concan strings below aabacadaeafag bbcbdbebfbg ccdcecfcg ddedfdg eefeg ffg g and then append strings repeat.
•  » » 13 months ago, # ^ |   +9 you want to minimize occurrence of each distinct pair of letters (adjacent letters) that appears in the string , add an edge between each pair of usable letters .Then our answer is minimized if we take euler cycle of this graph ,euler cycle always exists since its a directed complete graph, each letter has equal indegree and outdegree.
•  » » 13 months ago, # ^ |   +15 I did brute force over all pairs ,$"aa","ab","ac"\cdots\ "zz"$ and greedily selected the best pair with minimum occurence.Compleixty; $O(n*26)$https://codeforces.com/contest/1511/submission/112864604
•  » » » 13 months ago, # ^ |   -6 ya, that's what I thought of. But couldn't get to the solution.
•  » » » 13 months ago, # ^ |   0 I did the same but the only difference in mine solution was if(cnt[ans[i-1]-'a'][p]<=mi) this line. I used this if(cnt[ans[i-1]-'a'][p]
•  » » » 13 months ago, # ^ |   0 I did the same thing but for some reason i was convinced that placing the first k characters first like (abc...k) is optimal submession
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Problem D: There can be $k*k$ possible pairs of characters. Now consider each of these pairs as a vertex of a graph. Then add a directed edge from $c_1c_2$ to $c_2c_3$ for all possible $c_1$, $c_2$ and $c_3$. Now do topological sorting to find a sequence of pairs. This sequence has each of the pairs exactly once, so the cost is $0$. So, you get the maximum lengthed string which has $0$ cost ($c_1c_2 \rightarrow c_2c_3$ will become $c_1c_2c_3$). Now just keep concatanating this string until its size becomes n.
•  » » 13 months ago, # ^ |   0 Pay attention to the Example 1's output.
 » 13 months ago, # | ← Rev. 2 →   +14 Solved problem G in $O(nq)$ with auto-vectorization. My worst test works in 4305 ms. Solution 112850106. Hope that it will stay strong during next 12 hours and later.
 » 13 months ago, # |   0 Can someone suggest approach for B and D?
•  » » 13 months ago, # ^ |   0 for B:take the gcd as pow(10,c-1)
•  » » 13 months ago, # ^ | ← Rev. 2 →   +2 I have not given the contest. But just saw B. I think you can have many possible answers . One possible answer can be like this : X = 100...000(a-1 zeroes) Y = 77...7000...00( (b-c+1) 7s & c-1 zeroes).This will always give you gcd as 10..00(c-1 zeroes)
•  » » » 13 months ago, # ^ |   0 Oh. This is very nice. I just went into unnecessary complications. Thanks, bro!!
•  » » » 13 months ago, # ^ |   -6 You can't do that. X and Y can't have leading zeroes.
•  » » 13 months ago, # ^ | ← Rev. 3 →   +1 For B, I decided to assign a unique prime factor to each of a (2), b (3) and c (7). As all the numbers (2, 3, 4) are lesser than 10, there will always be a power of {2, 3 and 7} whose decimal representation is of any given number of decimal digits. First of all, I find c by multiplying it with 7 till I get the required number of digits. Then, I multiply both a and b by c so that their GCD becomes c. Finally, I multiply a and b with their respective prime factors till their representations reach the required number of digits. Eg: 2, 2, 1 Output: 14 (2 * 7), 21 (3 * 7), 7 My Submission
•  » » 13 months ago, # ^ |   0 For B: I set both my answers equal to 10^(c-1). I multiplied the first answer by 2 until it was the right number of digits. I multiplied the second answer by 3 until it was the right number of digits. That way I would always get the right number of digits for a, b, and c.112795076For D: You want every pair of the first k lowercase characters to show up a minimal number of times. The best way to do this is rotate through like this for k = 4: aa, ba, ca, d + bb, cb, bd + cc, cd and then rotate through again if you have not exhausted all of n.112826898
 » 13 months ago, # |   +16 how to solve E?
•  » » 13 months ago, # ^ |   +33 OEIS
•  » » » 13 months ago, # ^ |   -10 can u plz tell what is OEIS?? i have heard it a lot(at cf itself) in pattern related questions.
•  » » » 13 months ago, # ^ |   +4 Which sequence? How did you get there? I think I'm just really bad at looking on OEIS.
•  » » » » 13 months ago, # ^ |   0 What is OEIS?
•  » » » » » 13 months ago, # ^ |   0
•  » » » » 13 months ago, # ^ |   +19 I generated the results for 1D patterns like "o", "oo", "ooo" and so on, got an oeis sequence with these numbers, then for each vertical / horizontal contiguous pattern, I added "formula(lengthContiguous)*2^(nbWhites-lengthContiguous)"Formula was weird, couldnt understand (I suck at combinatorics), something like "((3*n+1)*2^n-(-1)^n))/9"
•  » » » 13 months ago, # ^ |   0 logic.?
•  » » » 13 months ago, # ^ | ← Rev. 3 →   +25 Whenever there is a combinatorics problem in one dimension, it is often the case it's formula or some related information will be available on OEIS. So find the answer for small terms and search these terms in oeis.org and you will get the formula for it. To solve E ,Step 1 : Try to reduce a problem to find the answer for only 1 row having N white color cells.Step 2 : Write bruteforce and search OEIS.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +3 Actually we can do it without OEIS using contribution technique,but yea for that too we need to come up with the observation on small single rows.... If l is the length of row,c is total white places,so the answer is sum of2^(c-2)+2^(c-2)........l-1 times...-2^(c-3)-2^(c-3)........l-2 times...2^(c-4)+2^(c-4)........l-3 times... .........till this converges.
•  » » » » 13 months ago, # ^ | ← Rev. 3 →   +36 Step 2 (alternative) by Combinatorics: Problem E 1511E - Colorings and Dominoes Let's denote the answer for N contiguous white color cells by f(n) and try to compute for f(n+1). If (n+1)th character is 'b' then we simply have 'value' as f(n). If (n+1)th character is 'w' then: If nth character is 'b' (.......bw) Then we have f(n-1) If nth character is 'w' (.......ww) Then we can put a domino on these ww. The number of such cases is 2^(n-1). Also, we need to add f(n-1) for the 'value' of the n-1 elements. so f(n+1) = f(n) + f(n-1) + 2^(n-1) + f(n-1) Solution: 112869725
•  » » » » » 13 months ago, # ^ |   +1 thank you so much, this is the best explanation I have found for this problem.
•  » » 13 months ago, # ^ |   +1 I just used dynamic programming (didn't even know there is such thing as OEIS) to find the sequence of the 1D o's and the equation I found was f(k) = f(k-1) + 2f(k-2)+ 2^(k-2) where f(k) denotes the total sum of the maximum tiling for a length k vertical or horizontal row of o's, and then multiplied that by 2^(nbtotal_white-k)
•  » » » 13 months ago, # ^ |   0 can you explain this "then multiplied that by 2^(nbtotal_white-k)"?
•  » » 13 months ago, # ^ |   +4 another way to solve for some n is to iterate on len of the consecutive blocks which have same color this solves for some n in O(N). my submission
•  » » » 13 months ago, # ^ |   0 Can you please explain your solution?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +4 Ok Ill try to explain in detail, I hope you get the fact that we want to calculate answer for only a string of length N consisting of 'o' only. where 'o' can be red or blue ,so for some arbitrary painting we consider all consecutive segments of red . Now we iterate on length of this segment (you can see solve function in my code). this contributes to floor of (len/2) and we simply count how many times it occurs and add it to the answer. You can see some article on contribution technique which is what I used here.
 » 13 months ago, # |   +1 Can someone please help in suggesting an approach for another version of problem C wherein the colours of cards and query colours can be up to 3e5?Thank you in advance!
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 I was working with java. First tried with ArrayList Which definitely went TLE but using LinkedList worked.
•  » » 13 months ago, # ^ |   +5 This submission should also work for bigger C than 50.
•  » » » 13 months ago, # ^ |   0 Thanks a lot!
 » 13 months ago, # |   -9 D is so much harder than E for me. How to solve it?
•  » » 13 months ago, # ^ |   +6 D could be solved by the pattern like a+ab+ac+b+bc+c for k=3 , and then just repeat it until you reach n . Can you tell how to solve E
•  » » » 13 months ago, # ^ |   0 Can u please help me as to how u were able to come up with this pattern.
•  » » » » 13 months ago, # ^ |   +2 I came up with this pattern after looking at sample test case 1 .
•  » » 13 months ago, # ^ |   0 first of all given condition is nothing but checking substrings of length two which are repeated how many times.If you are able to observe it then your task is simply to minimize the Cost which can be minimized if two length substrings are repeated minimum times hence try to make all distinct possible two length substrings which wont be repeated if you add it to end your resulting string continue this and make your resulting string
•  » » 13 months ago, # ^ |   0 This Video might help you. Video Explanation
 » 13 months ago, # |   0 Wasted lot of time thinking about b and then I knew C, when I had opened the submission page , the contest ended notification came, now that I submit C i realize I got it correct. :(
•  » » 13 months ago, # ^ |   0 I could have easily got 2 problems right instead of one
 » 13 months ago, # |   +3 How to solve E?
 » 13 months ago, # | ← Rev. 2 →   +15 $O(nq)$ solution for problem G, using vectorization: 112850202.A completely straightforward $O(nq)$: 112827572.I understand that the my submission might be impossible to fail, but how in the world did the setters allow the second submission to pass?
•  » » 13 months ago, # ^ |   +21 Second solution is not straightforward $O(nq)$. It is auto-vectorized with GCC and has same logic as your. See assembly here. Click on cycle for and click on "reveal linked code".
•  » » » 13 months ago, # ^ |   0 Yeah, sorry. When I was writing my code GCC didn't optimize it for some reason. Also they have similar worst case performance, it's just that pretests are weak.
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 I tried several variations of your code and only a few of them passed, you can check my submission history. I guess it's easy to miss that gcc might optimize this particular problem.
 » 13 months ago, # | ← Rev. 2 →   +15 Worked like half an hour on C with fancy algos, segment tree and things...before noticing that super simple simulation works fine :/Edit: And needed some time in B to realize that the order of the two output values matters. That felt fairly uncommon for that problem.
•  » » 13 months ago, # ^ |   0 How can we do C problem if color of cards is of order 10^5(instead of 50)?
•  » » » 13 months ago, # ^ |   -14 There are max 50 colors, so max 50 positions to maintain.
•  » » 13 months ago, # ^ |   -13 Fairly SImple way to do C. cin>>n>>k; vector mp(51,-1),m1(51); for(ll i=0;i> a[i]; if(mp[a[i]]==-1) mp[a[i]]=i; } ll tot=0; for(ll i=0;i>j; cout<
•  » » » 13 months ago, # ^ |   0 this type of solution is being hacked . But why?
 » 13 months ago, # |   0 I resubmitted my problem E but the initial time of submission is shown in the standings. Which will be considered, if both of them pass?
•  » » 13 months ago, # ^ |   0 The second one
•  » » » 13 months ago, # ^ |   0 but in the standings it shows 1:53, the time of my first submission.
•  » » » » 13 months ago, # ^ |   0 I think u can see the answer in this bloghttps://codeforces.com/blog/entry/4088at "System Testing and Final Standings"
•  » » » » » 13 months ago, # ^ |   +3 Turns out my 1:53 submission was considered. Maybe the rules of resubmission are different for Educational Rounds.
 » 13 months ago, # |   +8 Why is my rate in offical the same in unoffical?
 » 13 months ago, # |   +18 G O(NQ)
 » 13 months ago, # |   -26 Well, Contest was really a good one B and D were really good problems but one thing which I observed is that in previous three contests there were overall three problems which were googleable which is a bit weird on platform like codeforces which is known for its originality.A lot of People copied code of linked list in C problem today which makes it somewhat unfair.
•  » » 13 months ago, # ^ |   0 I doubt, C was an easy question, it was about common sense. How could one even use linked lists in the question, in a limited timeframe ?
•  » » 13 months ago, # ^ |   +43 Linked lists :)...Lol, these people are dumb!
 » 13 months ago, # |   +2 I think my D is different from all Please hack it. 112846805
•  » » 13 months ago, # ^ |   +1 Yes my submission is also similar to you https://codeforces.com/contest/1511/submission/112834762
•  » » » 13 months ago, # ^ |   0 Yes It seems like we have found global minima for the sequence by just considering one extra step beyond i+1th character. It is like summation of all local Minima converging to global Minima.
 » 13 months ago, # |   0 I am really sad today , wasted a lot of time in D then at last forgot to assign one of the variable to 1. :(
 » 13 months ago, # |   0 in question B the order of output matters , that's wrong , it costed too much
•  » » 13 months ago, # ^ |   0 yeah , i got the idea and implemented it. It shows wrong answer i spend approx 10 min to find that order matters.
•  » » » 13 months ago, # ^ |   0 yes i spend almost the entire time and recognised it very late that the order matters.costed me 4 wrong submission and a hell lot of time.
 » 13 months ago, # |   0 can anyone tell me how to approach A in today's contest?
•  » » 13 months ago, # ^ |   0 Just put all the 1st and 3rd type no. in one server and 2nd type no.s in another server
•  » » » 13 months ago, # ^ |   0 ok thank you
 » 13 months ago, # |   0 14th test for D TLEd me, although on the PC it takes 0.4 sec. How is it even possible?
•  » » 13 months ago, # ^ |   0 Most likely undefined behaviour, like an array out of bound access or the like.
 » 13 months ago, # | ← Rev. 2 →   0 I am unable to figure out why my solution is not passing all the test cases ? Can someone please help by telling What am I missing? Submission : Link
 » 13 months ago, # | ← Rev. 2 →   0 .
 » 13 months ago, # |   0 awoo why this 112845193 code is giving TLE in python3.
•  » » 13 months ago, # ^ |   0 Probably just because python isn't very fast. A static array of size 50 for all the different cards would probably work.
•  » » » 13 months ago, # ^ |   0 This reply perfectly justifies your current contribution
•  » » » » 13 months ago, # ^ |   0 for i in range(n): if a[i] not in d: d[a[i]]=i+1 I think it might be due to this line a[i] not in d , this operation is O(n)https://stackoverflow.com/questions/17539367/python-dictionary-keys-in-complexity
•  » » » » » 13 months ago, # ^ |   0 I think you are saying O(len(d)) then O(3.10^5*50) will work fine in 2 sec time limit
•  » » 13 months ago, # ^ | ← Rev. 3 →   0 Your exact code passes with Pypy 3 in 1153 ms. Worth a try next time.
 » 13 months ago, # | ← Rev. 3 →   0 (Problem-B), Can anyone tell me why my code is giving Wrong answer? Thanks. Here's the link to my code https://codeforces.com/contest/1511/submission/112825682 (Test case 228)
•  » » 13 months ago, # ^ |   -8 it will give wrong ans on 4 6 1 case .
 » 13 months ago, # |   0 How to solve problem C ?
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 You just care about the minimum index for each number from 1 to 50Create an array of size 51 (i call it idx), idx[i] = minimum index for i in the inputwhen he ask for t, you put idx[t] = 1 but before changing it shift all other elements in array "idx" by 1 in case they were less than idx[t].
•  » » 13 months ago, # ^ |   +1 if you know stl it will be easy for you at first you need to store your value in deque then for each query find the expected value print it's position erase that that position's value from deque push expected value in the front of the deque you are all done ^_^ you can see my submission here
•  » » 13 months ago, # ^ |   0
•  » » 13 months ago, # ^ |   0 This Video Explanation Might Help you. Video Explanation
 » 13 months ago, # |   0 Problem C:Python3 gets accepted, the same code on PyPy3 gets TLE :DI listened to your advice and submitted PyPy and ended up with egg on my facehttps://codeforces.com/contest/1511/submission/112854945https://codeforces.com/contest/1511/submission/112860623
•  » » 13 months ago, # ^ |   0 I think it is due to a bug in pypy's implementation of dequehttps://stackoverflow.com/questions/13421326/why-is-pypys-deque-so-slow/13421804
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 It's not a bug. Not necessary a bug at least
•  » » » » 13 months ago, # ^ |   0 In pypy community it is considered a bug.
•  » » » 13 months ago, # ^ |   0 Check my solution using pypy2 it got accepted but my python 3 solution gave TLE, One thing to note here is , see the wrapper I have used for pypy submissions , it makes the code faster. Also unless you are dealing with strings always use pypy or else python as python solves string based problems faster than pypy
 » 13 months ago, # |   +14 Masters and above are in the official standings for some weird reason.
 » 13 months ago, # | ← Rev. 4 →   +31 Yesterday's contest https://codeforces.com/contest/1513/submission/112706259This is how k_Rishav bypasses Plagiarism testing. He has done this today and yesterday both, and I am sure he must have done it multiple times before as well. People like k_Rishav are spoiling the sport. I don't understand where would cheating take them in life. They will never get anywhere in life but always remain what they are i.e cheater. He should be banned from the platform as soon as possible.
 » 13 months ago, # |   +2 How to solve $C$ if distinct no of color of cards may be of order $O(n)$ ?
 » 13 months ago, # |   0 112861635 TLEcan anybody explain this !! why using LL gives tle in B??
•  » » 13 months ago, # ^ |   0 It might be that a>b, then the 32 bit integers somewhere overflow and the loop terminates, but the ll do not overflow.
 » 13 months ago, # |   0 Someone hack my solution for C, it should give RTE verdict
•  » » 13 months ago, # ^ |   +34 You can hack your own solutions
 » 13 months ago, # |   0 i forgot to use fast i/o in problem C. now i'm wondering if i'm gonna get tle
 » 13 months ago, # |   0 How to prove correctness for the approach used in D?
•  » » 13 months ago, # ^ |   0 So the cost of the string is the sum over ${occ[ij] \choose 2}$ where $i$ and $j$ are characters from $a$ to $z$ and $occ[t]$ is the number of substring $t$ in the given string $s$.You can prove that if $x \geq y+2$ then ${x \choose 2} + {y \choose 2}$ is greater than ${x -1 \choose 2}+{y+1 \choose 2}$. Then consider an optimal string. The difference in the occurrence of the maximum and minimum should not exceed $1$. With this information and the value of $n$, we can uniquely determine the maximum and the minimum number of occurrence over all substrings. This paves way for a simple cyclic construction.
•  » » » 13 months ago, # ^ |   0 I understand that we want to spread occurrences of each of the k * k substrings as evenly as possible, in that case, the string of maximum and minimum occurence will differ at max by 1. But how to construct it? Some answers said that we can take an Euler tour over the complete graph, but I don't see why it works? Can you explain that?
•  » » » » 13 months ago, # ^ |   +7 oh the construction is pretty simple. No need for euler tour. Let's say consider first f letters. You can consider this pattern: faabacadaeafbbcbdbebfccdcecfddefeefyou can cyclically iterate through this string, as you know that the difference between the max and min will be not more than 1 at any time, when you cycle through this pattern.
 » 13 months ago, # |   +5 Can C be optimised brute forced? I don't see the complexity going beyond O(50*q)
•  » » 13 months ago, # ^ |   +9 Yes. It is. subash23, Look at this submission : https://codeforces.com/contest/1511/submission/112800822
•  » » » 13 months ago, # ^ |   0 Yup I did exactly the same
•  » » 13 months ago, # ^ |   0 Shouldn't it even pass unoptimized? Is the 2 seconds alloted to answer all of the queries or for each query individually? Because I think for each query O(N^2) should pass but who knows.
•  » » » 13 months ago, # ^ |   0 No, n is 3*10^5 and so is q, even n*q won't pass
 » 13 months ago, # |   0 Did problem C had weak test case?
 » 13 months ago, # |   0 I tried to hack my solution on problem D using the test case "2000005 26" and it got hacked but same test case was there in pretest as well test case number 36I resubmitted my solution it got accepted can anyone explain to me why? thanks in advance
•  » » 13 months ago, # ^ |   0 MikeMirzayanov please look into this .. My code is hacked by a test case that was already there in pre-tests as well and same code if I submit now is giving AC verdict :(
 » 13 months ago, # | ← Rev. 7 →   0 Problem D, you can search the zero-cost string by testing if the current chosen letter will make an existing pair using set(notice that you also do not want to make the next position no choice, so check if the next pair is possible). 112873007 This string is $k*k+1$ long and costs 0. If $n>(k*k+1)$, we make it repeat. The reason is that every two repeated zero-cost string has exactly $k*k$ cost(every adjoint two letters have a collision). Also, observe that the zero-cost string starts with $aa$ ends with $a$, we do not want $aaa$ since it results in more appearances of pair $aa$, so we delete the last $a$ of the zero-cost string.However, I forgot the deletion during the contest. Not clever :<
•  » » 13 months ago, # ^ |   0 Yup did the same mistake during the contest.
 » 13 months ago, # |   0 It was better to use array than map in problem C as size was just 50 only. By using map everytime searching is done so increases the time complexity.We can use map in problem C but have to be careful that searching is done minimum time and that is possible by using a variable to store the value.
 » 13 months ago, # |   +5 Why people are getting tle in problem C? is it because we use map?
 » 13 months ago, # | ← Rev. 2 →   -6 submission (Hacked)submission (Accepted) I resubmitted my hacked solution and it got accepted! Please have a look!
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Your Accepted solution can be hacked again. All submissions will be rejudged after the open hacking phase is finished.
•  » » 13 months ago, # ^ |   +1 Now it's hacked :)
•  » » » 13 months ago, # ^ |   0 see my submission it got hacked by a test case that was there in pretests200000 26https://codeforces.com/contest/1511/submission/112856095do you know whats the reason for this? and now when I again doing it is giving unsuccessful hack
•  » » » » 13 months ago, # ^ |   +1 Sometimes you notice that if you resubmit your code it runs in different speed, This thing from CodeForces itself sometimes it differ in a little millisecondsSo always try to keep at least 100ms (depends on the problem) between your code run time and the time limit
•  » » » » » 13 months ago, # ^ |   0 But i am again trying to hack my solution with samr test case it is giving unsuccessful hack. I want to know are hacked submission also rejudged during final system testing. Is there any chance that verdict will change to accepted from hacked because its running within time limits specified
•  » » » » » » 13 months ago, # ^ |   +1 I'm sorry, Hacked solutions can't return Accepted
 » 13 months ago, # | ← Rev. 2 →   0 Better Understanding solution for B :: --For C use multiple of 10 : [pow(10,c-1)]--Find next prime of pow(10,a-c) and pow(10,b-c)--multiply c with both ( :
 » 13 months ago, # |   +2 I couldn't prove/hack my solution for D, tried to make distribution uniform, maintained a $next[$ $]$ char array of size $k$ where $next[c] = c$ initially, started with $'a'$ and appended $next[prev$_$char]$ char and incremented it cyclically. For $n = 10, k = 3$ the resulting string is $'aabbccacba'$. Did anyone try this approach and proved it?
•  » » 13 months ago, # ^ |   0 I did this as well though no proof.
 » 13 months ago, # |   0 Could someone help me to explain what's wrong with these approaches for question D? Just using greedy to get the next digits that have the lowest frequency.
•  » » 13 months ago, # ^ |   0 This Video Explanation Might help you. Check this
 » 13 months ago, # |   +8 Why the brute force can pass G?
 » 13 months ago, # | ← Rev. 2 →   0 My $O(1)$ solution for B. Felt weird but works.First i take $z$ as $10^{c-1}$ . Now $z$ has $c$ digits. I want add $a-c$ digits for $x$ and $b-c$ digits for $y$. To keep $z$ as a factor i have to achieve this by a multiplication of sum number (with $a-c+1$ digits and $b-c+1$ digits). But to keep $z$ as the GCD, two numbers used to multiply for $x$ and $y$ must not have common factors. aka coprime. But all prime numbers are coprime. Therefore i just have to find two prime numbers with required lengths. For that i precalculated these two arrays. Having two numbers for each length is sufficient. int p1[] = {3,11,101,1009,10007,100003,1000003,10000019,100000007,1000000009}; int p2[] = {5,13,103,1013,10009,100019,1000033,10000079,100000037,1000000007}; Now answer can be calculated as,$x=10^{c-1}*p1_{a-c}$$y=10^{c-1}*p2_{b-c} •  » » 13 months ago, # ^ | ← Rev. 3 → -8 my solution for B TIME O(9*285) Your code here... string s1="1" for(int i=0;i0) s2+='1',ones-- else s2+='0' if(a>b) cout<< s1 <<" "<< s2< •  » » 13 months ago, # ^ | +8 Or you could notice that 10^n and 10^m+1 are coprime for all n and m. So you could do:x = 10^{a-1}$$y = (10^{b-c} + 1) \cdot 10^{c-1}$And the expression for $y$ simplifies to:$y = 10^{b-1} + 10^{c-1}$Which I think is a pretty neat answer!
 » 13 months ago, # |   0 Can anybody tell at which test case my C is hacked? thanks
•  » » 13 months ago, # ^ |   +1 Your code is slow some cases with high constraints and a specific way to arrange the elements will hack it
 » 13 months ago, # |   0 why does this solution pass and no one can hack it? 112850106
 » 13 months ago, # |   -6 Problem C Video Editorial (ENGLISH EXPLANATION) : https://www.youtube.com/watch?v=icggEsoxWEo
 » 13 months ago, # |   +6 Where is the Tutorial? : )
•  » » 13 months ago, # ^ |   0 +
 » 13 months ago, # |   +26 The system is accusing me of cheating when I didn't cheat. It says that my problem D coincides with some other person's problem D, I think because both of us had the same idea and the implementation code is really short. My SolutionOther guy's solutionMikeMirzayanov Can you please look into this?
•  » » 13 months ago, # ^ |   +31 +
 » 13 months ago, # | ← Rev. 2 →   -22 .
 » 13 months ago, # |   +1 For problem C:Can anybody tell me why these Python3/Pypy3 solutions giving TLE.But Exact same implementation with C++ giving AC? PyPy3 Code — 112823159 Python Code — 112824003 C++ Code — 112836141 Is my implementation is wrong somewhere, or is it a Judge (Or Language) issue?TIA.
•  » » 13 months ago, # ^ |   +14 Quit using python if there is no bignum related problem. It is just a slow language.
•  » » 13 months ago, # ^ |   +9 Both solutions are bad. C++ solution works because C++ is faster.
•  » » » 13 months ago, # ^ |   0 Thanks. I realize this now, it is a bad solution indeed. I should have thought more optimized approach than this.
 » 13 months ago, # | ← Rev. 2 →   -22 I used ideone.com for coding, I dont know till now that it can viewed by anyone. Iam a trusted user and had been practicing problems genuienly,You can see my profile (to see the days I spent with codeforces) and previous contests solutions to check the templates I used,that proves my honesty.clearly its my code copied by these accounts which mostly doesn't have any activity.These accounts are meant for copying.I would request you to look into the issue hope u ban these type of accounts,and I look forward to return my ratings back. I changed default settings in ideone.com. Thanks.
•  » » 13 months ago, # ^ | ← Rev. 2 →   -16 .
 » 13 months ago, # |   0
 » 13 months ago, # |   0 Is there a way to get full testcase 7 of problem CThere is a performance regression in PyPy project and they need it to investigate, here is the link to the issue https://foss.heptapod.net/pypy/pypy/-/issues/3437#note_157645
•  » » 13 months ago, # ^ |   +3 You should contact the problem setter for that
 » 13 months ago, # |   +27 When ratings will get updated??
•  » » 13 months ago, # ^ |   0 +1
•  » » 13 months ago, # ^ | ← Rev. 2 →   -48 z
•  » » » 13 months ago, # ^ |   -17 +1
•  » » » 13 months ago, # ^ |   -11 When it says rated for division 2 means it is not rated for div3?
•  » » 13 months ago, # ^ |   +37
•  » » 13 months ago, # ^ |   +3 +1
 » 13 months ago, # |   0 In problem D. Instead of thinking so much complex i have a simple logic...and by using this i got ac.I though there are limited pairs of two alphabet so after some length whatever we choose this much have occurred previously. and lets say the count of any pair is X. so if any new occurence of that pair will cost x+1; So i have to minimize this X. it is inly possible if we distribute the occurence of pair symmetrically. Means first form all the pair by A then same with B,C,D...Z. until its length becomes N.
•  » » 13 months ago, # ^ |   0 I have also done same
 » 13 months ago, # |   +5 Why ratings are not updated yet ??
•  » » 13 months ago, # ^ |   +8 +1
 » 13 months ago, # |   +26 It seems that many O(n^2) solutions pass problem G . Maybe 4e10 "xor" operations is very fast QwQ.
•  » » 13 months ago, # ^ |   +8 interestring QwQ
 » 13 months ago, # |   +26 Why the title of this contest in the rating graph says the contest is unrated?
•  » » 13 months ago, # ^ |   0 Because it is not still rated !
•  » » 13 months ago, # ^ |   +4 Because rating has not changed yet.
 » 13 months ago, # |   +31 waiting for rating change
•  » » 13 months ago, # ^ |   +3 Me too.
 » 13 months ago, # |   +6 Why the ratings don't change ?
 » 13 months ago, # |   0 why the ratings haven't changed?
•  » » 13 months ago, # ^ |   +3 Why is the rum gone??
 » 13 months ago, # |   0 Why the rating has not updated?
 » 13 months ago, # |   0 Where's the beef? Why hasn't my rating changed? I stayed up late to participate in the contest!
•  » » 13 months ago, # ^ |   +1 It's normal for educational rounds, rating changes usually appear around 24 hours after the contest.
•  » » 13 months ago, # ^ |   +5 beef is banned in India
•  » » » 13 months ago, # ^ |   0 ig u could have come up with something btr.. js
 » 13 months ago, # |   0 During contest I misread Problem A Review Site. I thought type 3 person will downvote if there are more upvotes than downvotes, otherwise they will upvote. Can anyone guide me how I can solve this version of the problem.
•  » » 13 months ago, # ^ |   0 I think it would be optimal to send type 1 guy to the first server and types 2 and 3 to second server, and then just loop through the types.
•  » » » 13 months ago, # ^ |   0 I thought the same but it actually fails for this test case - 2 3 3 Your answer would be 1 but correct answer is 2.
•  » » » » 13 months ago, # ^ |   0 As the statement mentioned : "type 3: a reviewer hasn't watched the movie — they look at the current number of upvotes and downvotes of the movie on the server they are in and decide what button to press. If there are more downvotes than upvotes, then a reviewer downvotes the movie. Otherwise, they upvote the movie.", you can easily put all of the people from type 1 and type 3 in server 1 and the rest of them in the second server, So the answer is the number of '1's and '3's in the input array.
•  » » » » » 13 months ago, # ^ |   0 Please read the original comment one more time.