Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### vovuh's blog

By vovuh, history, 3 years ago, translation,

Hello!

Codeforces Round #490 (Div. 3) will start on June 21 (Thursday) at 14:35 (UTC). You will be offered 6 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 problems and 2 hours to solve them.

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 Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

UPD: Also great thanks to step_by_step, kevinsogo and nhho for help in round preparation and testing the round.

UPD2: The results table!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 EricHuang2003 6 150
2 JerryKFC 6 151
3 Lovely_qgq 6 170
4 Meroeht 6 181
5 MYTH_vs_REALiTY 6 209

Congratulations to the best hackers:

Rank Competitor Hack Count
1 djm03178 30:-2
2 2014CAIS01 13:-3
3 quailty 5:-2
4 Harmonium_Wale 4:-2
5 kimden 2

110 successful hacks and 226 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A jh05013 0:01
B JerryKFC 0:02
C abrunoaa 0:03
D T______________T 0:21
E NamikazeBoruto 0:11
F Counting_Stars 0:20

UPD3: Editorial

• +171

 » 3 years ago, # |   +24 Thanks for conducting another div3 round!! Looking forward for participation :)
•  » » 3 years ago, # ^ |   +63 I love it when people downvote comments for no apparent reason. The community of codeforces is great :)
•  » » » 3 years ago, # ^ |   -52 You know sometimes I downvote some users comments even before reading the comment, I just cant stand those users :3
•  » » » 3 years ago, # ^ |   -28 yep,but i downvoted u for a reason (your sarcasm):|
 » 3 years ago, # |   +12 Why it's not in the homepage?
•  » » 3 years ago, # ^ |   +15 Now it is :) Sorry for delay
 » 3 years ago, # | ← Rev. 3 →   -66 Can't be there some provision that people with rating(1600-1899 or maybe some lower) can also participate in div3(rated for them too) rounds with a totally different rank list i.e no cushioning for them and ensuring that ratings don't cross past 1899.And as stated during announcement of div3 rounds problems will be easy for participants in the range 1600-1899,so it will be matter of just time.ORMaintaining a different rating graph can also be a way.
•  » » 3 years ago, # ^ |   +20 I don't understand what the point of something like this would be. Maintaining two different rating graphs would be an enormous pain with very little payoff imo. If you really want to see how fast you can do it, just participate unofficially, it's not a big deal. Div 2 contestants get enough rated contests as it is.
 » 3 years ago, # |   0 Please if possible add some critical case during contest time in preliminary test. If someone didn't hack my solution and I got wa from final test that's the most sad moment. Again thanks for arrageing this time of contest like div3. It is very good for beginner.
 » 3 years ago, # |   0 Div-3 rocks. I think you will add some critical test cases. 
 » 3 years ago, # |   -8 i do not like ACM_STYLE
•  » » 3 years ago, # ^ |   0 The high penalty always result in my larger rank!!
 » 3 years ago, # | ← Rev. 4 →   +170 I have doubt on using 20-min WA penalty for all ACM-ICPC style contests. Usually, the contests on Codeforces are length of around 2 hours and have 5-7 problems. But in ACM-ICPC contests, there are usually much more problems (10+) and they have long contest time (3+ hours).Taking this mathmetically, let's say if a contestant A needs 5 more minutes than B to solve each problem. If they solve only 5 problems, A will get 75 more penalty than B, because every time you spent on the previous problems will affect the later solved problems' penalty. But when there are 10 problems, it becomes 275. In other words, it's proportional to the square of the number of problems. On the other hand, the penalty from the WAs would only increase linearly, as each wrong submissions have fixed penalty.I'm not the only one thinking this way as I saw similar opinions on previous Div. 3 or Educational rounds too. I'm much like for having just 10-minute WA penalty for 2-hour contests, especially in a Div. 3 round, considering the accuracy of the official contestants would be quite low. How do you think about it?
•  » » 3 years ago, # ^ |   0 True
•  » » 3 years ago, # ^ |   0 Strongly agree. It is really painful when get so many WAs in an educational round. Your rank will drop significantly. Codeforces can't just use ACM-ICPC rules without changing them according to their contests.
•  » » 3 years ago, # ^ |   0 MikeMirzayanov, you might wanna check this comment and tell us what you think about it :)
•  » » » 3 years ago, # ^ |   +69 It is good idea and likely we will adjust constant +20 soon.
•  » » 3 years ago, # ^ |   +6 Ya even codechef changed their cook off penalty to 10 min for same reason.
 » 3 years ago, # | ← Rev. 2 →   0 I tried to make strong tests I smelled FST :(
•  » » 3 years ago, # ^ |   +3 What is FST?
•  » » » 3 years ago, # ^ |   0 Failed System Test
 » 3 years ago, # |   +13 I like the term Hacked other than Failed System Test
 » 3 years ago, # | ← Rev. 9 →   +4 2 hours to solve, 12 hours to hack... That's why I love CF... And then you get a "time limit" on the main test... :|
 » 3 years ago, # |   0 Looking for more frequent div3 contests such that beginners like me can learn! :) Best of luck everyone.
 » 3 years ago, # |   -9 Rated or not? Maybe a silly question for others:(
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Rated for those who have rating <1600
»
3 years ago, # |
+7

#### IIR?

(Abbreviation of Is It Rated? :P)
•  » » 3 years ago, # ^ |   +7 Rated for people having rating<1600
•  » » » 3 years ago, # ^ |   0 Thx :)
•  » » 3 years ago, # ^ |   +4 It may also be an Abbreviation of Islamic Iran Republic, which is kind of my Specialization :D :D
 » 3 years ago, # |   -16 Open Codeforces See a contest Checks contest starting time (worries might clash with Argentina's match) Checks contest length Gives contest peacefully. PS- Thanks for not clashing it with Argentina Vs Croatia match.
•  » » 3 years ago, # ^ |   +14 Thanks for the downvotes. Will try to improve myself.
•  » » » 3 years ago, # ^ |   0 vamos Argentina
•  » » » » 3 years ago, # ^ |   0 Hmm...
•  » » 3 years ago, # ^ |   +6 And what a game!Sad time for those with Messi profile pictures :(
 » 3 years ago, # |   +11 A contest right after the senior high school entrance examination in China. Hope I will win the scores I lost these two days back as ratings.
•  » » 3 years ago, # ^ |   +8 Make the most of yourself. You are still new and promising, no worries ;)
•  » » 3 years ago, # ^ |   0 Or rather, a contest right before we can see our scores.
 » 3 years ago, # |   +1 my first div-3 contest. feeling excited!
 » 3 years ago, # |   0 It's raining contests. :)
 » 3 years ago, # |   0 Does hacking solutions increases points of the hacker?
•  » » 3 years ago, # ^ |   0 No. Hacks don't contribute to your final score on the contest.
 » 3 years ago, # |   +5 the predictor isn't working !
•  » » 3 years ago, # ^ |   +1 Now Working
•  » » 3 years ago, # ^ |   0 where can I find the predictor? Thanks
•  » » » 3 years ago, # ^ |   +8
 » 3 years ago, # |   +6 What is the test case 4 of problem E
 » 3 years ago, # | ← Rev. 2 →   0 How to solve Problem E? I was using DSU + DFS, but was getting WA!!
•  » » 3 years ago, # ^ |   0 I did BFS + greedy
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Got WA in 31st test case. I used BFS + Greedy!!
•  » » 3 years ago, # ^ |   +1 I am just finding all connected components and print number of connected components-1 but keep getting WA on TC 4
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Take a case : 9 7 5 1 9 8 1 2 1 3 4 4 5 5 6 6 3Ans will be 3.
•  » » » » 3 years ago, # ^ |   +4 No, ans will be 3
•  » » » » 3 years ago, # ^ |   0 Answer will be 3 for your test case.
•  » » » » » 3 years ago, # ^ |   0 Yes it will be 3.
•  » » » 3 years ago, # ^ |   0 same except i didn't summit because i got tested against a test case
•  » » 3 years ago, # ^ |   +1 2 DFSs — keeping track of finish time.
•  » » » 3 years ago, # ^ |   0 but what is wrong with my approach why is it not going to give correct answer
•  » » » » 3 years ago, # ^ |   0 According to your approach the answer will be 1.
•  » » » » 3 years ago, # ^ |   0 3 1 12 3Your answer = 2 (1 -> 2, 1 -> 3)Correct answer = 1 (1 -> 2)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 My idea : First, run dfs on capital vertex. While running dfs, make every path as bi-directional. Now build Strongly Connected Commponents. Count number of vertices which has 0 indegree expect the one containing capital vertex.
•  » » » 3 years ago, # ^ |   0 I applied your method. Its giving wrong answer at test case #3.
•  » » » » 3 years ago, # ^ |   0 ummm :| I think you should read this
•  » » » » » 3 years ago, # ^ |   0 Ok, I ran Dfs on capital vertex. While running DFS, i made bi-directional edge. (Thus every point reachable by capital can reach back to capital). Now i built strongly connected components.....(Correct me if i am wrong until this point). After that, my idea is to count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.
•  » » » » » » 3 years ago, # ^ |   0 (Correct me if i am wrong until this point) As long as you use correct algorithm, (like tarjan's SCC or something) I think it would be fine. count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.You can just count number of SCC vertices which has 0 indegree, but when counting, exclude a SCC vertex which contains the capital vertex.
•  » » » » » » » 3 years ago, # ^ |   +3 Gotcha!! Thanks.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Kosaraju I think
•  » » » 3 years ago, # ^ |   0 I used a similar idea but I didn't find the strongly connected components that Kosaraju does.
•  » » » » 3 years ago, # ^ |   0 What was your approach then?
•  » » » » » 3 years ago, # ^ |   0 You run two DFSs. The first time you keep track of all the finishing times of the DFSs. Then run a DFS starting from the capital city. Then, while some cities are unvisited, keep starting a DFS from the unvisited city with the highest finish time, adding one each time we do.
•  » » » » » 3 years ago, # ^ |   0 Its Kosaraju :P
•  » » » » » » 3 years ago, # ^ |   0 There's no transposing of the graph.
•  » » » » » » » 3 years ago, # ^ |   0 I did it that way! never mind..
 » 3 years ago, # |   +23 Last three problems were a little difficult for div3
 » 3 years ago, # |   +11 That was a lot of fun! Thanks vovuh
 » 3 years ago, # |   +4 What is wrong with test case 8 in D. Any strong test case?
 » 3 years ago, # |   0 how to solve E?
•  » » 3 years ago, # ^ |   0 I did it as follows : 1.)Mark all vertices that can be visited from s(by simple DFS). 2.)For rest of the vertices run DFS and count the number of nodes that can be visited by each of them.Sort according to the number of nodes visited by a particular vertex. 3.)Now run DFS from the last node in the sorted list and count the number of components left.
 » 3 years ago, # |   0 Was it only me who was facing problem to submit in the last 45 min?
 » 3 years ago, # |   +18 For E, I removed all vertices that are reachable from s (excluding s itself), and then found the condensation of the new graph. The number of SCC's with indegree 0 (excluding the possible SCC that contains s and has indegree 0) is the answer. Is there a simpler way to do it?
•  » » 3 years ago, # ^ |   0 Is this approach wrong? 1. Find out the topological sort of the graph 2. run dfs for given s mark all visited 3. In the order of the toposort, run dfs and count components. 4. answer is components-1.Btw, if u find anything wrong, u are free to hack!!
•  » » » 3 years ago, # ^ |   +2 What about cycles in graph ?
•  » » » » 3 years ago, # ^ |   0 I'm marking visited, so cycles won't be a problem. Provide a test case if u find anything fishy
•  » » » » » 3 years ago, # ^ |   0 I mean , how are you doing topological sort if the graph has cycles
•  » » » » » 3 years ago, # ^ |   0 which algo you are using for topological sort kahns or ... because kahns need atleast one vertice with indegree=0 in starting
•  » » » » » » 3 years ago, # ^ |   0 I'm marking visited, and then not visiting a vertex if its already visited. Cycles will be handled automatically I guess. Sorry that I'm not able to comprehend what u are trying to say, so u may look at the code:-999E
•  » » » » » » » 3 years ago, # ^ |   0 I had a similar idea. But I cannot convince myself that this approach works. Can you please help me?
•  » » » » » » » » 3 years ago, # ^ |   0 Topological sorting gives you an order of vertices along which if you run dfs, you will get connected components in a directed graph. Thereafter, the answer is simply numComponents — 1
•  » » 3 years ago, # ^ |   0 if you don't mind can you please elaborate this : "The number of SCC's with indegree 0(excluding the possible SCC that contains s and has indegree 0) is the answer"?
•  » » » 3 years ago, # ^ |   +9 Each vertex in the condensation graph corresponds to an SCC in the original graph. Look at the vertices in the condensation graph that have indegree 0: clearly they are not reachable from s. The other vertices, ones with indegree > 0 are reachable from some vertex with indegree 0. Therefore, we can add edges from s to the vertices with indegree 0, and then the entire graph is reachable from s.However, there is one corner case: when the vertex (in the condensation graph) containing s has indegree 0, we don't want to count it since a vertex is certainly reachable from itself. The second example input corresponds to this case.
•  » » » » 3 years ago, # ^ |   0 thanks for the reply !
•  » » » » 3 years ago, # ^ |   0 What about the case when all the SCC's(excluding the vertex s) form a cycle(i.e none of them have indegree 0) and the vertex s is disconnected from the whole graph ?
•  » » » » » 3 years ago, # ^ |   +5 In that case, the cycle will actually just be 1 SCC. And since s is not a part of the cycle, the answer will be 1.
•  » » » » » » 3 years ago, # ^ |   0 Yeah.. completely missed it :p
•  » » » » » 3 years ago, # ^ |   0 The new condensed graph where all each node represents an SCC is always a DAG.
•  » » 3 years ago, # ^ |   +8 Let a[i] be equal to 1, if we need edge (s, i) in optimal answer. Then instead of SCC after removing all nodes reachable from s, launch dfs from every non-used node v and assign a[i] to 0 for all reachable nodes from v. After that assign a[v] to 1. We can do it, because instead of any edge (s, i) we can place edge (s, v) if i is reachable from v.
•  » » 3 years ago, # ^ |   0 For every vertex count the number of vertices that can be visited from there. Use dfs from start and then you can iterate through every of these vertices in decreasing order and just use dfs once again.
•  » » 3 years ago, # ^ |   0 Can you please share your code ? I am not able to view your submission for problem E.
 » 3 years ago, # |   0 how to solve D ?
•  » » 3 years ago, # ^ |   +1 first put all the remainders with counts less than n/m in a set and then iterate on each index with value greater than n/m and for each of them find the closest element in the set and add the required value.
•  » » » 3 years ago, # ^ |   0 ohhh ... i did almost the same except that i puted every remainder with counts != n/m and hence it had greater also.
•  » » » 3 years ago, # ^ |   0 Can you please explain a little more what you did. What do you mean by "and for each of them find the closest element in the set and add the required value."
•  » » » » 3 years ago, # ^ |   +1 yes, sure. First put all the remainders with counts less than (n/m) into a set and then iterate over each remainder which have value greater than (n/m) (let's suppose we are currently at 'i') and notice one thing we have to only move forward so, the best we can do is to conver current 'i' to it's nearest remainder having value less than (n/m) and so just do a binary search for that and find that index.(set's lower_bound will help you). Now, it may happen that we are at 'i' and there are no index in range [i, m-1] having value less than (n/m) so, in that case we have to search for the same from front.Hope it helps!
•  » » » » » 3 years ago, # ^ |   0 Yes, Your comment made it very clear. Thank you :)
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Can you please tell me why we only move forward?EDIT : I got it that we can only add 1 every time. Thanks
•  » » » » » 3 years ago, # ^ |   0 Why should we convert "i" to the nearest remainder having value less than (n/m)? Can't we covert it to any remainder having value less than (n/m)?
•  » » » » » » 3 years ago, # ^ |   0 because it may happen that some of the remainders before it (nearer to the current one) has a value greater than (n/m) and so, if we convert that then we have to pay less.
•  » » » » » » » 3 years ago, # ^ |   0 Anyway, all remainders have to be filled equally. So if we convert "i" to its nearest one, then there may be some "j" which needs to travel farther and satisfy the next remainder. Else, if "i" already travelled farther and satisfied the second remainder, then "j" will just have to satisfy the nearest (first) encountered remainder. Both ways seem the same to me. Am I going wrong somewhere? If yes, please explain with a small counter case.
•  » » » » » » » » 3 years ago, # ^ |   0 you forget that we can only move right! let's aarray be 3 1 4 1 1 and we have to make all 2's.Then if we add 3's 1 to the 4th position (instead of nearest 2nd) then we have to take the 4's 1 to the 2nd position in which we have a total cost of (3 + 2 + 4) instead of the optimal cost which is (1 + 1 + 2).Hope it makes your doubt clear.
•  » » » 3 years ago, # ^ |   0 Did the same and got TLE in 4th test case. You can view my solution on my profile.
•  » » » 3 years ago, # ^ |   0 i thought abt it..but don't u thnk it's complexity will be O(n*n/4)??
•  » » » » 3 years ago, # ^ |   0 see there are atmost 'n — m' elements that are greater than n/m and similarly 'n-m' indexes are there which have less than value n/m. So, we are inserting 'n — m' elements and for each of 'n-m' element we are doing a binary search. so, O(NlogN)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 Consider every reminder c[i] a container that can hold at max n/m numbers. As you read the input you put a[i] in the container c[ a[i] % m ], if it's full: you put it in the next available container and add to a[i] the number of steps. To do it quickly the next available container is registered in another array.Let me know if that makes sense.EDIT: An array to store the next available container isn't good enough, a set is needed.
•  » » » 3 years ago, # ^ |   0 Hey there! I am also very stuck on this problem and your solution is not making sense to me. I have some questions, hope you will answer.-- If C[ a[] % m ] is full, how do you decide the next bucket in the container? Why do you add a[i] number of steps?-- At the end how do you track what the final array is?Thanks
•  » » » » 3 years ago, # ^ |   +1 This is the code if you couldn't find it 39498091.-I decide the next bucket by lower_bound(a[i] % m) in a set of buckets, every time a bucket is full I erase it-I add to a[i] the difference between the buckets, which is how many times I have to increase it-The final array is the original one that I changed every time
•  » » » » » 3 years ago, # ^ |   0 Thankss, alwerty u explained D in easy way :)
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks for the explanation
 » 3 years ago, # |   0 How to solve F?
•  » » 3 years ago, # ^ |   0 Consider any single number of card. Now the problem is 'For given N cards and M people, each person can have at most k cards. What is the maximum score?'
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 orange4glace, Sorry, I didn't get. Can you please elaborate more, what's the intuition behind solving problem F with an example?
•  » » » » 3 years ago, # ^ |   +2 Since h is strictly increasing, it is optimal to distribute as much as favorite cards to each peraon. eg. Let 3 people likes card 1 and each person has 2 cards. If number of card 1 is greater than or equal to 3×2, just distribute 2 cards for each and leftovers are 'dont care'(any other will have it and it has no effect to score) Else if the number of cards is less than 3×2, now the problem is distribute m cards to 3 people while maximum the score
•  » » » » » 3 years ago, # ^ |   0 Thanks, got it!
 » 3 years ago, # |   0 can anyone help me how to solve problem D????
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 Does anyone knows what is wrong with my solution(39488794) on 999E - Reachability from the Capital? :( The ideia i've used was to find all SCCs and make a new graph composed with those contracted SCCs. The next step was to add edges between the capital and the SCCs whose had vertex with lower degree.Thanks!
•  » » 3 years ago, # ^ |   0 Count SCC's with zero in degree (except the SCC's containing the capital city).
 » 3 years ago, # |   +38
 » 3 years ago, # |   0 Help on E appreciated, please let me know what's wrong with this approach (which fails pretest 4): Mark all vertices that are reachable from the capital (via DFS); For any vertices not reachable from the capital, count (via DFS) the number of child vertices that are still not reachable from the capital, and put them in a priority queue sorted in decreasing number of children; Greedily add an edge from the capital to the first vertex in the priority queue, and mark (via DFS) vertices that are now reachable from the capital, removing them from the priority queue; Repeat the previous step until the priority queue is empty. Thanks a lot for any insight!
•  » » 3 years ago, # ^ |   0 When you remove the first element of the priority queue along with all of its childs it is possible that you change the degrees of some of the vertices that are still going to stay in the queue.
•  » » 3 years ago, # ^ |   0 check this test 8 7 1 2 3 2 4 2 5 2 6 7 4 7 5 8 7 the answer is 2 in your approach the answer will be 3 as i think ,is it ? 
•  » » » 3 years ago, # ^ |   0 Please can you help me out to figure out the mistake. I have applied BFS for the given node s. After that I stored the index of the remaining indices in a vector called node. Then i again ran bfs on the this vector and mark the boolean vector the remaining one's with false are the answer Here is the link to solution-
 » 3 years ago, # |   +27 I don't think it's OK to have contests in which almost all participants solve the first X problems, but then only a small percentage of them solve the (X + 1)th problem. The difficulty distribution seemed a little off for this round.
•  » » 3 years ago, # ^ |   +1 As usual for Div.3 rounds
•  » » 3 years ago, # ^ |   +1 Totally agree. There are about 2000 participants (ranked ~#500-#2500) solved exactly 3 problems.
•  » » 3 years ago, # ^ |   0 I dont think its optimal but I dont think its unacceptable either.
 » 3 years ago, # | ← Rev. 2 →   0 Any miniature version of test 4 of E?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +18 This test is just a complete directed graph with a 71 vertices and n * (n — 1) edges.UPD: Woops, the fifth test was a complete graph. I was wrong. The fourth test is a just random directed graph with an 5000 vertices and 5000 edges.
•  » » » 3 years ago, # ^ |   0 vovuh Can you please tell will there be editorials for this round. They are not on home page.
•  » » » » 3 years ago, # ^ |   +2 The editorial will be available in few minutes =) Sorry for delay, i was on the exam today
 » 3 years ago, # |   +8 Can someone tell why 39491266 gives WA but 39491559 gives RE for problem D.I only changed all "int" to "long long".
•  » » 3 years ago, # ^ |   0 maybe something overflowed and when you took the remainder you got a negative value, which then caused you to look at a negative entry of an array?
 » 3 years ago, # | ← Rev. 2 →   0 I had been debugging my solution D(39490746) for half an hour. When the contest is over and I saw the test case, I realized the result is long long. So it(39494662)passed...
 » 3 years ago, # | ← Rev. 2 →   0 I rage quited after 3WA's in E and D After the contest I checked my E again and Saw this:""Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:92:12: runtime error: index 5000 out of bounds for type 'int [5000]' SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:92:12 in""I wish I would have checked my array sizes rather than rage quieting cf after 3WA's and also wish codeforces will give RTE verdict rather than WA for these :pNice Problems Overall :D
 » 3 years ago, # |   -10 Contest was not beautiful as its id.
 » 3 years ago, # |   -8 How MYTH_vs_REALiTY solved all tasks in an hour ?
•  » » 3 years ago, # ^ |   0 His code looks different from his usual code.
•  » » » 3 years ago, # ^ |   0 Yes totally and unless having that template gives a coder magic powers I think something is fishy.
•  » » » 3 years ago, # ^ |   +1 Same is the case with BigDelta
 » 3 years ago, # |   0 So, this was my first contest on Codeforces and I can't seem to find any ROOM link on the top menu bar nor can I find a way to lock my submissions so that I can participate in hacking. Do first time users don't have this privilege of hacking or am I missing something?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 This is Div.3 Round. after the round it will be a 12-hour phase of open hacks-there isn't hacks during the round.
•  » » » 3 years ago, # ^ |   0 Isn't the round already over?
•  » » 3 years ago, # ^ |   0 same here i cant find my room, if anyone can help us
•  » » » 3 years ago, # ^ |   0 Its open hacking. You can hack anyone's solution.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 k
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 There isn't any rooms. Rooms are needed in rounds with hacking during them. There is such thing as CF predictor: expected results of this round
 » 3 years ago, # |   +6 Thank vovuh for your contest, it was more difficult than last div 3 round.
•  » » 3 years ago, # ^ |   +2 Funny, it seemed simpler to me! BTW, I found the last div 3 round more difficult than some div 2 (not that I have much experience, however)
 » 3 years ago, # |   0 I solved only 4 problems and its my first constest, my rank will go up or down?
•  » » 3 years ago, # ^ |   +2 try this cf rating change predictor
 » 3 years ago, # |   0 Why My code for D getting runtime error on test 8 ?
•  » » 3 years ago, # ^ |   0 Probably because of the "matrix index out of range"
 » 3 years ago, # |   +1 In problem D i used a queue to store the number remainders . If the size of the remainders > n/m then we move one by one to the next container with the value (previous + 1). And keep doing that until everything is equal to n/m (only 1 needed 1 for) and traces and etc, why am i getting TLE ? and how can i fix this or maybe another approach ? Code : https://ideone.com/Z6Y8I5
•  » » 3 years ago, # ^ |   0 It seems to me like you have nested for loops. Oouter loops iterates until m and inner loop iterates until trace[i], which (at least at first glance) seems like it could be O(n). So overall complexity would be O(n^2)?
•  » » » 3 years ago, # ^ |   +1 ah okay i think i get it, so is there anyway to optimize it because i cant find a way to trace the answer
•  » » » » 3 years ago, # ^ |   +5 You can use something like dsu (I don't know the name for this technique) so every remainder >= n/m won't be visited againhttp://codeforces.com/contest/999/submission/39476990
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Correct me if I am wrong but I think your solution has quadratic complexity as well. If n = m, then the only stop condition of your cari function is that val[x] is 0. So For a case like: 200000 200000 200000 199999 199998 199997 ... When processing the first number you'll take 1 step, when processing the 2nd number you'll take 2 steps etc. So overalall you'll take N*(N+1)/2 steps.
•  » » » » » » 3 years ago, # ^ |   +3 Isn't the answer for that tc is 0 change? My val[x] is only incremented after I found the valid position for current number, so cari will only be called once for each number (Because val[x] is still 0)
•  » » » » » » » 3 years ago, # ^ |   0 Sorry, I didn't notice you actually modify the nex array (also the test I wanted to type was an array full of zeroes, but it doesn't matter anyway).
•  » » » » » 3 years ago, # ^ |   0 Nice technique bro thanks, i finally understand your code!
 » 3 years ago, # |   0 can someone help me to find out why the first solution was not accepted but second got accepted for problem Bhttp://codeforces.com/contest/999/submission/39483346http://codeforces.com/contest/999/submission/39486399
•  » » 3 years ago, # ^ |   0 It is not advisable to insert characters in C++ string like this s[i]=ch. You are allowed to do this in character array string.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Really? So... how did you do it in your solution?Are both of you joking?Maybe I miss something but...isn't the problem with s1[r--] operation? These parts of code aren't the same, of course: s1[r--]=s[i]; compare with s1[r] = s[i]; r--; Doing something with s1[-1] and s1[0] aren't the same.
•  » » » » 3 years ago, # ^ |   0 changing s1[r--]=s[i] to s1[r]=s[i] doesn't make any difference. Still runtime error in testcase 8.
•  » » » » » 3 years ago, # ^ |   0 Oh, sorry. I was a little tired yesterday. aditya10 is right. Little more: string is an object. When you initialise "string s1;" constructor make it s1 = "". So, when you write "s1[r] = s[i]" you just change the element with address s.begin() + r (not s1). And... we don't no, what the rubbish is there. When you are trying to change it, you can get an error.When you print the s1 itself (cout << s1), you see that it doesn't change. s1 = "".So...just initialize "s1 = s;". Now it has got the same number of elements as s, and all will be ok.
•  » » » » 3 years ago, # ^ |   0 Doing s1[r--]=s[i]; and s1[r]=s[i];r--; are actually same. In post decrement value is decremented after being initialized.
 » 3 years ago, # |   0 Regarding question DI wrote the code using lower_bound(st.begin(), st.end(), t) and got TLE but when i wrote the same code using st.lower_bound(t) it got AC. Why this happened???
•  » » 3 years ago, # ^ |   +9
 » 3 years ago, # |   +1 A, B, C was too easy and C, D, E was too hard. So the standings will probably depend on penalties.
•  » » 3 years ago, # ^ |   0 ""A, B, C was too easy and C, D, E"" i geuss you meant F D E and thats actually true , they are harder than most B's in div 2
 » 3 years ago, # |   0 I just realized I really need to practice to be a better coder.. I got the idea of d but struggled alot coding it and didn't have the time to solve it because of some annoying coding mistakes :(
 » 3 years ago, # |   0 Why my solution for problem C is exceeding the time limit in testcase#5 despite having linear complexity? here is the link: http://codeforces.com/contest/999/submission/39496135
•  » » 3 years ago, # ^ |   +1 I assume that anss=s[n-1-i]+anss; may be O(N).
•  » » 3 years ago, # ^ |   +4 Because it doesn't have linear complexity :)The + operator for strings (from line anss=s[n-1-i]+anss;) is not constant time, but linear (see documentation). Considering the outer for loop as well, it results in quadratic time complexity.
•  » » » 3 years ago, # ^ |   0 Thank you. I overlooked it :(
 » 3 years ago, # |   0 Can someone explain the first test case of Problem B? In the above statements, it say in decreasing order. I try to implement the algorithm but got different results on test case 1 and 2.
•  » » 3 years ago, # ^ |   0 the task is to decrypt, the problem description algorithm is to encrypt
•  » » 3 years ago, # ^ |   0 Actually you are given the resultant string in the input,and you need to find the original string from where it is transformed. So basically you have to do "rocesfedoc" --> "rocesfedoc" --> "orcesfedoc" --> "secrofedoc" --> "codeforces". Opposite of what is explained. So most probably you are sorting the divisor array in descending order, sort it in ascending order,you will get correct answer unless your code is correct for reversing the string.
 » 3 years ago, # |   +1 Hello! Can someone help me with Problem D? I saw the comment, but I do not understand it. Will appreciate if someone can explain the idea and how you reached it.For Problem D, I did a BFS from the initial array until one array suceeds. This I feel is correct, but I had a memory limit exceeded within test 5.Thanks
 » 3 years ago, # |   0 Hack for Problem C?
 » 3 years ago, # |   0 Can D be solved using two pointers ?
•  » » 3 years ago, # ^ |   +1 I think its possible if you first sort the entries of the array in increasing value of the remainder mod m.
 » 3 years ago, # |   0 What is the effect on rating after hacking others solution in this round?
•  » » 3 years ago, # ^ |   +1 Hacking that take place after contest have no effect on rank (for hacker). So no effect on rating.
 » 3 years ago, # |   +3 can someone explain the idea of F?
•  » » 3 years ago, # ^ |   0 For a fixed type of cards you have x cards and c players that them likes this type, so compute the dp[i][j](maximum value that you can get) where i is the number of remaining players and j is the number of remaining cards initially dp[c][x]=0 and the answer will be in dp[0][0..x] I leave the link to my solution for a better understand of this idea: 39504913
 » 3 years ago, # |   0 Thanks for conducting another div3 round!!
 » 3 years ago, # |   0 Can someone explain question F to me? I've read it thrice but I do not understand.
 » 3 years ago, # | ← Rev. 2 →   0 My solution for D: 39490456.I believe my answer is just a permutation of the correct answer ( 4 2 1 6 11 12 ). Should this not get accepted considering any array satisfying the required condition is correct?
•  » » 3 years ago, # ^ |   0 The only operation you can do is incrementing an array element, changing order is not allowed.
•  » » » 3 years ago, # ^ |   0 Alright. Thank you so very much.
 » 3 years ago, # | ← Rev. 2 →   0 vovuh please check my submission for B it is not showing output on codeforces while the same is giving correct answer in my ide. This took my 40 mins. here is the code-!! :( Anyone having idea of this? Thanks for your insight!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 You can't use scanf/printf with ios_base::sync_with_stdio(false); You can read this blog (look for comments)
•  » » » 3 years ago, # ^ |   +1 Thank You! :)
•  » » » 3 years ago, # ^ |   +4 Actually, that's only half true. What you shouldn't do is MIXING either scanf/cin or printf/cout in the same code (since different streams aren't synchronized, there's no guarantee what will be read or written first). Otherwise, using only one from each pair is usually safe.
•  » » » » 3 years ago, # ^ |   0 U mean scanf and cout or printf and cin? Right?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Yes, no problem with those.
 » 3 years ago, # |   +33 Problems A, B, C vs problems D, E, F
•  » » 3 years ago, # ^ |   +6 But really why was it like this? 100 participants with a full mark and almost all others with only three questions... Then the one who just codes faster, gets a better result. Is it a marathon or a contest???
 » 3 years ago, # |   0 Newbie here! Can anyone explain why I got TLE on problem C?? Problem C submission
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 The time complexity of your solution is O(n^3). It can be solved with much better time complexity. Link : My solution
 » 3 years ago, # | ← Rev. 3 →   0 My solution for D: http://codeforces.com/contest/999/submission/39505442. I think it's O(n) ?
•  » » 3 years ago, # ^ |   0 can you please explain your approach?
•  » » 3 years ago, # ^ |   0 Last two for loops where each runs m times, contain a while loop. Can you explain how its complexity is still O(max(n,m)).
•  » » » 3 years ago, # ^ |   0 each for loop runs m times, each while loop runs maximum n / m times => I think total complexity is O(m * n / m) = O(n) ?
•  » » » » 3 years ago, # ^ |   0 If we look at while loop independently, it will run the number of times equal to number of elements not "in place". So say all elements have same reminder, the while loop might run, roughly speaking, O(n*n/2) times. Still I am not sure, what do you think about it?
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   0 int d = n / m;int need = d — v[i].size();=> need <= d => need <= n / mwhile(need--) => each while loop runs atmost need times or n / m times.
•  » » » » » » 3 years ago, # ^ |   0 Okay thanks. I got it now.
 » 3 years ago, # |   0 where i can find editorials/solution of the contest?
 » 3 years ago, # |   +3 Can anyone figure out the mistake in this solution for E? LINKFor tc #4, it is computing 1818 as the answer instead of 1817.Approach : Run a dfs from source and mark all reachable nodes. Now, run a dfs from every unreachable node and mark all the ones that are being traversed from some parent. Suppose, we're running dfs from 2, we will mark every node reachable from 2 as visited, but we'll keep 2 as unvisited. This way, we will know the nodes(and components) which require a path from source.
•  » » 3 years ago, # ^ |   +3 What if while running the second DFS you reach a node marked by the first DFS. What do you do?
•  » » » 3 years ago, # ^ |   +3 I'm ignoring it, because the nodes which can be reached from this node would've already been marked.
•  » » » 3 years ago, # ^ |   +2 I am facing the same problem. And does it matter that after running second dfs if we come across the visited nodes from the first dfs,as they are already visited and reachable from s.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +2 Check for this test case 5 4 5 1 2 2 3 3 1 4 3Correct Output: 1
•  » » » 3 years ago, # ^ |   0 Thanks for that.
 » 3 years ago, # | ← Rev. 2 →   0 Why is this http://codeforces.com/contest/999/submission/39505722 submission of mine for A giving WA on this case: 6 6 7 1 1 1 1 1 The answer is actually 5, but in cf it is showing 4. But in ideone compiler it is giving right answer. Link: https://ideone.com/je07LC
•  » » 3 years ago, # ^ |   +1 The pos variable is uninitialized, causing ambiguous results.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/contest/999/submission/39470600 Mine is also giving a WA on 23. I have initialized correctly I guess.
•  » » » 3 years ago, # ^ |   +1 Your code did not check if start and last are out of bounds.
•  » » » » 3 years ago, # ^ |   0 Okay. Thanks
•  » » » 3 years ago, # ^ |   +2 When all elements have values less than k, value "start" is equals n, n+1, ... , because you are have a rubbish in anon[n,∞).
 » 3 years ago, # |   0 why rating is not updated yet?
 » 3 years ago, # |   +1 did all the testcases are run or some testcases are yet to be judged during system testing
 » 3 years ago, # |   +5 Is the system testing done? If not, when?
•  » » 3 years ago, # ^ |   0 I want know this,too
•  » » 3 years ago, # ^ |   0 This is the only question after every round in acpc format at codeforces..
 » 3 years ago, # |   0 Can't believe that i have solved 5 problems!
 » 3 years ago, # |   +11 For some reason 999F reminds me of game theory/mechanism design about auctions, when I first look at the joy level constraint I thought "oh this is a gross substitute valuation" instead of "oh it's strictly increasing"... Weird.
 » 3 years ago, # |   0 System testing has started now.
 » 3 years ago, # | ← Rev. 5 →   -7 .
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 You are not checking for (start
•  » » » 3 years ago, # ^ |   0 Yeah I got it now. Silly me -_- Thanks for replying.
 » 3 years ago, # |   +2 It would be great if someone can put editorial's link here. Thanks in advance.
 » 3 years ago, # |   0 I got TLE in Java for problem C and I got very confused about my logic. But then I researched a little more and I wrote this for Java programmers:https://letsdocp.wordpress.com/2018/06/22/java-in-competitive-programming/
 » 3 years ago, # |   0 I am getting MLE in problem-D test-5 here. I have made vector and map of linear order.Anyone help ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 I guess vectors do not release memory after popping up the elements. I used stack in your code hereinstead of vector and it shows TLE. The underlying approach is wrong.
 » 3 years ago, # |   +2 all those who got stuck on test 4 of problem E can try this test case no 47: 8 8 1 3 2 3 4 4 5 5 3 6 4 6 7 7 8 8 6 ans:1 you might be getting 2...
 » 3 years ago, # | ← Rev. 2 →   0 UPD: I got the mistakeIn E, for test case 20, I get answer as 11, whereas the solution ans is 12. I even added the edges and put asserts to check that every node is indeed reachable from s, however I did not get any assert failures. Someone please point out what's going wrong with my solution, thanks! 39515068
•  » » 3 years ago, # ^ |   0 i think you were first doing dfs of capital node and then for every non visited node ,finding all other nodes from where you can reach to that node ,by backtracking the reverse adjacent vector and doing dfs on all back nodes....
•  » » » 3 years ago, # ^ |   0 I'm not sure about that. The mistake here was I added edges as bidirectional from input, but it actually has way more issues :P
•  » » 3 years ago, # ^ |   0 How to solve E?
•  » » » 3 years ago, # ^ |   0 First check for every vertex 'a' how much vertices can go to 'a'. Then sort vertexes by sizes of groups. Notice that for every group you only need to add one road for all vertices in group to be connected to root. Iterate groups from biggest to lowest, check if road exist before you add one. If you add one road, notice that you made all vertices that belongs to the group connect to root. If they are connected, you shouldn't build roads because they're already connected.
•  » » » 3 years ago, # ^ |   0 If you have for example root: 1 2->3 2->1 4->3 First sort groups (3 will be first, then 1 and 4)You add one road (3->1) and then 4 becomes connected. Next up is 4, but 4 is connected trough 3 so we move on. Next up is 2, but 2 is also connected to root.
 » 3 years ago, # |   0 I need help, even though my solution for test 1 was right, it gives WA on problem D. Here's the submission. Mine code outputs: 3 0 2 3 8 10 13 their answer: 3 0 2 3 7 10 14
•  » » 3 years ago, # ^ |   +3 Input: 6 3 3 2 0 6 10 12 Your Answer: 3 13 8 0 3 10 2 You can just increase elements by 1, you can't change the order.
 » 3 years ago, # |   0 I am getting WA at test# 4.I tried Solving E: 1. Did the DFS on s, marked nodes visited. 2. initialized c = 0(counter: for counting connected components in Graph), then started running DFS on every node except S, forwardly(means when in the edges direction) and then took a step backwards(means run the loop to iterate over all the node which is pointing towards current node, for, eg, if 2 is current node and there is an edge 4->2, then I went back to 4.) and obviously marked the nodes visited. 3. then counted all the connected components.here is my link: http://codeforces.com/contest/999/submission/39517716Actually, my idea was simply to have the no of connected components fo graph. can someone please point out the mistake??
•  » » 3 years ago, # ^ |   +1 Your Solution Will have no of Connected Components in Undirected Graph But in The Problem The Graph is Directed.
•  » » » 3 years ago, # ^ |   0 can you give me an example?
•  » » » » 3 years ago, # ^ |   0 Try This Example 8 7 1 2 3 2 4 2 5 2 6 7 4 7 5 8 7 The Output is 2 But Your Code Prints 1 , Because Graph is Directed But Your Implementation is to find number of connecting Components in Undirected Graph.
•  » » » » » 3 years ago, # ^ |   0 Thanks for the help!!!
•  » » » » » » 3 years ago, # ^ |   0 I just couldn't understand this at all!! that why on test case 2's last line "4 1" my code is giving runtime error, and if u change it to like "5 1", it will give the answer, I couldn't understand why?This is the link http://codeforces.com/contest/999/submission/39538352
•  » » » » » » » 3 years ago, # ^ |   0 There's Problem in dfs1 It doesn't Stop.I think Problem is in that Line if(vis[node[s1[i]]!=s&& vis[node[s1][i]]!=s1) 
•  » » » » » » » » 3 years ago, # ^ |   0 No, I checked that problem was in Line "node[x].pb(y);" because after that it's not printing "----" and this only arouses in "4 1" case.
•  » » » » » 3 years ago, # ^ |   0 how this example is giving output 3 in my code?? can u explain?? http://codeforces.com/contest/999/submission/39526515
•  » » » » » » 3 years ago, # ^ |   0 Could You Explain to me The Idea of Your Code ?
•  » » » » » » » 3 years ago, # ^ |   0 Actually the idea was wrong but thnx really for helping out!!
 » 3 years ago, # |   0 Your crafting.oj.uz ratings are updated, check it right now :)
 » 3 years ago, # |   +8 Since the system testing is done and my solution for E passed the tests,though i still don't know if its correct.My solution:Find all the cities not reachable from capital and add a directed edge from capital to it.Now for all newly added edges just remove that edge and check if its possible to reach all cities from capital.If yes, then just remove that edge and continue checking for other edges,else add that edge back and continue checking.I don't know how to prove that this gives the optimal answer.Can someone prove it or give some counter test for this?