### Vovuh's blog

By Vovuh, history, 4 months ago, translation, ,

<almost-copy-pasted-part>

Hello! Codeforces Round #565 (Div. 3) will start at Jun/09/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) 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 (or 8) 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.

</almost-copy-pasted-part>

UPD1: Big thanks to Um_nik, Rudy358, nigus, opukittpceno_hhr and Temotoloraia for testing the round! And also big thanks to my dear friends Ivan BledDest Androsov, Roman Roms Glazov and Mikhail PikMike Piklyaev for help with round preparation!

UPD2: Editorial is published!

UPD3:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Yushen 6 235
2 Violet_user 6 293
3 BudiArb 6 345
4 xenoframium 6 350
5 njchung93 6 439

Congratulations to the best hackers:

Rank Competitor Hack Count
1 nikolapesic2802 69:-15
2 stefdasca 42:-11
3 dorijanlendvaj 15:-11
4 orz_liuwei 10:-11
5 interestingLSY 5:-1
170 successful hacks and 236 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A riz_1_ 0:02
B _ekaterina_dudina 0:04
C BudiArb 0:05
D hxylalala 0:18
E csts.21 0:17
F njchung93 0:32

• +146

 » 4 months ago, # | ← Rev. 2 →   -51 So many contests in the previous week feel like.
 » 4 months ago, # |   -11 It will be a great contest... Best of Luck to all...
•  » » 4 months ago, # ^ |   0 thanks, man
 » 4 months ago, # |   +14 Div3 Contest == Vovuh
•  » » 4 months ago, # ^ |   +10 What a nice person!
•  » » 4 months ago, # ^ |   0 Vovuh = great contest <3
 » 4 months ago, # |   -44 ITS INDIA VS AUSTRALIA IN THE CRICKET WORLD CUP ....#TIMECLASH
•  » » 4 months ago, # ^ |   -11 So don't give contest
•  » » » 4 months ago, # ^ |   +8 kam boll thoda
•  » » » » 4 months ago, # ^ |   +7 oh my god , khud tourist ke papa ji ne apne unrated account se reply kiya hai , main to dhanya ho gaya
•  » » 4 months ago, # ^ |   -6 Contest > Cricket
 » 4 months ago, # |   -15 I think that "copy-pasted part" is just a dead meme, let it go
•  » » 4 months ago, # ^ |   +18 No! It's a tradition! It will forever be there!
 » 4 months ago, # |   -48
 » 4 months ago, # |   +35 Let me think :$Div.3 \Leftarrow \Rightarrow Div.(1+2)$so why not rated for someone whose rating is more than 1600
•  » » 4 months ago, # ^ |   +79 mathematics 100
•  » » 4 months ago, # ^ |   +36 Let me rethink : $Div.2 \Leftarrow \Rightarrow Div.(1 + 1)$so why not rated for someone whose rating is more than 2100
•  » » » 4 months ago, # ^ |   +59 mathematics 2100
•  » » » 4 months ago, # ^ |   +47 A further thinking: $Div.2 \Leftarrow \Rightarrow Div.(3-1)$so why not rated for someone whose rating is more than 1600 and less than 1900
•  » » » 4 months ago, # ^ |   +2 Div.3 participants are very luckyDiv.3 ⇐⇒ Div.(2 + 3)Also can take a part in Div.2 contests
•  » » » » 4 months ago, # ^ |   +117 luckydiv. 3it is like saying "paralympians are lucky because they can participate at paralympiads"
•  » » » » » 4 months ago, # ^ |   0 haha, awesome! U've made my day... But still I'm sure some users will feel offended.
•  » » 4 months ago, # ^ |   0 the next prepare many DIVs for you,the div3 is for the rating lower than 1600
•  » » 4 months ago, # ^ |   +9 The trick is to get lucky, this is the second time I fall from expert to specialist and the next round is DIV3.
•  » » 4 months ago, # ^ |   0 haha
 » 4 months ago, # |   0 cheer up
 » 4 months ago, # |   0 I hope my Rating will UPUP!
 » 4 months ago, # |   0 Wish everyone have fun!
 » 4 months ago, # |   0 Cool!
 » 4 months ago, # |   +9 I just want to say I appreciate the Slay the Spire problem.
 » 4 months ago, # |   +1 What is the solution for F? I can't understand why my dp solution didn't work. I had dp[i][j] that means maximum cost for the first i rounds if the count of the total cards we use is j modulo 10.
•  » » 4 months ago, # ^ |   0 I had the same idea and it got AC https://ideone.com/rRrMmW
•  » » » 4 months ago, # ^ |   0 Well I still don't get it my solution is wrong. I almost did the same things as you. Can someone please check my code?
•  » » » » 4 months ago, # ^ |   +1 I think the cause of the problem is this code: int t; if (j % 10 != 0) t = 1; else t = 2; Check, for example, this test case: 4 3 1 1 1 1 1 1 3 1 1 1 1 1 1 3 1 1 1 1 1 1 3 1 1 1 1 1 1 The answer is 13 while you program prints 12
•  » » » » » 4 months ago, # ^ |   +3 Ah, shit. Thanks for you help, the problem was the case when new 10'th is created. Now I fixed it T_T
•  » » 4 months ago, # ^ |   0 My solution had the same idea also and it fails on testcase 2. Did you take into consideration that you can reorder the cards of each round however you want?
•  » » 4 months ago, # ^ |   0 I've got accepted with this idea. int dp[2][10]; /// cur/prev, cards count modulo => max damage 55365600
•  » » 4 months ago, # ^ |   +8 This is the solution for F, maybe you made mistake in considering the different cases. Choose only one three cost card (if exists) Choose one two cost card and one, one cost card (if exists) Choose one two cost card (if exists) Choose 1-3, one cost card (if exist) Choose no card.
•  » » » 4 months ago, # ^ | ← Rev. 4 →   +3 Instead of considering multiple cases we can do the following: Store at most three cards that give most damage for each cost Iterate through all possible combinations of amounts of cards for each cost. So we can take $(0,1,2,3)$ of cost $1$, $(0,1,2,3)$ of cost $2$ and $(0,1,2,3)$ of cost $3$. In total $4^3 = 64$ possible combinations (not of them are valid, of course, but we can check it manually for each combination) For each combination check that total cost of all taken cards is less than $3$ List all damages of taken cards in common list and sort it Now we can easily get the amount of damages with doubled card and without doubled card and update our DP with these results
 » 4 months ago, # | ← Rev. 2 →   0 Why is this TLE? TLE
•  » » 4 months ago, # ^ |   0 Hmmm... Maybe the problem in your bfs, exactly too many q.push()
•  » » 4 months ago, # ^ |   +12 There can be up to $2*10^5$ test cases in the problem with graph containing only one edge (1, 2). Your solution creates so many arrays of size $2*10^5$ each, and it leads to quadratic complexity of the solution. Replace all arrays with vectors of size $n$ instead of $2*10^5$.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Same happened with me. But Vovuh I have declared a global array fo all test cases. Why does this give TLE? Shouldn't the memory allocation be just once for all test cases as I have used a global adjacency list??55377706
•  » » » » 4 months ago, # ^ |   +12 In your case the problem is in the adjacency lists. Where do you clear them between test cases? I think your bfs works too long overall. I don't know how it passed the first test lol.
•  » » » » » 4 months ago, # ^ |   0 Gotcha
 » 4 months ago, # |   0 I was completely surprised by how hard these Div3 tasks were..
•  » » 4 months ago, # ^ |   0 I dont know. As for me, it was not too hard. A,B — quite standard problems. C — binary search, D — Sieve of Eratosthenes, E — vertex paint. But maybe i'm wrong
•  » » » 4 months ago, # ^ |   +2 C can be solved in O(n).
•  » » » » 4 months ago, # ^ |   +1 How?
•  » » » » » 4 months ago, # ^ |   +4 https://codeforces.com/contest/1176/submission/55341035There's absolutely no need for O(logN) complexity when the constraints are within O(NlogN) bounds.
•  » » » » 4 months ago, # ^ |   0 C can be solved in O(n). It's seems pretty easy. See my submission---! ! ! ! ! ! 55354250
•  » » » » » 4 months ago, # ^ |   0 n*logn
•  » » » » » » 4 months ago, # ^ |   0 No. It's O(n) . No need to consider log(n) for map . You can also take 6 variable for count insted of map.
•  » » » » » 4 months ago, # ^ |   0 hey can u plz explain your logic I see your code but I didn't get it...plz!!! thanks.
•  » » » 4 months ago, # ^ |   0
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   -10 > O(n)Uses std::map
•  » » » » » 4 months ago, # ^ |   0 you can replace it with a vector with 6 elementsi also forgot that i was using a map :D
•  » » » » » 4 months ago, # ^ |   +19 It's still O(n).
•  » » » 4 months ago, # ^ |   0 You're not wrong at all, its my fault that I didn't get these, but the fact that on the previous Div2 contest I got ABC and I couldn't even get Div3 B now is stupid from me. Looking at the solutions, the solutions are pretty clear, but they didn't seem pretty clear to me when I was trying to create one by myself. I'm just venting because I've tried really hard to come up with a solution but I couldn't do it because of simple restrictions in the problems that I just couldn't overcome.
•  » » » » 4 months ago, # ^ |   +1 Dont worry, just keep training
 » 4 months ago, # |   +5 Can you hack my randomized solution for E? 55348371
 » 4 months ago, # |   0 I was not able to solve a single problem in this contest. Any direction to improve this. I was stuck in question number one itself for more than 1.30 hrs. in the last minute I got a correct solution for the test cases but forgot how to take input from multiple newline. Any direction would be helpful.
•  » » 4 months ago, # ^ |   +1 Whats number of the taks?
•  » » » 4 months ago, # ^ |   0 Sorry I don't know what you want to say?
•  » » 4 months ago, # ^ |   +2 The best and straightforward answer is just solve more problems. I've started CF 2-3 months ago, and I'm better now than I was then purely because I've simply solved more problems.I managed to only solve A in this contest when I usually do ABC in Div3, but that attributes to me mostly not solving enough problems that are similar to this.All other advice pale in reference to the first I provided you, but its also nice to know that Div3 ABC and Div2 ABC can almost always be solved greedily (they just require implementation/data structures and not complex algorithms like graphs or dynamical programming).
•  » » » 4 months ago, # ^ |   0 Is there any way to add you as a friend? @Scofield11
•  » » » » 4 months ago, # ^ |   0 You click a star next to a person's nickname when you visit their profile.
•  » » » » » 4 months ago, # ^ |   0 Thanks.
•  » » » » » 4 months ago, # ^ |   0 May I know which one is the easier. Div3 , Div2 or Div1
•  » » » » » » 4 months ago, # ^ |   0 Div 1 > Div2 > Div3From hardest to easiest.You can view previous contests on CF and solve the problems, you can't participate in Div1 contests unless you have high rating.
•  » » » » » » » 4 months ago, # ^ |   0 Thanks I thought Div1 was the easiest one and Div3 was the hardest. Thanks for clarifying.
•  » » 4 months ago, # ^ |   0 In fact, A was not as easy as it should be. I solved it by trying in which order the three operations should be applied. But I still dont know why the one I finally submitted works, and others do not. B was less problem for me than A. As a suggestion, try to keep calm if it does not work out as expected.
•  » » » 4 months ago, # ^ |   0 hey just simply see that, for first one it makes a number (0.5)*n the second one make (0.667)*n and the third one makes (0.8)*n so clearly the first one makes the number smaller faster than the other two. So definitely go for 1 then 2 then 3.
•  » » » 4 months ago, # ^ |   0 I was shocked by how apparently hard A was, because I thought that I'd need dp to solve it because I wasn't sure what operation (if any) had a priority over the other.Took me a while to realize that its an A problem, there's definitely not going to be any dp, and I just should just write it down as it is, and I was right.
•  » » 4 months ago, # ^ |   0 Change ur dp first. Keep something inspirational.
 » 4 months ago, # | ← Rev. 2 →   +1 How do I delete a comment
•  » » 4 months ago, # ^ |   +1 You can't delete your comment after two minutes.
 » 4 months ago, # | ← Rev. 2 →   0 Why is this approach wrong for the problem E:For every edge, if a vertex is not taken and is not visited by a previously taken vertex then I will take this vertex. Any sample case to prove that I might take more than n/2 vertices.
•  » » 4 months ago, # ^ |   +5 Example from PikMike: PictureIf you'll start coloring from the vertex $5$, you cannot take less than $3$ vertices to cover all vertices (vertices can be reordered so the vertex $5$ will be vertex $1$ or something like this).
•  » » 4 months ago, # ^ |   +2 Consider a chain of length 3. If you start from one end, you will need to color 2 vertices which is more than 1.
•  » » » 4 months ago, # ^ |   0 If both nodes are unvisited I was taking one with a greater degree so this case was being covered but the example from vovuh is what I was missing.
•  » » 4 months ago, # ^ |   0 maybe smth like 1 -- 2 -- 3 -- 4 -- 5, you get 1,3 and 5?
 » 4 months ago, # |   +1 getting runtime error in problem D but working fine on local ide.
 » 4 months ago, # | ← Rev. 2 →   +2 For D, you need to sort the array and then look at the largest number, say L. If its kth prime, then L can't be part of original array, so we add k as one of the elements of original array. We remove L and k after this from array and repeat. If L were composite, then it definitely gets added to original array and we remove L and its highest divisor from the array. The highest divisor can be found easily if you store for every number what is the smallest prime that divides it. Use seive smartly.
•  » » 4 months ago, # ^ |   0 Thank u very much!
 » 4 months ago, # |   +12 For E, just color the graph with alternating white and black colors. I know it may not be bipartite but its okay. Then if white nodes are more than N/2, we chose black nodes.
•  » » 4 months ago, # ^ |   0 I am getting a runtime error in Problem E. Can someone help fixing it. Link to Code
•  » » » 4 months ago, # ^ |   0 Logic: I do a BFS starting from the node having largest degree and proceed to add nodes in the answer which are present at odd levels with respect to the root.
•  » » 4 months ago, # ^ |   0 https://codeforces.com/contest/1176/submission/55374222 i have done the same !! why it giving me tle ?
•  » » » 4 months ago, # ^ |   0 Memset color giving u tle, because if there are 2 nodes and 10^5 test cases that gives u 10^10, u need to clear color just size of n, also clear graph size of n
•  » » » » 4 months ago, # ^ |   0 thanks buddy for helping me!! i change that and it got ACCEPTED!!! thanks
•  » » 4 months ago, # ^ |   +3 Sir, I love your videos regarding competitive programming and always get motivated
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 We can find the distance of all nodes from root(1). (using simple DFS)Then we can select even or odd distance nodes which fulfill ( N/2 — condition) .
 » 4 months ago, # |   0 What is wrong with this approach for E : I will consider all the nodes which has only 1 adjacent node and take that one adjacent node into the answer set(not the node which has only 1 adjacent node).Then go for the the existing nodes one by one and if not adjacent to any node that i picked already I will take that too.
 » 4 months ago, # |   0 Testcase 6 in problem C ?
•  » » 4 months ago, # ^ |   0 May be smth like this: 12 4 8 15 16 23 42 4 8 15 16 23 42
•  » » » 4 months ago, # ^ |   0 My code is showing answer as 1.
•  » » » 4 months ago, # ^ |   0 12 is not possible as an array element I think?
•  » » » » 4 months ago, # ^ |   0 12 is the value of n.
•  » » 4 months ago, # ^ |   0 Did you interpret meaning of subsequence right? I thought it might be an error.
•  » » » 4 months ago, # ^ |   0 https://codeforces.com/contest/1176/submission/55357081 please check my code.
•  » » » » 4 months ago, # ^ |   0 I think those break statements messed it up a bit, instead incrementing index was better choice, what do you say?
 » 4 months ago, # |   -8 Number theory and Graph theory? it seems really difficult for div3
•  » » 4 months ago, # ^ |   0 actually you can solve first 3 problems w\o any algo and its cool, when in div2 in problem C can be some algo
 » 4 months ago, # |   0 why it gives tle in E ? https://codeforces.com/contest/1176/submission/55374222
 » 4 months ago, # | ← Rev. 2 →   0 Can anyone tell why I am getting TLE in Problem C at TC:7 https://codeforces.com/contest/1176/submission/55371060
•  » » 4 months ago, # ^ |   0 maybe due to the use of remove function. I was doing the same at first attempt .
•  » » » 4 months ago, # ^ |   0 Got it!. Thanks
•  » » » » 4 months ago, # ^ |   0 A little tip for you, if you're going to remove elements from a vector or some other array in a for loop, don't use a static variable like m. For example if you plan to remove several elements from a vector $ARR$ of size $M$, your for loop shouldn't be: $for(int$ $i=0;i •  » » » » » 4 months ago, # ^ | 0 It won't work here.  » 4 months ago, # | ← Rev. 2 → 0 What is wrong with this solution 55346608 of B? •  » » 4 months ago, # ^ | +3 rem[1] -= min(rem[1],rem[2]); rem[2] -= min(rem[1],rem[2]);when you subtract from rem [1], the result increases as the already subtracted rem [1] is subtracted from rem [2] •  » » 4 months ago, # ^ | +3 You are changing the value of res[1] before calculating min(res[1],res[2]). Store the value in some other variable and then u can use it later. I have corrected your code : https://codeforces.com/contest/1176/submission/55376346 •  » » » 4 months ago, # ^ | 0 Thanks...That was such a foolish mistake  » 4 months ago, # | 0 What is the hacking test case for Solution E ?? •  » » 4 months ago, # ^ | 0 Is it legal for codeforces? If so, it seems to me unfair •  » » » 4 months ago, # ^ | 0 I meant share hacking test with others •  » » » » 4 months ago, # ^ | 0 The contest is already over and I think any discussion about only seems useful •  » » » 4 months ago, # ^ | +3 How is it unfair?Nobody is being awarded any marks for hacking other's submission. •  » » 4 months ago, # ^ | +4 In my case: My solution got Hacked because of using memset(visited,0,sizeof(visited)); for each test case. The size of visited array in my soln was 2e5. So if the number of test case is 2e5, it will give TLE. :/  » 4 months ago, # | 0 This is really strange behaviour I have observed. My solution is absolutely correct but still giving tle. can someone look into this. Thanks in advance.My solutionIt is really annoying to see people with the same approach pass the solution. where as my solution fails.Soulution with similiar Approach that passedAonther Such SolutionAnd here one moreI kindly request community to help me figure out the issue. Correct solution being hacked due to some disgusting silly tight time constraint is really frustrating.. •  » » 4 months ago, # ^ | +1 you use memset T times •  » » 4 months ago, # ^ | 0 Using memset T times: giving TLE. Even my solution got hacked due to same reason :/ •  » » » 4 months ago, # ^ | 0 I guess that's really awful. getting tle for absolutely correct solution. what say?? Such silly tight time constraints shouldn't be entertained. Even if one puts up correct solution, getting unsuccessful verdict for this is really not done. •  » » » » 4 months ago, # ^ | 0 Well, I think that we should have been more careful about it. It was clearly written that the number of test case are till 2e5. We could've done without using memset. Check my latest submission. •  » » » » 4 months ago, # ^ | ← Rev. 3 → +23 I don't see anything awful. Maybe you see this for first time. But doing something unnecessary should not be entertained and that's what problem author has done! When you don't need$2\times 10^5$nodes in each test case then why using memset? You should know about the functions before using them.  » 4 months ago, # | ← Rev. 2 → +3 Can you explain me why is it working as it is working?55375918 this solution gets OK55375854 this solution get TLBut the problem is, the asymptotic is the same.The difference is that in first submission we check from 2 to x-1and in second from x-1 to 2.Am I missing something? •  » » 4 months ago, # ^ | ← Rev. 4 → +6 The number 1530169 = 1237 * 1237 is not a prime, so in the first program you will iterate from 2 to 1237, but in the second program you will iterate from 1530168 to 1237. In the worse case the first program will iterate from 2 to sqrt(x). In the worse case the second program will iterate from x-1 to sqrt(x).  » 4 months ago, # | 0 Will an unsuccesful hacking attempt affect my rank? •  » » 4 months ago, # ^ | +4 No  » 4 months ago, # | 0 I am curious about how to do for minimum number of vertices in question E, anybody can help? •  » » 4 months ago, # ^ | +4 Asking for minimum number of vertices is NP-hard. Wikipedia page •  » » » 4 months ago, # ^ | 0 Ok thanks •  » » 4 months ago, # ^ | +7 For a tree u can calculate that value using dynamic programming and problem is called minimum set cover  » 4 months ago, # | -9 When you get WA on submitting C.PS: Those who have watched Lost will relate. •  » » 4 months ago, # ^ | +15 Indeed, this number sequence is the one used in "Lost".  » 4 months ago, # | 0 How come I am getting TLE? Problem Ehttps://codeforces.com/contest/1176/submission/55377412  » 4 months ago, # | +7 WTF !!!Memset gave me TLE in E. •  » » 4 months ago, # ^ | 0 Hard Luck!! •  » » 4 months ago, # ^ | 0 I think it's because you use memset in the beginning of each test case. Which is around 1e5 test cases, and you use memset for an array with a size of around 1e5, so its basically a TLE. •  » » » 4 months ago, # ^ | +3 Yes, I realised that later.  » 4 months ago, # | +6 is using memset inside the test cases loop making E questions wrong ?? Hard Luck to those who have not taken care of it. •  » » 4 months ago, # ^ | +3 yes, someone hacked my solution using TLE verdict. :(  » 4 months ago, # | 0 How to solve problem E ? •  » » 4 months ago, # ^ | +3 You can DFS or BFS start from node 1 to build a tree of the graph. Now if the number of nodes which have odd degree is <= n / 2 then the answer is all of them, otherwise the anwser is all the nodes which have even degree. •  » » 4 months ago, # ^ | +6 Notice that this problem can be solved on a tree this way: paint a tree in two colors (black / white), this way each edge will connect vertices of different color and it will guarantee us that each white vertex is connected with at least one black and vice versa splitting vertices into two groups guarantees us that one of these groups will not be greater than$\lfloor \frac{n}{2} \rfloor$(application of Pigeonhole principle) We can select any group of vertices to solve the original problem, so we need to select smaller group of vertices Now, we can notice that removing edges from our graph without breaking it into multiple connectivity components does not affect the solution correctness (if we satisty all conditions with less amount of edges, we still satisfy it for any additional edges). This allows us to delete some edges from our graph without breaking connectivity. So, we can delete all edges and only leave a spanning tree of our graph (we can do it with DFS) and solve problem on a tree. •  » » » 4 months ago, # ^ | +5 understood ! thank you very much. •  » » » 4 months ago, # ^ | 0 how i can get a tree by delete some edge?i do not understand you •  » » » » 4 months ago, # ^ | 0 We can find an edge that does not break a graph connectivity and delete it from our graph. If we will repeat this operation until there is no edge left that can be removed from the graph without breaking conectivity the graph will become a tree. This happens because we can only delete an edge that is included in some cycle in a graph and when we will eliminate all cycles in given graph it will becaome a tree. Such tree is called spanning tree of our graph.But in practice it is not efficient to build spanning tree of a graph by iterativety deleting edges and checking connectivity after this. We can utilize some graph traversal algorithm here, such as DFS or BFS. These algoriithms have an important property: they visit each vertex only once. So, we can track the edge that was used to come to each vertex for the first time (except for the starting vertex). Obviously there will be no cycles in choosen edges, so we will get a tree that connects every vertex that can be reached from the starting vertex. So, we get a spanning tree of our graph. These trees are also called DFS-tree or BFS-tree and have some additional useful properties along with being a spanning trees of a given graph.Hope this explanation helps. •  » » » » » 4 months ago, # ^ | 0 thank u  » 4 months ago, # | 0 if anyone wants to hack plz hack my solution of E i want to know whether it is correct ?? •  » » 4 months ago, # ^ | 0 Try resubmitting it.  » 4 months ago, # | 0 Bop it!  » 4 months ago, # | +1 Hey guys, I have made a new app Coding List which contains all live, upcoming programming competitions from hackerearth, kaggle, codechef, codeforces, topcoder, aigaming, hackster, codinggame, hackerrank, projecteuler, atcoder and many more.A must have app for programmers. Please rate and review it. Try it here https://play.google.com/store/apps/details?id=io.github.vikasgola.coding_list  » 4 months ago, # | ← Rev. 2 → 0 ss  » 4 months ago, # | 0 Can anyone please tell why am I getting TLE in Problem E: 55381696 Thank you.. •  » » 4 months ago, # ^ | 0 check answers above before commenting. •  » » 4 months ago, # ^ | 0 Remove memset and use a simple for(0 -> n+1). You defined MAX to be 200005, which gets executed 200005 times(queries). Thats why TLE. •  » » » 4 months ago, # ^ | 0 ohh yes..that was so silly .. Thanks u very much..  » 4 months ago, # | 0 How come I am getting TLE? Problem Ehttps://codeforces.com/contest/1176/submission/55377412  » 4 months ago, # | 0 Did C using recursion(dfs style). But I guess many did in iterative way. Anyways complexity comes out to be$O(n)\$.Here is the Code
•  » » 4 months ago, # ^ |   0 Congratulations
 » 4 months ago, # |   0 Hey guys, can anyone tell me what's wrong with my solution for C (https://codeforces.com/contest/1176/submission/55357077) ? I fail test 7 and I don't see why. Maybe someone can tell me a counterexample for my approach.
•  » » 4 months ago, # ^ |   0 i don't know if that is the main problem or not .. but test like this 14 4 8 15 16 23 23 42 4 8 42 15 16 23 42 fails in your code .. you pop from the queue whenever you enter the function even if the sequence isn't right so you affect the following sequences.
 » 4 months ago, # |   0 Can someone tell me why this TLE plz? Thanks! Code
•  » » 4 months ago, # ^ |   0 you define vector t times with size MAXN.
 » 4 months ago, # |   0 System Test has finished?
 » 4 months ago, # |   +2 Editorials?
 » 4 months ago, # |   +1 did it rating?
•  » » 4 months ago, # ^ |   0 Not it
•  » » » 4 months ago, # ^ |   0 okay
 » 4 months ago, # |   0 The writer of F( Destroy it!) must be a Slay the Spire player !
 » 4 months ago, # |   +5 Can someone check my code in Problem D? I have no idea about why it got Memory limit exceeded on test 5.
•  » » 4 months ago, # ^ |   +13 your bug is in finding maxD. actually you're finding greatest prime factor! and cause of this you may erase something which is not in multiset(st.end()) from it and you get memory limit in this case
•  » » » 4 months ago, # ^ | ← Rev. 3 →   +13 I get it. I should read the problem description closely. Thank you!
•  » » 4 months ago, # ^ | ← Rev. 2 →   +13 I think you're incorrect fill maxD. maxD at your logic is max prime divisor while you need there to just max divisor. You can fix it, if replace maxD with minD and try to find p / minD[p] instead of maxD[p].
 » 4 months ago, # |   0 Rating is not updated yet for this contest
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 System testing has just finished. Rating will update in a couple of hrs. If you want to check live rating during contest plz. check out this CF predictor plugin
 » 4 months ago, # |   0 Good contest with less number of hacks :)
 » 4 months ago, # |   0 Why can't I see all the testcases when the system test has ended?
•  » » 4 months ago, # ^ |   0 Just wait till the ratings are out. And you can actually see them by checking the solution of one who has got AC.
•  » » » 4 months ago, # ^ |   0 Those are pretests bro. Just 15-16 in number max. They were displayed in the hack phase too.
 » 4 months ago, # |   +1 Can someone help me? Problem C, my code I am getting answer 65 in test case 65 instead of 64.
 » 4 months ago, # |   +13 I suggest you read my_solution for problem F(Destroy it!). I have dp[N][10] that dp[i][j] is maximum sum if we have get x cards from first i round and x mod 10 = j. and it's easy to see that in each round we may use only 3 strongest card that cost 1, strongest card cost 2 and strongest card cost 3 so by a mask on these(at most 5)cards you can update dp easily. if you have shorter solution please tell me
•  » » 4 months ago, # ^ |   +3 I think this is intended solution. I have something similar but I didn't debug yet. And I really doubt there is something shorter
 » 4 months ago, # | ← Rev. 3 →   0 In problem E why an output of:24 5wrong for the test case:5 82 52 15 14 51 42 43 43 5
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 For this test case your output is correct. But in test#2 there are 40057 testcases. You just wrong output in some other testcase.P.S. Your solution is incorrect for graph-chain. Lets imagine graph 1-2-3-4-5-6. There are 6 vertexes. And you output n / 2 vertexes with smallest degrees. There you can output vertexes 1, 6, 2. And vertex 4 remain unconnected.
•  » » » 4 months ago, # ^ |   0 Yes, thanks.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +11 your solution isn't correct let's try this:17 61 21 31 42 53 64 7
 » 4 months ago, # |   0 Sorry if this question is trivial but I don't relly get the solution of C. I think that we just need to find the number of subsequences that can be formed from the given array by finding the minimum frequency of 4, 8, 15, 16, 23 and 42, right. But that solution fails at test 6, which I don't understand why because clearly we can have 13 subsequences in this case.
•  » » 4 months ago, # ^ |   0 Your solution doesn't respect order of numbers.As said in task: "Examples of bad arrays:[4,8,15,16,42,23] (the order of elements should be exactly 4,8,15,16,23,42);..."
 » 4 months ago, # | ← Rev. 2 →   0 Can someone please have a look at my code for problem D. I can't understand why it is giving WA on test case 20. Thanks
 » 4 months ago, # | ← Rev. 2 →   -6 Editorial please
 » 4 months ago, # | ← Rev. 3 →   0 Can somebody help me out here? This submission for problem A where i used map to store results gets TLE whereas this one which uses brute force doesn't. Shouldn't the former just reduce complexity?
•  » » 4 months ago, # ^ |   +1 First solution does three recursive calls, second always does only one.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Oops, I didn't even notice that i used if instead of else if there, this was quite stupid to even ask, Btw Thanks mate.
 » 4 months ago, # |   +1 for problem A why do you choose this order of operation 4*n/5 , 2*n/3 , n / 2 ?
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 I don't think the order matters in this question, as the number of steps depends on the prime factors of the number itself. Let's take 60 for example, here 60 = 3 * 5 * 2 * 2 ; so it will always require 2 operation 1, 1 operation 2 and 1 operation 3 and as second and third operation multiplies 2 and 4(2 * 2) respectively, we would need to apply first operation 3 more times. Hence, the answer would be 1 + 1 + 2 + 3 = 7 irrespective of the order of operations applied.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 let's take n = 10 and order /2 , 4/5 ,2/3 then n is 10 , 5 , 4 this outputs -1 so order does matter if u do it this type of operations but i think you to wanted to get its factors so you do /2 , ans ++ , /5 , ans+= 3 , /3 ,ans+= 2 ,
•  » » » » 4 months ago, # ^ |   0 Dude, for 10 if you apply 1st operation first then it would go like this 10 -> 5 -> 4 -> 2 -> 1 (applying 1st operation two more times when n was transformed into 4). if you apply 2nd operation first then it would go like this, 10 -> 8 -> 4 -> 2 -> 1. Number of operations remains same irrespective of order (in this case it is 4). And this should hold for every number as number of operation depends solely on the factors of that number.
•  » » » » » 4 months ago, # ^ |   0 that's wrong !
•  » » » » » » 4 months ago, # ^ |   0 How is that wrong? can you elaborate?
•  » » » » » » » 4 months ago, # ^ |   0 I misread the statement , sorry .
 » 4 months ago, # |   0 Getting WA in problem D. My logic:First, I sorted the given array in descending order. If a number is composite, I printed it and removed this number and it's highest divisor. Finally, The array contained only prime numbers and printed lowest half of prime numbers. My submission.
•  » » 4 months ago, # ^ |   0 Your algo is correct
•  » » » 4 months ago, # ^ |   0 But, why getting WA ?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +9 "The array contained only prime numbers and printed lowest half of prime numbers" — I think this is incorrect. 32 3 3 5 5 11Correct answer: 2 3 5Your answer: 2 3 3
•  » » » » » 4 months ago, # ^ |   0 Really grateful to u.
 » 4 months ago, # |   +13 Can you please make an editorial for this contest?
 » 4 months ago, # |   +8 Editorials?
 » 4 months ago, # |   0 Div.1⇐⇒Div.(2−3+3-1)
 » 4 months ago, # |   +1 Hello, I have no idea how a girl @hdude0164 managed to copy my solution during the contest. I don't know her by any chance whatsoever. I don't use any online IDEs, I use dev cpp on my laptop and submit the solutions on codeforces. I don't know what else could be provided as proof to prove my innocence. I had submitted the solution 15 minutes prior to her. Plus i did some research, her original account is @chhavij and this is surely some fake account. Please look into it.
 » 4 months ago, # |   +7 Are there editorials?
 » 4 months ago, # |   +8 Also, can someone explain why is C a binary search problem?
 » 4 months ago, # |   +7 When will the editorials be published?Vovuh
 » 4 months ago, # | ← Rev. 3 →   +24 HiI saw you need editorial so i wrote this my self i hope it's useful for you
•  » » 4 months ago, # ^ |   0 problem about link is just fixed
 » 4 months ago, # |   +8 In problem E how can we find the minimum number of nodes to be chosen to satisfy the given condition
•  » » 4 months ago, # ^ | ← Rev. 3 →   +19 Wow such an amazing problem!But it seems to be NP hard cause I think if we can solve this we will solve that type of SAT that want minimum sum of variables.
•  » » » 4 months ago, # ^ |   +11 thanks bro
 » 4 months ago, # | ← Rev. 2 →   0 .
 » 4 months ago, # |   0 https://codeforces.com/contest/1176/submission/55406758 Can someone explain me why is it failing?
 » 4 months ago, # |   0 Why is this solution right solution ? 55421378
 » 4 months ago, # |   0 Best of Luck for your first contest as a problemsetter.