vovuh's blog

By vovuh, history, 17 months ago, translation, ,

Happy New Year to all of you! So, meet another round from blue :)

<copy-pasted-part>

Hello!

Codeforces Round #531 (Div. 3) will start at Jan/09/2019 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD1:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Jester 6 196
2 eneas 6 224
3 Nutella3000 6 267
4 pedulia 6 288
5 I_love_albeXL 6 297

Congratulations to the best hackers:

Rank Competitor Hack Count
1 ______-__________-______ 299:-99
2 im0qianqian 100:-3
3 greencis 97:-23
4 minhson 52:-2
5 MarcosK 35
1183 successful hacks and 1459 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Isabella_Vesterbury 0:01
B ThankGodItsFriday 0:05
C Voronin_Ivan 0:05
D GiveMeAGirlFriend 0:16
E EremKa 0:21
F RedDreamer102 0:43

UPD2: Editorial is published!

UPD3: I forgot to thank eddy1021 for help with testing the round!

• +203

 » 17 months ago, # | ← Rev. 2 →   +34 I was a bit surprised when I saw the black MikeMirzayanov lolupd: I mean I am used to the magic MikeMirzayanov
•  » » 17 months ago, # ^ |   +93 He is white...
•  » » » 17 months ago, # ^ |   -7 deep message ._.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +74
•  » » » » 17 months ago, # ^ |   +55 Why his ears are white?
•  » » » » » 17 months ago, # ^ |   -9 cause im a programmer not a graphist
•  » » » » » » 17 months ago, # ^ |   +34 Dont be racist nigga
•  » » » » » » » 17 months ago, # ^ |   0 u are white. Don't tell me u wrote that with a black pen cuz it is still offensive roflan
•  » » » » » 17 months ago, # ^ |   -20 When u write a question of this kind in English u put the verb in the second position. It's common knowledge. It also sounds really odd. come'on! Pls don't call me a grammar nazi lmao
•  » » » » » » 17 months ago, # ^ |   +25 a PROgrammar nazi
•  » » » » 17 months ago, # ^ |   0 Gold.
•  » » » 17 months ago, # ^ |   +36 Man, at first sight I thought you were Radewoosh who changed his handle or something.That dp though xD
 » 17 months ago, # |   -8 Good luck to everyone <3 !!
•  » » 17 months ago, # ^ |   0 thank you
 » 17 months ago, # | ← Rev. 2 →   -30 I think CODEFORCES loves me! Whatever comment(or reply) I make (I tried many kinds. Contributed, Made memes, Helped people etc.), always get dozens of upvotes. I'm really happy about it. I want to keep contribute.
 » 17 months ago, # |   -15 17.35 (MSK) for contests is really inconvenient time for all who works in the office )
 » 17 months ago, # |   +3 See you guys at expert. I wish..
 » 17 months ago, # |   0 I didnt like first div3s but I think it evolved and now there some good problems init
 » 17 months ago, # |   0 6 or 7?
•  » » 17 months ago, # ^ |   0 mostly there will be 2 part of problem
 » 17 months ago, # | ← Rev. 2 →   0 Oh no... "copy-pasted-part" is reaching another level. People will make memes with it (probably). Then it will die. Although it makes me laugh when I see a round begining and starting with it, stop overusing it. It will die :(
 » 17 months ago, # |   +11 OMG, Mr Vovuh, when did u become blue? (( so sad... Is it because u are tired of session?I wish u fast uprate
•  » » 17 months ago, # ^ |   0 Well, in last two rounds I had really bad luck and missed too many easy key ideas because of my brain (idk what's wrong with it) and because I didn't participate in any contests after NEERC at all. So I forget how to solve problems fast
•  » » » 17 months ago, # ^ |   +16 Lol. I thought you used the 'color changer' to get blue.
 » 17 months ago, # |   +54 "You will be given 6 or 7 problems and 2 hours to solve them." Can we assume that or as bitwise OR? 6|7 = 7
•  » » 17 months ago, # ^ |   +7 Actually, because of precedence of operators, it is: (given 6) | (7 problems) = 69. So today we will have 69.
•  » » 17 months ago, # ^ |   0 hahah too funny
 » 17 months ago, # |   0 Huge participation :)
 » 17 months ago, # |   0 Feeling like gotta explain the reference in task C to English speaking participants. It is about a Russian video where policemen broke into an insane man's flat, by breaking his door. He was kind of surprised by that. He also appears to be very concerned and upset about that and wants them to repair the door and leave.Here's the video (NSFW to anyone who knows Russian): https://www.youtube.com/watch?v=pJTSfvtM8iYIt made me laugh so hard, I wasted 10 minutes of my time on that. Well done, Vovuh! (how to tag a user btw?)
•  » » 17 months ago, # ^ |   +1 to tag a user: press "user" in the right of spacebar at the top of a message
 » 17 months ago, # |   +6 The problems are in appropriate difficulty for div3 contest,thanks.
 » 17 months ago, # |   +4 A today : 899C - Разбиение чисел
 » 17 months ago, # | ← Rev. 2 →   +44 I'd love to see the look on this guys face after he got WA on this test I specifically crafted just for the similar solutions (48143945) :D
•  » » 17 months ago, # ^ | ← Rev. 2 →   +7 if(m==69) return 0;
 » 17 months ago, # |   +6 Submitted F successfully at 1:59:20 ... Phew!!!
 » 17 months ago, # |   +1 How to prove A?
•  » » 17 months ago, # ^ |   +7 You can construct the solution for x from solution of (x-4)Base cases: n = 0 => ans = 0, n = 1 => ans = 1, n = 2 => ans = 1, n = 3 => ans = 0
•  » » 17 months ago, # ^ |   +9 Suppose you have numbers x, x + 1, x + 2 and x + 3. Then you can take x and x + 3 to the first set, x + 1 and x + 2 to the second set and the difference between their sums will be 0. So you can take n modulo 4 and just solve it manually.
•  » » 17 months ago, # ^ |   0 The summation from 1 to n is n*(n+1)/2, let it be S, if S is even we can straight away divide the array into two subsets such that, the sum for both the subsets are equal, thus giving a minimum of 0, in the case of S being odd, since the division will not happen equally, the difference between the sum of two partitions will be at least 1, since the difference will be caused by any two numbers which are consecutive in nature.
•  » » » 17 months ago, # ^ |   0 Thank you! I solved it but didn't know why it worked tho :D
•  » » » 17 months ago, # ^ |   -23 When a newbie explains better than an expert!
•  » » » 17 months ago, # ^ |   0 This argument isn't thorough. I agree that the optimal difference will be equal to the parity of the sum, but it's not guaranteed we can achieve that.For example, if your array is [2, 4, 8], the sum is 14, but the best possible division is [2, 4] and [8], which has an absolute difference of 2. It's important to prove that the optimum division can be achieved for the set [1, 2, 3, ..., n]. I proved this using the same logic as Vovuh above.
 » 17 months ago, # |   0 (48141727) why this solution for problem E is wrong? what is testcase 32?
•  » » 17 months ago, # ^ | ← Rev. 4 →   +1 You could try this test case: 1 1 2 2
•  » » 17 months ago, # ^ |   +6 After some precalculations, one can do bitmask DP to find the maximum answerMy recurrence relation was DP[mask][first line][last line]
•  » » » 17 months ago, # ^ |   +3 Thank you! Unfortunately, I could not solve this during the contest :(
 » 17 months ago, # | ← Rev. 2 →   +2 Hello mister Vovuh. First things fist, thanks for the support that you've shown to us with these rounds but i think this was a bit messed up.Problem A was ok, but i don't quite enjoy these "intuition" type problems because when i saw it i was like : "yes, that got to be the solution", without proving it.Problems C and D was really good, altough the 10^100 statement was a bit unclear (infinite number of turns worked as well :p) But gosh, problem B was a nightmare and it seemed terrible tbh, like i think that excluding the case where max_appearance of a number < k would have made it a perfect 1000-1200 B problem. C was easier than B. I didn't have time to think on E or F, but my guess is E was solved using DP but F i dunnoThanks for the round yet again! Waiting for that editorial.
•  » » 17 months ago, # ^ |   +10 Haha, I actually think difficulties worked out surprisingly well. When I solved C (it was B at the time), I said Vovuh it's really hard for B (and for C, tbh). He told me the less complicated solution, but still. After that E was added and I felt it was even easier than C. And it turned out, Vovuh was about right about all the difficulties (considering B had hard to understand statement).
•  » » » 17 months ago, # ^ |   0 I got C really quick but i don't know if my solution was optimal. I still think C was a better B. Now i tried an easy O(n^2) solution for B and it worked....During the contest i was so sure it wouldn't work that i didn't even try it. Pff, in my country, the complexity, time limit and things matter so much, i wouldn't even think about these types of solutions.
•  » » » 17 months ago, # ^ |   0 unfortunately , till now I can't understand B but luckily get solution for C .I think this div3 contest is more harder than last div3 contests that prepared by Vovuh . he has kill my dream to be pubil hhh . but , in general great thank's for his effort and great conests ^_^
 » 17 months ago, # |   +6 could anyone explain problem F?i have no idea about it,thanks.
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 After some precalculations, one can do bitmask DP to find the maximum answer 48133701My recurrence relation was DP[mask][first line][last line]
•  » » » 17 months ago, # ^ |   0 You could write a backtracking with randomized order. Solution
 » 17 months ago, # |   0 Hi, Could anybody help me what is wrong in my solution for problem D SolutionThanks!
•  » » 17 months ago, # ^ |   0 it is because your code make more changes than the minimum.see my code
•  » » » 17 months ago, # ^ |   0 I didn't get how the number of changes are more.What I have done is that increasing count of 0 first, then of 1 and then 2(whichever is necessary). As soon as the count becomes n/3 for all 3 values, I stop making changes. So how are the changes more than the required minimum value?Giving a counter case of small size will be helpful for me to understand.
 » 17 months ago, # |   +1 why this solution on A, didn't get TLE while its running a for loop of n, where n can be as large as 2e9?
•  » » 17 months ago, # ^ |   +5 Compiler optimizations
•  » » » 17 months ago, # ^ |   0 can you explain more please? do the compiler translate this kind of stuff like for loops calculating sum of numbers 1 to n, or similar things into an o(1) pre-process refrencing?
•  » » » » 17 months ago, # ^ |   0 Compiler optimizes simple stuff and makes them O(1). Given that CF is very fast, such solutions will pass system tests too
•  » » » » » 17 months ago, # ^ |   0 thanks
•  » » » » » 17 months ago, # ^ |   +1 It's not O(1). It's O(N), however, the operations done in the loop are very simple and C++ is very fast in those situations. It's possible that the compiler does some optimizations like loop unrolling, but it's still O(N).
•  » » » 17 months ago, # ^ |   0 can you explain bit more?
•  » » 17 months ago, # ^ |   +32 So his solution has a loop of size 2 × 109 which the compiler optimizes for him. And he overflows 32-bit integer which does not matter since we're only interested in the last bit.
 » 17 months ago, # |   -26 I cannot understand, why this Div.3 was about 2 times harder than last Div.2, and even others
•  » » 17 months ago, # ^ |   +2 i am agree with you for problem b.but others are not really hard.
•  » » » 17 months ago, # ^ |   -8 Problem B was terrible and F was too hard for Div.3 imo Others were right
•  » » » » 17 months ago, # ^ |   0 Problem B is not that terrible if you think in the right way. It's pretty easy to check if there is a way to give them a color or not. To choose the colors you can, sort the values, iterate through them and give them an increasing color using modulo.
 » 17 months ago, # |   0 In Open Hacking Phase, If I hack someone's solution, How will it effect my ranking. Also, Can someone explain the role of penalty.
•  » » 17 months ago, # ^ |   0 If you hack someone's solution, you (may) climb 1 place. Your ranking will increase(or decrease, in case you get hacked).Penalty is meant to separate contestants with the same amount of problems solved.
•  » » » 17 months ago, # ^ |   0 Can someone explain,How penalty is calculated ?
•  » » » » 17 months ago, # ^ |   0 Sum of times in which you get accepted + 10 minutes * amount of wrong submissions
•  » » » » » 17 months ago, # ^ |   0 Thank you for making things clear.
 » 17 months ago, # |   +5 Aren't they the same?
•  » » 17 months ago, # ^ |   0 Oops, doesnt seem right NeverBeNutella :think:
 » 17 months ago, # |   +1 Thanks for nice problems, Vovuh!Too bad I couldn't translate my solution for F 48149115 from python to C++ in time (got it accepted late by several minutes with 48154003) :'cBy the way, I know that Codeforces community mostly code in C++, but wouldn't it be better if there were different TLs for different languages, as on HackerRank?I understand that such a change requires a lot of resources (both human time and hardware) and, probably, is not in the priority queue of Codeforces' developers (or have a low priority).I also haven't searched Codeforces for the discussion of this idea, so maybe there is already a consensus that such a change won't be introduced, (in this case I kindly ask you not to dovnvote my comment as duplicate), but otherwise it can be food for thought for the amazing Codeforces team.
•  » » 17 months ago, # ^ |   +23 this would give an advantage to python coders, because coding in python may take less time than coding the same solution in c++ because of built in functions, simplifications, etc;
•  » » » 17 months ago, # ^ |   0 First, in order to use something you should know about it, and I think that it is a good idea to reward any such knowledge.Second, all less or more advanced C++ contest programmers have a lot of pre-written code that somewhat equalize the powers. Not to mention that there is a lot more code online implementing different algorithms in C++ (e-maxx is a nice example) than in Python.By the way, writing Python code is not always easier than writing C++ code.
•  » » 17 months ago, # ^ |   +15 Those time limits are incredibly difficult to get right — HackerRank has many problems where writing a suboptimal solution in a slower language actually nets you more points, which is pretty counter-intuitive. This system, while harsh to slower languages, minimizes the work testers / setters have to do and has fewer slow solutions unexpectedly pass.
•  » » 17 months ago, # ^ |   +1 In "Baekjoon Online Judge", Korea's biggest online judge, we can submit in about 40 (Not quite sure the exact number. Different compiler version counted.) different languages and they all get different time and memory bonuses. For example, if C++ solution has TL x second and ML y MB, all python solutions will judged with TL (3x+2) second and ML (2y+32) MB. Kotlin Native solution will be judged with same TL with C++ and (y+16) MB ML.This is great for python coders and most of JAVA coders. However, this had also made countless problems too. There are a lot of problems which something like in C++ you'll get TL with naive solution but with python you can actually fit the naive solution.To solve this problem, community members make harder datas or even "temporarily change the TL/ML bonus only for that question". This actually happens a lot. Then the system rejudges every single solution submitted for that problem — which is possible because it is online judge, not a competitive programming platform, and There are only 1/4 problems there.Baekjoon Online Judge holds Competitive Programming contests like codeforces gym, and to avoid these problems some setters just ignore the BOJ basic policy and make sure that the contest will ignore TL/ML bonuses (and it is allowed for setter to do so).I believe it is not only extremely difficult in terms of resources, it may have some unintended results which in Codeforces it will be harder to fix.
 » 17 months ago, # |   0 Can someone tell me the error in this? I don't see any difference between my output and the answer for Testcase #6 (as far it's visible on screen). Submission
•  » » 17 months ago, # ^ |   +1 Maybe I am missing smth obvious, but can you explain me why you don't one-- here: for (int i = 0; i < n && zero < k; i++) { if (chars[i] == '1') { chars[i] = '0'; zero++; } } It looks like you are using one after this loop, and therefore it should have a correct value.
•  » » » 17 months ago, # ^ |   0 Got it. Thanks! :)
 » 17 months ago, # |   0 Can someone help me with problem B?The verdict says its wrong on test case 1 which is 4 2 1 2 2 3 my code has given output NO but on my laptop its running correctly. i really am confused about this..i checked others (successful)code as well the logic is same as mine. what is really shocking to me is how my code is giving a different out put on my pc and different on codeforces. the link is herethis
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 Second for loop "i" is reaching the number 5001 and checking if (hash[i] > k), while the maximum index of that array is 5000 as you defined it. the index is out of bound , so it is calculating the wrong number and flagging it. it works on some compilers and on others it doesn't. fixing this should let you pass the first test.
•  » » » 17 months ago, # ^ |   0 Fixing that let me pass all the test cases.
•  » » 17 months ago, # ^ |   +4 From line 16 to 27: you are traversing the variable i from 0 to 5001, which caused a certain undefined behavior / memory violation since element hash[5001] didn't exist.
•  » » » 17 months ago, # ^ |   +8 Yeah got it thanks!!Totally overlooked it and i dont know why my compiler didnt give a wrong output.
•  » » » » 17 months ago, # ^ |   0 The name of the problem type said it all — "undefined behaviors". Thus, different compilers might behave differently, sometimes correct, sometimes not. One assurance you can make for yourself is to test your solution on "Custom invocations" tab of Codeforces.
•  » » 17 months ago, # ^ |   0 It's undefined behaviour, happens on your second for when you access hash[5001]
•  » » » 17 months ago, # ^ |   0 Yes thanks!!.
 » 17 months ago, # |   +1 I saw an accepted code for the problem 'A' in which he/she uses a loop to calculate counter.LOL.I thought to hack it but then normal test cases are also of that order and the program passed for it as well. I have no idea.
•  » » 17 months ago, # ^ |   +1
 » 17 months ago, # |   0 48157132 — what am I doing wrong? :(
•  » » 17 months ago, # ^ | ← Rev. 5 →   +7 You cannot simply divide the answer by 2 in the last line, since such division might not work.For example: if the true answer before dividing is 998244354, if you divide its modulo, your output will be 0 instead of expected 499122177.To do this, you'll need to multiply your answer by modular inverse of 2 by modulo 998244353. Remember to take the remainder of the product again (since obviously there is a high chance that it might exceed 998244353).
•  » » » 17 months ago, # ^ |   +8 Thank you so much! You're amazing :)
 » 17 months ago, # |   0 can someone explain me the problem B please ? I can't understand it through the contest
 » 17 months ago, # | ← Rev. 2 →   0 anyone thought about problem E in a DP approach?! is it possible to form the states ?
 » 17 months ago, # |   +1 How to solve F?
•  » » 17 months ago, # ^ |   +6 DP+Bitmasking. DP states are mask,last row,starting row.Here mask represents which rows are selected and cannot be selected again.Starting row represents the first row and last row represents the row of previous position.
•  » » » 17 months ago, # ^ |   0 Can you elaborate more ?
•  » » » » 17 months ago, # ^ |   +1 We will use 0-index array, so row index are from 0 to n - 1, column index are from 0 to m - 1.For each choice, to calculate the acceptable of table we need to calculate minimum of |ai, j - ai - 1, j| and |ax, k - ay, k - 1| where x and y is first row and last row. So we realize DP state should have first row and last row.Assume we have a DP state (x, y) and we want to add a row z behind row y. Then we want to make sure row z doesn't appear in above state. So we should add a binary state which tells you which rows are used, because number of rows is small. Then the DP state is (x, y, p) (1 ≤ x, y ≤ n, 1 ≤ p < 2n). We call it fx, y, p.If we let fx, y, p be minimum of |ai, j - ai - 1, j| and |ax, k - ay, k - 1| of a table with state (x, y, p), it would be impossible to calculate fx, z, q depends on fx, y, p. In fact, fx, y, p should only be minimum of |ai, j - ai - 1, j| of table with state (x, y, p), and minimum of |ax, k - ay, k - 1| can be calculated later.For each pair (x, z), we iterate all states (x, y, p) which bit x and y are represented in p, while z is not, and fx, y, p exists (has been calculated). Then p' = p + 2z and f(x, z, p') = max(f(x, z, p'), min(f(x, y, p), min(|ay, i - az, i|))). Result is min(fx, y, 2n - 1, min(|ax, k - ay, k - 1|)). We can see from the formula above that if fx, y, p has been calculated, then x and y must be represented in p, so we don't need to check x and y.To initialize DP state, we assign all value to  - 1, to show that these value hasn't been calulated.The only value we know is fi, i, 2i and we should assign them to ∞ (notice our DP formular). When n = 1, f1, 1, 1 = ∞, but it doesn't matter because we can iterate in last step to calculate result, since 2 ≤ nm.I want to warn you of iteration order. We should iterate the binary state first to get correct answer. It seems to give us correct order of DP. I haven't figured out why iterating x and y before p could give wrong answer. I think it due to the way we treat which DP value is calculated.
•  » » » » » 17 months ago, # ^ |   0 Thank you :)
•  » » » 12 months ago, # ^ |   0 why we can't do using only DP states mask and last row.
 » 17 months ago, # |   0 I want to be an expert in this round :D
 » 17 months ago, # |   +5 My solution for E:1) We will start filling array b from the left as we know b[1]=0, we can either increment this 0 in the next element in b array or not (as stated in the third condition)2) if we think about the second condition (if a[i]=a[j] --> b[i]=b[j]), we notice that not only b[i]=b[j], but also all b[i]=b[k] ; such that i<=k<=j, as we cant decrement as we move from left to right. Let's call elements from index i to j 'connected component'.Consider this example:1 2 3 1 3 2 10 10 10b[1]=b[4]=0 (first & second condition), so if we have b[3]=1, then the third condition is violatedThe solution depends mainly on the number of these 'connected components' that must have the same value in array b, in the previous example we have 2 components. First one is: (1 2 3 1 3 2) , Second one: (10 10 10)So how many ways are possible? Thinking of it like for every position we can increment or stay constant (2 choices). Then, the answer is just 2^(CNT-1), not 2^(CNT) as we can't increment in the first connected component, it must be 0.Remember to use mod, correctly count number of connected components.My submission link: https://codeforces.com/contest/1102/submission/48158289
 » 17 months ago, # |   0 Can anyone share your idea of problem D? Thanks :)
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 Basically we count the 0's 1's and 2's.they should all equal X = (the string length) / 3;if not then we swap these depending on the best lexicographical outcome. if the 0's are more than X then we need to swap some 0's to 1's or 2's, and the best way for lexicographical order is to swap the last 0's from the string because the 0's on the left assure a smaller lexicographical string, if we are missing both 1's and 2's we swap the 1's first because the 1's also assure lower value, after that we swap to 2's , else we just swap the number that is lower than X. if the 1's are more than X then we swap the first 1's with 0's -**IF (0's are missing)** — and then swap the last 1's with 2's — IF (2's are missing). if the 2's are ore than X then we swap the first 2's with 0's — IF (0's are missing) - and then NEXT first 2's with 1's — IF (1's are missing) .
•  » » » 17 months ago, # ^ |   0 Well A-m-z :). Nice explained. But I don't understand if 0s are more than 1,s and 2,s why we try 1,s swap first. Since we want lexi. minimum string we should try 2,s swap first. :) Anyway Thanks :)
•  » » » » 17 months ago, # ^ |   0 Actually two case will arise in case when we need to reduce numbers of '1' to n/3. In this case first run a loop from 0 to n-1 to swap with '0' then use another loop from n-1 to 0 to swap with '2'.see my solution https://codeforces.com/contest/1102/submission/48162307
•  » » 17 months ago, # ^ | ← Rev. 4 →   +1 I'm too lazy for write the proof, my solution use a greedy approach, i put the numbers in order (0, 1, 2) of course if is necessary to put them (cnt(#i) < n/3), and can be generalized for k digits instead of three. 48136350
 » 17 months ago, # |   -19 I guess Mr. Vovuh purposely gave weak testcases in B. Array K-Coloring. This is bad, users are not given to chance to improve during the contests. They solve and move forward.
•  » » 17 months ago, # ^ |   -19 Todays problem B was also slightly bad statement(hard to understand). It should be Problem C. Vovuh should understand people will surely attempt problem B first then they go for problem C. In my opinion problem C was too much easy than Problem B. Hopefully Vovuh will understand and next time we will get better contest. Thanks Vovuh for this type of contest. Its really helpfull contest for beginner. :)
•  » » 17 months ago, # ^ | ← Rev. 3 →   +2 B has a simple solution, I(and probably the problemsetters too) don't get why people tend to overcomplicate things for problems like A and B which can be solved with naive solutions most of the times.For example, even though I obviously know how to solve B in O(n log n), it wasn't needed in this case, and O(5000^2) works fine enough and it's simple to write.Also, in the end, no matter how strong the initial tests are, they are still pretests so fails can come at any problem
•  » » 17 months ago, # ^ |   0 Oh yes, I made weak tests in purpose! Of course! OMG... How this thought comes into your head?
•  » » » 17 months ago, # ^ |   0 I figured it out, luckily i tried tc#21 (hit & trial), that made my solution fail only because of 0 instead of 1... Mr. Vovuh this time u set all brute force problems, i was expecting some data structure problems. And yeah that profile pic, i am inspired by u.( i love cats(they are mean))..
•  » » 17 months ago, # ^ |   0 You just said B was easy to understand?
•  » » 17 months ago, # ^ |   0 It's only the problem of weak testcases, not incorrect problem statement. Thus, it's your fault that your solution got hacked or failed system test. Practice more, and try to map out every possible case within your mind.
•  » » » 17 months ago, # ^ |   0 Yes, i was aware of getting hacked/failed so i submitted twice..And yeah that tc in my mind which made my 1st solution fail, i applied it to every users solution.. And see, i hacked 14 solutions.(two valid submissions of a single user;P)..
 » 17 months ago, # |   0 I am getting a runtime error (exit code 3) on test 5 for problem B. Can someone tell me where the error is caused? The testcase isn't being shown completely since it's too big. I considered a vector of sets and tried to insert the numbers and stored the equivalent locations in l.
•  » » 17 months ago, # ^ |   0 Line 61 in b.at(j)
•  » » » 17 months ago, # ^ |   0 Thank you for your reply. I checked the value of j with the watch(x) function #define-d and saw j's range is [0,k-1]. b is a vector of size k, so b.at(j) should be ok, I think. I'm not able to find out what exactly is going wrong. Can you please explain?
•  » » » » 17 months ago, # ^ |   0 I tried it on my computer with 5000 200 and 5000 random numbers and it worked, I didn't get a runtime error
•  » » » » » 17 months ago, # ^ |   0 Try:  2 2 1 1
•  » » » » » » 17 months ago, # ^ |   0 Oh ok, thank you. I'll try to fix it.
 » 17 months ago, # |   0 What do I get for one successful hack?
 » 17 months ago, # |   +1 You're crazy and I'm out of my mind
 » 17 months ago, # | ← Rev. 2 →   +1 Hello, for this submission (48133245), I think it outputs a redundant character at the same time after outputting the answer. It passes the test point. I am not sure whether this submission is correct or incorrect, or checker does not solve this problem completely.Thank you! Time: 15 ms, memory: 156 KB Verdict: OK Input 4 2 1 2 2 3 Participant's output YES 1 1 2 1� Jury's answer YES 1 2 1 2 Checker comment ok Ok 
•  » » 17 months ago, # ^ |   0 you're correct!
•  » » 17 months ago, # ^ |   0 I guess that's a null-character, and the checker probably ignored it or considered it as a whitespace.
 » 17 months ago, # |   +6 Do we have system testing? Run all hacking test to all competitors?
•  » » 17 months ago, # ^ |   +1 I think we have
•  » » » 17 months ago, # ^ |   0 Okay. We had :)
 » 17 months ago, # |   -13 Yesterday's contest : ABABBD
 » 17 months ago, # |   0 When will the ratings change?
 » 17 months ago, # | ← Rev. 3 →   0 Though some people have already asked above, still I din't get it. How to solve F ? . P.S: Please care to elaborate your solution .
 » 17 months ago, # |   +2 Yeah, Im Expert now xD :D
 » 17 months ago, # |   0 What happened to good ol' editorials?
•  » » 17 months ago, # ^ | ← Rev. 3 →   +4 I think, it would be a great idea if blue/purple/orange/red guys that solved all problems during the contest will write editorials. I mean, for div3 and div2 contests, there are a lot of people who could do that. For div3, even I can write an acceptable editorial. It's also hard for Vovuh to write every editorial, it's really exhausting. Moreover, writing editorials will increase your contribution (if someone is interested in it).
 » 17 months ago, # |   0 Could anyone give me a solution for problem B?? It was terrible
•  » » 17 months ago, # ^ |   0 https://codeforces.com/contest/1102/submission/48132783 I put first k colours to the first k numbers. Then I start iterating over remaining elements and create variable cur initialised with 1 and check if 1 hasnt been used for the same number before by using hash. If it isnt simply put cur in the answer for that element. Else increase cur.If cur>=k at any time answer as false.
 » 17 months ago, # |   0 can anyone explain question E clearly ?
 » 17 months ago, # |   0 In problem E..submission made in C++14 using unordered_map gives tle..https://codeforces.com/contest/1102/submission/48176297while same submission using map gives correct verdicthttps://codeforces.com/contest/1102/submission/48176416Is there any way to know when to use map and when to use unordered map as in both cases pretest are passed!
•  » » 17 months ago, # ^ | ← Rev. 2 →   +9 You just need to understand what each of those data structures do. unordered_map implememts a hash table and, as such, it takes contsant time per operation on average BUT linear time in the worst-case.Cleverly designed anti-hash tests can be conceived to force the worst-case scenario (and this is very likely to happen with 12-hour open hacking). There are some tricks you can do to get around that though (you can find countless threads about this on codeforces).map on the other hand implements a BST and, as such, will run in logarithmic time in both average and worst case scenarios.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 Maybe it'll get away with hashhack.48279914
 » 17 months ago, # | ← Rev. 2 →   +5 Anything wrong with the standings?My contests in profile says my rank is 14 and the current standings says it's 6th.What's going on? :P What Abracadabra is that? xD
•  » » 17 months ago, # ^ |   +15 Remember that only the trusted participants of the third division will be included in the official standings table.Take a look at the link to see the criteria for "trusted participants". There might be users, which are still eligible to have this contest as rated, but do not fulfill the "trusted participants" criteria.
•  » » 17 months ago, # ^ |   +8 Thanks Akikaze for your response. I'm quoting the important part collected from that link if anyone's interested to know as well. " Accounts that materially participated in less than 2 rating rounds (materially means solved at least one problem there) before the start of the Div. 3 rounds, and those who have ever gained 1900 or more rating units will not get into the official standings and will be assigned to separate rooms. However, this does not mean that there is no rating recalculation for them. Thus, the rating will be updated for all users whose rating is strictly less than 1600 at the time of the start of a round." 
 » 17 months ago, # |   0 It seems like the statement for problem C isn't available anymore
•  » » 17 months ago, # ^ |   0 same time lol https://codeforces.com/blog/entry/64435
 » 17 months ago, # |   0
 » 17 months ago, # |   0 48184426 I am getting TLE on testcase 48 of problem E. Can anyone point out what can I do to improve it?
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 You are using an unordered map. Either change it to a map or randomize the key(example by taking xor with a random number generated using high resolution clock) in unordered map to avoid anti hash tests.See the comment above for more information : https://codeforces.com/blog/entry/64379?#comment-483358This blog explains it very well — https://codeforces.com/blog/entry/62393
 » 17 months ago, # |   0 When will this Vovuh get free from his evil cat and upload tutorial? Plz upload fast.
 » 17 months ago, # |   0 Why the problem E is "Time limit exceeded on test 48" if i used "unordered_map", but code is right if i used "map".