### Gol_D's blog

By Gol_D, history, 3 months ago,

Hello! Codeforces Round #805 (Div. 3) will start at Jul/10/2022 17:35 (Moscow time). You will be offered 7-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7-8 problems and 2 hours and 15 minutes 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 participant of the third division, you must:

• take part in at least five 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 our work. Problems have been created and written by ITMO University teams: MikeMirzayanov, MisterGu, myav, Vladosiya, Aris, SixtyWithoutExam and me Gol_D.

Also many thanks to turmax, Crescendo, antonis.white, Ronnie007, okwedook, Bugman, Kavaliro, antoshkin, omikad, yorky, Jostic11, Ziware, Kniaz, andrey.starodubtsev, Spaggetti and aniervs for testing the contest and valuable feedback.

Good luck!

UPD: Editorial

• +236

 » 3 months ago, # |   +4 Auto comment: topic has been updated by Gol_D (previous revision, new revision, compare).
•  » » 3 months ago, # ^ |   -9 bless you where are you from?????????!!!!!!!!!
 » 3 months ago, # |   +6 aniervs Chad <3
 » 3 months ago, # | ← Rev. 2 →   +1 Excited. Hopefully I will solve problems and learn many things form this contest. Thank you for organizing this contest.
 » 3 months ago, # |   0 Eid Day contest for South Asians! <3
•  » » 3 months ago, # ^ |   -6 Not for all south Asians...........
•  » » » 3 months ago, # ^ |   0 ++
 » 3 months ago, # |   0 I hope that codeforces round #805 will have very interesting tasks.
•  » » 3 months ago, # ^ |   0 Yeah It'll be.. ig interesting task's
•  » » » 3 months ago, # ^ |   0 I ahope that I will solve 3 problems somewhere
•  » » » » 3 months ago, # ^ |   0 Good luck hope me 2++ problems ^_^
•  » » 3 months ago, # ^ |   0 where do you come from bless you
 » 3 months ago, # |   0 Great round Hope i would able to solve 2++ problems:) Good Luck Everyone :D
 » 3 months ago, # |   0 Hope every contestant can achieve their expected results~Good Luck Everybody.Let's fight!
 » 3 months ago, # |   -39 A is XOR for sure
•  » » 3 months ago, # ^ |   -9 Meh, math!
 » 3 months ago, # |   0 All the Best Everyone!Hope everyone gets to learn something new from this contest and have a positive rating change!
 » 3 months ago, # |   0 Hoping that I can get out of gray tomorrow...
•  » » 3 months ago, # ^ |   0 Hell of a plot twist in your rating graph, Orz
•  » » 3 months ago, # ^ |   0 I managed to become a pupil despite under-performing heavily!
 » 3 months ago, # | ← Rev. 2 →   0 I hope that problems will be good
 » 3 months ago, # |   0 Eid Mubarak to evryone.
•  » » 3 months ago, # ^ |   0 you to brother. where you from??
•  » » » 3 months ago, # ^ |   0 Bangladesh,you?
•  » » » » 3 months ago, # ^ |   0 Algeria
 » 3 months ago, # |   0 Very excited! Hoping to get a positive delta!!
•  » » 3 months ago, # ^ |   +13 Go away Respected Mr expert ,lemme play with my div3 :)
 » 3 months ago, # |   -6 Eid day Contest night
•  » » 3 months ago, # ^ |   0 eid mubarek brother
 » 3 months ago, # |   +27 EID MUBARAK!
•  » » 3 months ago, # ^ |   0 you can't forget div4's
•  » » » 3 months ago, # ^ |   0 yes! i can't forget
 » 3 months ago, # |   0 I hope problems are good
 » 3 months ago, # |   +15 First div 3 on a weekend since July 10,2021 (exactly 1 year ago!)
 » 3 months ago, # |   +6 I like div.3 !!!
 » 3 months ago, # |   0 It's going to be fun solving doing #803 problems !!!
 » 3 months ago, # |   +3 what topics to expect in problems C to D?
•  » » 3 months ago, # ^ |   -7 Greedy
 » 3 months ago, # |   0 Is div3 harder than div2 or eazier?
•  » » 3 months ago, # ^ |   0 Easier. Good luck!
•  » » » 3 months ago, # ^ |   0 Is problem A a question about XOR?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Tbh,I am not a tester.. But I guess it will be a math (or number theory) problem
•  » » » » » 3 months ago, # ^ |   0 I will get ABCD(I'm not sure)
•  » » » » » » 3 months ago, # ^ |   0 Good luck, added you to my friend list cuz you look like an ambitious programmer!
•  » » 3 months ago, # ^ |   0 Easier
•  » » 3 months ago, # ^ |   0 Div3 tasks easier than div2 tasks
•  » » 3 months ago, # ^ |   0 easier
 » 3 months ago, # |   +16 Where are the "as a tester, blah blah blah" comments? Lol. Good luck guys!
 » 3 months ago, # |   +3 There was a time when div3 was unrated for me )
•  » » 3 months ago, # ^ |   +5 It's time to restore those times then. Good luck!
•  » » » 3 months ago, # ^ |   +1 Thank you bro )
 » 3 months ago, # |   0 fighting!!!
 » 3 months ago, # |   +2 Very exited for speedforces for div 1 participants..
 » 3 months ago, # |   0 wish to be blue today :D
 » 3 months ago, # |   +1 Specialists are least worried of their rating drop today, bcoz they hav div 4 coming soon to rescue in that case.
 » 3 months ago, # |   0 nice
 » 3 months ago, # |   0 Hope there will be an increasement on my rating, depending on #805 and #806 OwO.
 » 3 months ago, # |   0 7-8 problems? wow!
 » 3 months ago, # |   +1 my rating is less than 1600, still, it is showing unrated for me. why?
•  » » 3 months ago, # ^ |   +11 It is fixed!
•  » » » 3 months ago, # ^ |   +13 The rated leaderboard has some expert users. Is the round rated for them?
•  » » » » 3 months ago, # ^ |   0 same doubt
•  » » » » 3 months ago, # ^ |   0 No
•  » » » 3 months ago, # ^ |   0 my rating is less than 1000 , still, it is showing unrated for me. why?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I have the same situation with [user:mr_i_oker], my rating is less than 1600, and it is still unrated for me.
•  » » » » 3 months ago, # ^ |   0 me too.
•  » » » 3 months ago, # ^ |   0 Excuse me, I'm all G2 checked, but I just changed the board. What should I do? Sorry, I'm only 2000 and can't add points
 » 3 months ago, # |   +41 Round 805 — cout << (ok ? "YES" : "NO");
 » 3 months ago, # |   +1 E seems so easy , but not able to get Accepted :( . Frustration
 » 3 months ago, # |   0 Easier div3 but problems are also nice :p
 » 3 months ago, # |   +46 Today's problem F — https://atcoder.jp/contests/abc254/tasks/abc254_h
•  » » 3 months ago, # ^ |   0 It's exact the same.
•  » » 3 months ago, # ^ |   +8 Yeeeeep! No wonder i wrote it so smoothly.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 ...
•  » » » 3 months ago, # ^ |   0 No, the number of edges will be $n^2$ in worst case
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 ...
 » 3 months ago, # |   0 For G2 what do we need to pre-calculate.
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ |   +3 yes I thought about that but was not able to figure out actual process to solve query, I mean what to look for in the queries.
•  » » » » 3 months ago, # ^ |   +26 First, convert the tree into a rooted tree.Let $d_i$ be the depth of a vertex $i$, and $u$ and $v$ be two vertices where $d_u <= d_v$.For each $(u,v)$ pair, there are two cases:Case 1: $lca(u,v) = u$ : This means that you are going "upwards" in a straight path and the path never goes down.In this case, as long as $lca(u,v) = u$ is true, we are going upwards and every vertex is in the same path. Case 2: $lca(u,v) = x$ : This means that the path is not a "vertical" straight line. It has broken into two paths from vertex $x$.Now, it is clear that every new vertex $y$ must exist within the shortest path from $u$ to $v$. Otherwise, the set is not passable.The vertex is present in the path if and only if: $d_y > d_x$ or $y = x$ ($lca(x,y) = x$) $y$ lies between $u$ and $x$ ($lca(u,y) = y$) OR $y$ lies between $v$ and $x$ ($lca(v,y) = y$)
•  » » » » » 3 months ago, # ^ |   0 thanks
•  » » 3 months ago, # ^ |   0 Hey, I was seeing your G1 code, but not able to understand what you doing in the dfs func..coud you pls explain briefly? thanks
•  » » » 3 months ago, # ^ |   0 Binary lifting.Written tutorial by AlexLuchianovVideo tutorial by ErrichtoLCA using binary lifting at CP Algorithms
•  » » » » 3 months ago, # ^ |   0 Excuse me, I'm all G2 checked, but I just changed the board. What should I do? Sorry, I'm only 2000 and can't add points
•  » » » » » 3 months ago, # ^ |   0 Sorry, what?
•  » » » » » » 3 months ago, # ^ |   0 My G2 has been double checked. How can I appeal
•  » » » » » » » 3 months ago, # ^ |   0 I assume you mean your submissions have been skipped. I think you need to contact Mike about it.
•  » » » » » » » » 3 months ago, # ^ |   0 Thank you for your comments
•  » » 3 months ago, # ^ |   0 @sadid_005 also please tell the dsu logic u used for e. thnks
 » 3 months ago, # |   0 Although I didn't perform very well, I enjoyed the contest.
 » 3 months ago, # |   +1 How to solve E?
•  » » 3 months ago, # ^ |   +1 Just use dsu. If cycle of odd length exists then the answer is NO.
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 I did it with 2SAT using Kosaraju's SCC algorithm. Edit: Easy first check: Make sure no domino has the same number (e.g {3,3}) and no number is in more than 2 dominos ({1,2},{1,3},{1,4} since 1 appears 3 times). Next, for each domino $i$, define a variable $x_i$ for if $x_i=true$ set domino $i$ in set 1 and $x_i=false$ to put it in set 2. Then for each two dominos $(i,j)$ that intersect ($O(1)$ per domino because of the checks above), add the 2 sat constraints $(x_i\lor x_j) \land (\lnot x_i \lor \lnot x_j)$. Then there is a valid satisfiability if and only if $x_i, \lnot x_i$ do not exist in the same strongly connected component.
•  » » 3 months ago, # ^ |   0 Bipartite graph matching. But also check if each number appears < 3 times
•  » » 3 months ago, # ^ |   0 Bipartite graph knowledge is needed to solve it.
•  » » » 3 months ago, # ^ |   0 Could you pls explain a little more..I know bipartite though...but i cant get that if a domino is {1,2} are we taking 1->2 as edge? if yes, then how we are partitioning them as they would come together in 1 set?
•  » » » » 3 months ago, # ^ |   +1 Each Domino is a node. And edge is when 2 dominos have a common element like {1, 2} and {2, 3}. Then basically we do graph coloring like assign Red color to node A and recursively assign Blue to all its neighbours since they cant be in same set. While doing this we are dividing the big set into 2 sets. If during recursion, the neighbors have same color : recursion fails and graph is non-bipartite and we cannot divide the big set into 2 sets.Hope it clears things++
•  » » » » » 3 months ago, # ^ |   0 Yes got it. Amazingly explained. Thanks a ton!
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Bipartite Colouring
•  » » 3 months ago, # ^ |   0 check if all the connected components in the graph formed by (ai, bi) as edges are bipartite, and also make sure that the degree of all nodes is at most 2
•  » » » 3 months ago, # ^ |   +3 I just checked for degree of each node and the number of nodes in each connected component should be odd and it works fine no need for bipartite.
 » 3 months ago, # |   +2 Problem G2 had appeared in CodeChef July Long 2021 K Path Query
 » 3 months ago, # |   +6 I hate E.
 » 3 months ago, # |   +32 Problem F: ABC254-H
 » 3 months ago, # |   +7 Problem G can be found on Codechef — submission
•  » » 3 months ago, # ^ |   0 No wonder I submitted my exact Code from long challenge without even touching it 1 bit and everything passed xD.
•  » » » 3 months ago, # ^ |   0 I submitted the testers solution, the one i submitted on codechef a year ago gives TLE on test 89 (https://ideone.com/gUSCNT), honestly i don't even want to understand what i implemented back then.
 » 3 months ago, # |   0 i got the desired output for question d and i am pretty confident that the logic is correct as well but in test 1 it showed an unexpected error "wrong answer Line [name=s] equals to "aa ", doesn't correspond to pattern "[a-z]{0,200000}" (test case 1)", i don't understand what this is, please tell me where i am wrong or if this is an issue on your end please fix it, here is my submission https://codeforces.com/contest/1702/submission/163545146
•  » » 3 months ago, # ^ |   0 You are printing a space after string
•  » » 3 months ago, # ^ |   0 Sorry to say but you made a very minute mistake of defining endl as " \n" ( #define endl " \n" ) This is leading to an extra space character in each of the outputs and hence not matching the pattern.
•  » » » 3 months ago, # ^ |   0 Thank you for replying, but I have been using this template since the beginning should I start using endl in place of \n?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Just remove the space before \ in " \n". Your AC code: 163581870
•  » » » » » 3 months ago, # ^ |   0 Thank you
•  » » » » 3 months ago, # ^ |   0 No, using endl would flush stdout, which is definitely superfluous when it's redirected to somewhere rather than terminals.Instead, you might define endl to be '\n' solely.For your reference.We need to flush the stream only if there's an interactive problem on online judges.
•  » » » » » 3 months ago, # ^ |   0 Thank you
 » 3 months ago, # |   0 Really know little about string....I can only use the STL thus then I failed C and D while my code is ok on the test set x<
 » 3 months ago, # | ← Rev. 2 →   +5
 » 3 months ago, # |   +21 YesNoForces
 » 3 months ago, # | ← Rev. 2 →   +5 Solving E: Ahahahaha easy question, not fit for E; Writes code using set stl;... Wrong answer test (2) wtf??? Think think think... Finds that ordering matters; Anguish LOL, even after that I found a viable solution using graphs and cycle detection (any odd cycle detected = NO) else true. Graphs are not simple; but i kept them undirected ...But then the contest finn (more anguish)
•  » » 3 months ago, # ^ |   0 I also solved E using set and got WA on test 2 but cannot figure out any counterexample can you please explain a counterexample where set fails.
•  » » » 3 months ago, # ^ |   0 {{1,2},{3,4},{3,5},{2,5},{4,6},{1,6}} We can partition as {{1,2},{3,5},{4,6}} and{{3,4},{2,5},{1,6}}. But your code will give NO
 » 3 months ago, # |   0 It is my first time to solve 4 problems in a div3 contest :)
•  » » 3 months ago, # ^ |   0 Same here Bro, Congrats!!
•  » » » 3 months ago, # ^ |   0 Nice! Good luck:)
 » 3 months ago, # |   +15 In B, I would have been happy to read something like "Poly does not remember letters from previous days". Or at least having a sample from that this detail would become clear.In E it would have been helpfull to have an example of two dominoes that must not go into one group, like "if there is an domino {x,y} in one group, not other dominoe with x or y can go into the same group". Instead there are positive examples only, and no formular description.
•  » » 3 months ago, # ^ |   0 Agree B...however didnt quite get you for the E one... I think there was an announcement too about this... Also, if anything they could add as a visible testcase, it could have been an example where changing the order of queries/dominos would result in a switch between NO/YES.
•  » » » 3 months ago, # ^ |   0 The phrase "all numbers on the dominoes of a set are different" was unclear to me. After having that read, I asked if {1,2} is same domino as {2,1}, which shows that I completly did not understand what was asked for.
 » 3 months ago, # |   0
 » 3 months ago, # |   0 First round where I shifted from c++ to py just for A,B xD...because the code is much much simpler and shorter
 » 3 months ago, # |   0 why a greedy method will fall for E? If no dup in set1, put in set1, if no dup in set2, put in set2. Otherwise, output No.163580026
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Consider a test case like: (1 3) (2 3) (4 5) (2 5) Now 2 5 cant be inserted if greedy, but otherwise it is possible.
•  » » 3 months ago, # ^ |   0 That would fail for a case like: (1 2), (3 4), (3 5), (2 5)
•  » » » 3 months ago, # ^ |   +3 You cannot have 5 if n is 4.
•  » » » » 3 months ago, # ^ |   0 Exactly!
•  » » 3 months ago, # ^ |   +4 Consider these pairs for N = 6 2 5 3 1 4 1 4 2 5 6 6 3
•  » » 3 months ago, # ^ |   0 1 31 22 3
•  » » 3 months ago, # ^ |   0 {{1,2},{3,4},{3,5},{2,5},{4,6},{1,6}} .By greedy method you will insert 1 2 in fisrt set then 3 4 also in first and 3 5 in second .After that you can't insert 2 5 in any of the two. But we can partition it as {(1 2)(3 5)(4 6)} and {(3 4)(2 5)(1 6)}
 » 3 months ago, # | ← Rev. 2 →   0 Problem E is again a annoying cyclic permutation question. These question really confuses me even though idea is simple.
 » 3 months ago, # | ← Rev. 2 →   0 -
 » 3 months ago, # |   +9 Did anyone have a prediction for 0 rating changes? I had on this round)!
 » 3 months ago, # |   0 Although I now hazily see that I should have used dsu for problem E, I don't clearly understand why my greedy approach wasn't accepted: 163579353I can't see what kind of test case rendered it wrong since it's 6930th one down in the abyss. Can anyone raise an example?
•  » » 3 months ago, # ^ | ← Rev. 8 →   +4 Oh dear, n = 6, {1, 3}, {2, 3}, {4, 5}, {2, 5}, {4, 6}, {1, 6} leads to "NO" whereas it should actually output "YES". Self-satisfied.
•  » » » 3 months ago, # ^ |   0 look at my comment for greedy approach comment
•  » » » » 3 months ago, # ^ |   0 Oh gosh, revolutionary.
•  » » » 3 months ago, # ^ |   0 thanks.
 » 3 months ago, # |   0 well problem c was confusing for me.Let us say for the test case:-14 11 2 5 15 2we can go from station 5 to 2 because we can go from 5 to 1 and then 1 to 2. So Answer should be yes.
•  » » 3 months ago, # ^ |   0 It does not work like that. The train goes from 1 to 2 only in the first appearance of station 1, but going from 5 to 1 happens in the second appearance of 1.
•  » » » 3 months ago, # ^ |   0 Yeah but it wasn't mention properly.
•  » » 3 months ago, # ^ |   0 it was clearly mentioned train starts from left and moves to right .
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 No buddy we have to follow the order of the array. Here in this example the train will move from station 1 to station 2 then from station 2 to station 5 and from station 5 to station 1. Suppose you are at index i of this array then you can only go to stations from (i+1)th index to n-1. We cannot go from 5 to 2 because 5 is at index 2 but there is no index having value 2 in the range of (i+1)th index to n-1 . So the answer for this test case is NO. Hope you get it now.
 » 3 months ago, # | ← Rev. 2 →   +17 wtf is with place 19?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 In the last div 2 educational round, I can see red coders in the official standings
•  » » 3 months ago, # ^ |   0 why can't I see a rating change like in your screenshot!!!I am new to CF, Could you please help me.
•  » » » 3 months ago, # ^ |   0 It's an extension called carrot
•  » » » » 3 months ago, # ^ |   0 I can't see a rating change even after installing the extension
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 you can cf predictor extension
•  » » » » » » 3 months ago, # ^ |   +1 unfortunately cf predictor is not working from a couple of days
•  » » » » » 3 months ago, # ^ |   0 activate it and wait for a moment for it to load
 » 3 months ago, # |   0 void solve() { string s; cin >> s; ll p; cin >> p; vector mp(26, 0); ll w = 0; for (auto &i : s) { ll t1 = i - 'a'; w += t1 + 1; mp[t1]++; } vector pq; for (int i = 0; i < 26; i++) { if (mp[i] == 0) continue; pq.push_back(i); } ll o = w - p; sort(pq.begin(), pq.end()); int j = pq.size()-1; while (j >= 0 and o > 0) { ll val = pq[j]; o -= val + 1; mp[val]--; if (mp[val] <= 0) { j--; } } string res = ""; for (auto &i : s) { int t1 = i - 'a'; if (mp[t1] > 0) { res = res + i; mp[t1]--; } } cout << res << endl; } Can anyone point out why this gives TLE on test case 6. I think the complexity is O(nlogn) at max and it should work. It would be of great help if anyone could point to what i am missing.
•  » » 3 months ago, # ^ |   +13 Try res += i instead of res = res + i.
•  » » » 3 months ago, # ^ |   +3 why? is second one slower than the first one?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +7 Because first is just appending a char at the same address, whereas the second one is actually concatenating 2 strings and storing the entire result at the address.
•  » » » » 3 months ago, # ^ |   0 Unfortunately.
•  » » » 3 months ago, # ^ |   0 Thanks, buddy! got AC after this. Feeling so dumb rn (T-T). Never knew a simple assignment could make such a difference. Lesson learned :).
 » 3 months ago, # |   0 why everytime it seems hard to me when i went to implement more than 1 question in each of all contest,how should i overcome? should i follow c2ladder and learn stl? nowdays it seems disappointing but i dont want to give up, if you have some min to suggest than i hope you will do,and always grateful to the community.
•  » » 3 months ago, # ^ |   0 focus on DSA and implementation skills first, along with problem solving, at sites like GeeksForGeeks or Leetcode. I too started competitive programming right away and couldnt get a hang of it, until I went through the basics, and came back
 » 3 months ago, # |   +1
 » 3 months ago, # |   0 Great job on this round but we're still waiting for the tutorial hope it comes out fast also I want to ask problem E can it be solved using two sets and if not why
•  » » 3 months ago, # ^ |   0 ++
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 I don't think, try this test to get the idea : 1 24 52 33 45 6 6 1
•  » » 3 months ago, # ^ |   0 problem E can be solved using greedy approach, check my comment
 » 3 months ago, # | ← Rev. 2 →   0 Why is this failing, Problem (E) Bipartite coloring is used Code Thanks in Advance
•  » » 3 months ago, # ^ |   0 Nodes Adjacent to a node must be in a different set, not u and v.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 also, you have to check if some number occurs more than twice, e.g. n = 4, (1, 2), (2, 1), (2, 3), (5, 6)if not to take it into account, your code will yield yes, as the graph is bipartite
•  » » » 3 months ago, # ^ |   0 It has been mentioned in the first line that a[i] and b[i] will be from 1 to n so you cannot take 5 and 6 for n=4
•  » » » » 3 months ago, # ^ |   0 okay, the point was that 2 occurs more than two times, we can replace 5 6 for 3 4
•  » » » » » 3 months ago, # ^ |   0 Could you please give the final two sets for your testcase?
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 i've meant case like 4 (1 2) (2 1) (2 3) (3 4)
•  » » » » » » » 3 months ago, # ^ |   0 Okay, i misinterpreted What I was asking is could you give a testcase where the greedy solution fails but your solution passes?
•  » » » » » » » » 3 months ago, # ^ |   0 try smth like this: 6 (1 3) (2 3) (4 5) (2 5) (4, 6) (1 6)
•  » » » » » » » » 3 months ago, # ^ |   0 to be honest, i didn't even try to solve greedily
•  » » » » » » » » » 3 months ago, # ^ |   0 Thank you guys! Got it :))
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 here is accepted submission with your code: https://codeforces.com/contest/1702/submission/163587320you need to count occurences and make graph undirected instead of directedyou can also check my sumbission (but i've used dfs to color the graph) https://codeforces.com/contest/1702/submission/163524885
•  » » » 3 months ago, # ^ |   0 Ahh this is great! I got it now, thank you so muchh!!!
 » 3 months ago, # |   0 Instead of solving G1 and G2 in 15 minutes, I spent too much time on problem E...Such a great contest to learn from experience
 » 3 months ago, # |   0 G2 is exactly the same as CodeChef KPATHQRY.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I understand that we find the endpoints of a possible simple path by sorting the k vertices of a query by depth. But how does it work to check if all other vertices are on the simple path between them?
•  » » » 3 months ago, # ^ |   +9 You can check it using distance. Lets say your endpoints are $l$, $r$ and you want to check if vertex $u$ lies on the path. Then $u$ must follow, $dist(l,r)=dist(l,u)+dist(u,r)$
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 epsilon decribed quite an elegant method but you can also do it with binary lifting/hld: Mark all relevant ancestors of the node with the lowest depth (First endpoint). Mark all relevant ancestors of an Unmarked node with the lowest depth (Second endpoint). A simple path is only possible if all given nodes (except their LCA) has been marked exactly once.
 » 3 months ago, # |   0 Hi everyone , can any explain why I'm getting wrong answer 163558459 I will go crazy ;) ... The idea is to make a map for first and another for second set , and see if (the numbers duplicated in the first and the second)-> NO else it's gonna be the answer -> YESIs this all there is in the question, or is there more?
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 I did exactly the same as you and we were trapped on the same stumbling block (6930th in 2nd test case). An example is that, n = 6, {1, 3}, {2, 3}, {4, 5}, {2, 5}, {4, 6}, {1, 6} leads to "NO" whereas it should actually output "YES"
•  » » » 3 months ago, # ^ |   0 why yes ? I'm guess that I didn't understand the problem. ;(
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 A = {{1, 3}, {2, 5}, {4, 6}}, B = {{2, 3}, {4, 5}, {1, 6}} actually satisfies all conditions. If you employ greedy approach, until you finish picking up 2 dominoes, the situation would be that A = {{1, 3}}, B = {{2, 3}}, which is fine at the moment. After that, you might want to put 3rd domino into A, however this methodology is totally doomed.
•  » » » 3 months ago, # ^ |   0 My submission 163579850 satisfies this testcase...idk where it fails on the pretests....
•  » » » » 3 months ago, # ^ |   0 check this Link
 » 3 months ago, # |   0 This round is rated for me but in normal case it should be unrated. Can anyone tell me what's wrong?
 » 3 months ago, # |   0 Any hints from problem $F$ ? For any $b\in B$, I can generate $reach(b)\subseteq A$ that $b$ can reach in $A$ after a number of operations. I don't see how to do the matchings greedily though (which I am assuming is the idea)
•  » » 3 months ago, # ^ |   +4 Note that a multiplication can be reversed. So it is an aequivalent problem if we divide all a[i] until all of them are odd.Then it is greedy, match all b[i] to the biggest possible a[j], by try/devide/try/devide/... until b[i]==0. If no match is possible then ans=NO.
•  » » » 3 months ago, # ^ |   0 Thanks, AC, that's an elegant solution :).
•  » » » 3 months ago, # ^ |   0 why till odd can you elaborate more, please? like a proof or something I am unable to get intuition.
•  » » » » 3 months ago, # ^ |   0 Because you can generate all the powers of 2 from '1' in the second array. So only the odd factor in the first array matters. After that for every b[i], keep dividing by 2 until you reach an element present in a. If b[i] becomes 0, then at least 1 element from a will always remain unmatched
•  » » » » 3 months ago, # ^ |   0 All multiples of a number x with powers of 2 build an aequivalence set. Because we can devide these numbers to come back to the first number, the odd one.This means, after reducing all numbers in a[] to that root value of their aequi-set, each number in b[] can be matched with only one given odd number in a[].
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 I am starting the solution as you mentioned, i.e. reducing all A[i] to their respective odd values. But, if I try to match each A[i] to the smallest possible B[i] my solution fails. I tried to generate a counter-test case but wasn't successful. Can you tell me why you tried to match  B[i] -> to biggest possible A[i]  instead of  A[i] -> to smallest possible B[i]  My Codevoid solve() { ll n; read(n); vll A, B; read_array(n, A); read_array(n, B); bool is = true; for (int i = 0; i < n; i++) { while (A[i] > 0 and A[i] % 2 == 0) A[i] /= 2; } multimap ele; // {number,number of nos. that have been generated by B[i]} -> index of B[i] for (int i = 0; i < n; i++) { stack st; while (B[i]) { st.push(pair(B[i], i)); B[i] /= 2; } // stores the number of nos. that can be generated from B[i] int contains = st.size(); while (st.size()) { auto top = st.top(); ele.insert({ {top.first,contains},top.second }); st.pop(); } } sort(all(A), greater()); // to process the greatest values of A first. // sorting is most probably redundant. for (int i = 0; i < n; i++) { // trying to find the smallest value in B that is greater than or equal to A[i]\ // {A[i],0} -> 0 ensures that I find the smallest no. that can be used to generate A[i] auto get = ele.lower_bound({ A[i],0 }); auto [e, contains] = get->first; ll id = get->second; ll ele_in_B = B[id]; if (get != ele.end() and e == A[i]) { while (ele_in_B) { ele.erase(ele.find({ ele_in_B,contains })); ele_in_B /= 2; } } else { is = false; break; } } cout << (is ? "YES" : "NO") << endl; } 
•  » » » » 3 months ago, # ^ |   0 Actually we do not match the a[i] with the smallest b[j], but instead the b[j] with each biggest possible a[i].Consider we have in a[] after divisions some numbers: $( ...,3, 7, 15, ...)$Now see if we can match a b[j] with the 15, we can also match it with the 7, and also with the 3. But the other way it does not work. A b[j] that can be matched with 3 does not automatically match the 7 or 15.
 » 3 months ago, # | ← Rev. 3 →   +10 All the hacked solutions from this contest are in problem C using PyPy3 or python even though they have the same logic as accepted solutions from other languages. Maybe its because of slow input or slow dictionaries in python. Anyways, python should have more time to pass.
•  » » 3 months ago, # ^ |   0 No the issue is with the hash , which leads to o(n^2)
•  » » » 3 months ago, # ^ |   0 Yes, in worse case: python dictionaries use hashing, and too bad there is no such thing as a Binary Search Tree (TreeMap in java and map in c++)
•  » » » » 3 months ago, # ^ |   +3 just use a tuple or str as a key
 » 3 months ago, # |   0 Can anyone share the test case of C, thanks in advance!
 » 3 months ago, # |   +11 Why are so many python solutions of O(n) time complexity for Problem C getting hacked ?
•  » » 3 months ago, # ^ |   -20 because stop using python cas it may be slow?
•  » » 3 months ago, # ^ |   0 If you use a hash map (dictionary) then it is not really O(n).
•  » » » 3 months ago, # ^ |   0 Unlike C++ in general the time complexity of adding and retrieving key-value pair in pyhton dictionary is O(1). Although there may be some overhead but it is not that significant that it would convert O(n) to O(nlogn).
•  » » » » 3 months ago, # ^ |   0 Hash table lookup is O(1) on everage and O(n) worst case. Hacks use a sequence that results in worst case behavior.
 » 3 months ago, # |   0 Can someone say how to solve C without hashing, bcoz my solution using dictionaries got hacked. Or is it fate of Python Users :(
•  » » 3 months ago, # ^ |   0
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Two waysEither use string to store keys in dictionary, Or there is a solution for this. Check out this code. Append this before your solution. And submit in python 3 https://codeforces.com/contest/1702/submission/163491564Credit goes to [user:pajengod]
•  » » » 3 months ago, # ^ |   0 You can't append before — only prepend. ;)
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 Hacks depend on the specific order of input. One approach is to shuffle the input values (along with their positions) before adding them to the dictionary.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Don't convert to integer if not necessary. Here is my solution in Python3: https://codeforces.com/contest/1702/submission/163519912
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 mnkp just wrote about using strings as keys.
 » 3 months ago, # | ← Rev. 2 →   +14 Nuu
 » 3 months ago, # | ← Rev. 2 →   +11 Very very bad situation for python coders..... really annoying to see same logic got hacked in python (C question)... its now time to leave codeforces... thank you codeforces community....
•  » » 3 months ago, # ^ |   0 People who used c++ and unordered map also got hacked.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/contest/1702/submission/163500607My AC C++ code which uses unordered_mapBut failed in system test
 » 3 months ago, # |   +14 Can we increase the time limit of problem C for Python? It seems like a lot of the Python solutions are getting hacked yet most of the logic is the same as other languages.
 » 3 months ago, # | ← Rev. 3 →   0 Hi, why problem E can't be solved using two sets, like this solution which fails at test 2?
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ |   0 Oh, I see. the order is important omg Thank you, appreciate it:)
 » 3 months ago, # |   +1 Moment of silence for those hacked on c
 » 3 months ago, # |   0 can someone pls let me know the error in this my submission
 » 3 months ago, # |   0 For E, I tried backtracking. I know its a bad way though, still if someone could please tee where it went wrong, I ll be very grateful. Thanks:) My Submission Link
 » 3 months ago, # | ← Rev. 2 →   0 have solved till E but for C i will loose around 100 rating .... its very unfair.... time limit should be increased for python... and Hacked solutions should be reevaluated for fairness or this contest should be unrated ...
•  » » 3 months ago, # ^ |   +1 Could you please tell how you did E? thnks
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 Solved it by first counting degrees of every node if any node degree is > 2 then return False ... Else also see that any kind of odd cycles are not allowed ...like (3 4) , (4 5) , (5 3) will not fit in 2 sets.... but even length cycle will fit in 2 sets like... (3 4), (4 5), (5 6), (6 3) **** set1 = (3,4) , (5,6) set2 = (4,5) , (3,6) **** so we have to check weather there exist any odd length cycle.... to check this we check if the graph is bipartite (if you dont know about bipartite graph...its kind of graph which devides the vertices into two sets so that and there will not be any odd length cycles...) To check for bipartite just run BFS with coloring ....you can see my code here **My solution : 163566318 ******
•  » » » » 3 months ago, # ^ |   +1 Thank you so much. I understood your explanation very clearly. Amazed how you thought of the same, I could never :), though I knew bipartite beforehand.
•  » » 3 months ago, # ^ |   0 Your E also got hacked lolGreat job shiviDON
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 ᓚᘏᗢ
 » 3 months ago, # |   0 Was anyone able to solve F with bipartite matching?I tried to use straight-up Dinic's as a last ditch effort and it didn't work out. Ah well.
•  » » 3 months ago, # ^ |   0 Effectively yes — by colouring the graph 0/1 using BFS and then checking for any contradictions (i.e. same coloured neighbours).
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 ...
 » 3 months ago, # |   0 can someone tell me how get the editorial of this or past contests
•  » » 3 months ago, # ^ |   0 Editorial will be avaliable soon after contest
•  » » » 3 months ago, # ^ |   0 can i see the editorial of all past contests?
•  » » » » 3 months ago, # ^ |   0 Yes. You can do that by opening any problem from that contest and on the bottom right you will find a link to the editorial.
 » 3 months ago, # |   +18 I did what appears to be something different to the norm for G2. Here is my approach.(0. If K <= 2, obviously the path is good.) Find the LCA of adjacent pairs of nodes in the list. It is guaranteed the the LCA of all nodes will be among these values, and that it will be the value with minimum depth. A simple path visiting all nodes must pass through the LCA (possibly as an endpoint only), and there can be at most 2 simple paths extending down from the LCA (i.e. joining at the LCA). Now for all nodes other than the LCA (if it is even one of the nodes), partition them into two possible paths by taking the LCAs of the adjacent pairs, and if that LCA is the overall LCA they are on different paths, otherwise they're on the same path. Sort the two candidate paths by depth. For each pair of adjacent nodes, check the LCA — if this is a simple path ordered by depth, then the LCA must be the node with lower depth. If not, the answer is NO. If all these conditions are satisfied, the answer is YES.
•  » » 3 months ago, # ^ |   0 I did almost the same, but a bit simpler: your second point sort points by depth in reverse order. If there is more than two points with same depth, no let's build these two paths: next vertex u connects to path p iff lca(u, p) == u handle case when you can connect vertex to both paths (it must be last vertex)
•  » » » 3 months ago, # ^ |   +5 Nice! Like that — as you say a little simpler.
 » 3 months ago, # |   0 what graph topic was problem E?
•  » » 3 months ago, # ^ |   +1 If you treat each index as a node and create an edge between nodes with common numbers (including possible self-edges), then a partition is possible IFF you can black-white colour the graph such that no adjacent nodes are the same colour.
•  » » 3 months ago, # ^ |   0 bipartite graph
 » 3 months ago, # |   -12 It doesn't make sense to penalize correct Python submissions with efficient time-complexity. I mean, one cannot use Python in Codeforces unless we write our own hashing function and map class? It's absurd. And if this continues, I expect all Python users to migrate to another platform.
 » 3 months ago, # |   0 In problem C last sample testcase testcase7 5 2 1 1 1 2 4 4 1 3 1 4 2 1 4 1 1 2why is 1 3 answer as NO? Its clear that we can go from 1 to 3 while going from 1->2->4
•  » » 3 months ago, # ^ |   0 As we can see in the input list, 3 is not one of the stations where the train stops.
•  » » 3 months ago, # ^ |   +1 So are you suggesting that they just jump off the train without it stopping at the station? xD
•  » » » 3 months ago, # ^ |   0 The first statement of the problem clearly says at each index there is a station Along the railroad there are stations indexed from 1 to 109
•  » » » » 3 months ago, # ^ |   +1 Yes but the bus doesn't stop at all stations.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I got it now. The train needs to stop.
 » 3 months ago, # |   0 Why did solution get hacked?(TLE)https://codeforces.com/contest/1702/submission/163537426
•  » » 3 months ago, # ^ |   0 Because of unordered map.
•  » » » 3 months ago, # ^ | ← Rev. 7 →   0 My for loop never goes beyond 2*10^5. Is unordered_map that slow?I never thought unordered_map is slower than map due to hashing function... map: 451ms plain unordered_map: 264ms unordered_map with reserve and load factor: 217ms mp.reserve(1024); mp.max_load_factor(0.25);
•  » » » » 3 months ago, # ^ |   0
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thank you so much icy. In short, unordered_map is usually faster but in worst case O(n) due to collision unless we provide decent hash function.
•  » » 3 months ago, # ^ |   0 Is it because I used STL?
•  » » 3 months ago, # ^ |   0 Just by using the normal map and you will get Accepted
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I also used unordered_map in c++ but my code got ACCEPTED. Can you point out the reason? My submission https://codeforces.com/contest/1702/submission/163500607Failed in System Testing
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 Already answered in icy's comment. Hashes(outputs of hash function) are bound to collide unless they are randomly distributed.In short, It is possible to have all hashes collide deliberately if the hash function is known. e.g. key: "foo", val: 123 -> HashFunc("foo") -> hash: 0xdeadbeef key: "bar", val: 567 -> HashFunc("bar") -> hash: 0xdeadbeef -> collision! key: "baz", val: 890 -> HashFunc("baz") -> hash: 0xdeadbeef -> collision! Upon collision, the unordered_map iterate buckets for the hash and this results in O(n^2) at the end.This does not happens in STL map, a red-black tree, that guarantees O(logn).
•  » » » » 3 months ago, # ^ |   0 Got it ! Thanks for explaining .
 » 3 months ago, # |   0 People who ask for increased time limit for python because of hashhack annoy me even more than falling for this hack. That's so stupid when it comes from people above gray
 » 3 months ago, # |   0 if you like this contest print "YES" otherwise print "NO"
 » 3 months ago, # |   +3 Solutions to the interesting problems:Problem FSay we have our two multisets $a$ and $b$. Firstly, notice that we can keep dividing elements in $a$ until they are odd and likewise keep dividing elements in $b$ until they are odd. This doesn't change our answer. Now we can simplify the problem and only consider the operation in which you divide elements in $b$ by two (there is no point in multiplying them by two anymore...). If the largest element in $a$ is equal to the largest element in $b$, then we know that we can remove the largest elements in $a$ and $b$ without changing our answer. Then recurse downards. If the largest element in $a$ is smaller than the largest element in $b$, then halve the largest element in $b$. Then recurse downwards. If the largest element in $a$ exceeds the largest element in $b$, then we can proceed and we can print "No" by default. Problem GFind the "diameter" of the path. Basically, for any path we have these two "leftmost" and "rightmost" vertices which sort of define the path and then a bunch of points between those vertices. We can find the diameter of the path by first finding the deepest node and then finding the node that is farthest from the deepest node (similar to how you find diameter of a tree...). Call these points $x, y$. Then, the rest of the problem reduces to figuring out if the other points lie between $x$ and $y$, which is a standard problem.
•  » » 3 months ago, # ^ |   0 Nice Explanation.Can you share link of the standard problem which is similar to G?
•  » » » 3 months ago, # ^ |   0 A point $u$ lies between points $x$ and $y$ in a tree iff:$lca(x, y)$ is an ancestor of $u$, where lca stands for least common ancestor.$u$ is an ancestor of either $x$ or $y$.To find $lca$, see: https://cses.fi/problemset/task/1688
 » 3 months ago, # |   0 My submisson: 163602507 Problem E. Does anyone know of a case that went wrong?
•  » » 3 months ago, # ^ |   0 1 6 1 2 2 3 4 5 3 4 5 6 6 1 
•  » » » 3 months ago, # ^ |   0 Your code can give different answers depending on the order of dominos given.
 » 3 months ago, # | ← Rev. 2 →   0 First time got rank in 3 digit
 » 3 months ago, # |   0 It's now 5h before the final standings and why it says the round is unrated for me?
•  » » 3 months ago, # ^ |   0 It's said that one must attend at least 5 contests and submit at least 1 problem in each contest before he or she is able to attend rated div.3
 » 3 months ago, # |   0 Thanks for this contest. The problems are explained clearly. ❤️
 » 3 months ago, # | ← Rev. 2 →   +5 In E,The observation that I got to was that each number can be paired with at most two othet numbers. Also , to appropriatly divide them in two sets, there shou should not be any cycle of odd length, but I got WA again and again. Where did i go wrong?Edit : Submission https://codeforces.com/contest/1702/submission/163572445
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Everything is OK, except one mistake in implementation. In string 16, what is "len(a) > 2 or len(b) > 2"? a and b are not initialized here. Instead of this, you should write "len(i) > 2" and you will get OK.
•  » » » 3 months ago, # ^ |   +5 I had it in above line but I didn't know how did it came here.Thanks man,You killed my Imposter Syndrome today
 » 3 months ago, # |   0 Would the datas which were used to hack others' codes successfully be tested for everybody after the HACK is closed? I was trying to hack someone's code but I submitted a wrong data, but I'm sure his code will lead to Time Limit Exceeded. lol, then I hope others' hacking datas would hack this bro's code.
 » 3 months ago, # |   0 I am always dreaming of AK the div3
•  » » 3 months ago, # ^ |   0 Me too. But things became different when I was stuck on Problem E. And I sill don't know how my programmed go wrong. My submission: https://codeforces.com/contest/1702/submission/163579127
•  » » » 3 months ago, # ^ |   0 Problem E killed my 1-hour time with getting no gains.
 » 3 months ago, # | ← Rev. 3 →   0 update Got it
 » 3 months ago, # | ← Rev. 2 →   -14 Contest Must Be Unrated ... as many python coders unnecessary got hacked... it will be unfair to them...
•  » » 3 months ago, # ^ |   0 Can you explain how did it happen?
•  » » » 3 months ago, # ^ |   +5
•  » » 3 months ago, # ^ |   0 Of course you are afraid of your rating falling, you don't even have the guts to give div2 rated contest
•  » » 3 months ago, # ^ |   +8 That's an interesting usage of "unnecessary". I think you define an "unnecessary" hack as one that you do not want to see.However, in real life the defintion is more simple: If your solution can be hacked, then it will be hacked. So it is your responsibility to provide an unhackable solution.I think that might be sometimes more hard in Python than C++, but nevertheless, you are free to choose. And in this case, why you do not have a template implementing a not-hashcode based structure usable as a map? Or use one with a custom hash code?
 » 3 months ago, # |   0 The tasks were very interesting
•  » » 3 months ago, # ^ |   0 Bad tasks, if they copy exact previous problems for just hosting a contest. :(
 » 3 months ago, # |   0 Is this round unrated?
 » 3 months ago, # |   0 Hey there, why does the order of the dominoes matter in problem E? Also is it even possible to solve this question and other these type of questions without graph?
 » 3 months ago, # | ← Rev. 3 →   0 My approach for problem E (Without using Graphs/tree/dfs/dsu)Travel in all pairs and check for ith pairIf you can't put the ith pair in set 1 and set 2 both then : NOIf both numbers in pair is same then:NOElse If we can't put ith pair in set 1 then put in set2Else If we can't put ith pair in set 2 then put in set1THE MOST IMPORTANT : If we can put ith pair in set1 and set 2 both then Leave that pair for now.If all the remaining pairs can be placed in set 1 or set 2, put 1 pair of those remaining pairs in set 1 or set 2 and repeat this process again and again until all pairs are placed in set 1 or set 2 CODE?#include using namespace std; #define ll long long int #define f(i, x, n) for (ll i = x; i < n; i++) #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) void solve(){ ll n; cin>>n; ll a[n],b[n]; f(i,0,n) { cin>>a[i]>>b[i]; } map mapi1,mapi2; std::vector visited(n+1,false); ll cnt=0; while(cnt!=n) { bool condition=false; S: bool is_any_pair_putted_in_any_set=false; f(i,0,n){ if(!visited[i]) { if(a[i]==b[i]) { cout<<"NO"<> t; while (t--) solve(); return 0; } 
•  » » 3 months ago, # ^ |   0 I had a question about the sentence” If we can put ith pair in set1 and set 2 both then Leave that pair for now.” Why I can’t choose any set and add the ith pair in. Can you make a case for why this way isn’t correct? Thanks
•  » » » 3 months ago, # ^ |   0 such as (1,2)(6,4)(3,4)(6,5)(1,5)(2,3)if you choose (1,2)(6,4) into first set, then WA
•  » » » » 3 months ago, # ^ |   0 Thank you very much!!
•  » » » 3 months ago, # ^ |   0 i have done the same before, but i got WA on test 3 . think about that {(1,2),(3,4),(2,3)} (i know ai,bi<=n .but for understanding take this example)if you put first pair in set 1 , second pair in set 2 then you will get NO because you will not be able to put 3rd in any set. but correct answer is yes.so we try to put all pairs that can't put in one set in second set. after doing that we will put 1 pair from remaining in any set.
•  » » 3 months ago, # ^ |   +1 sad to say, seems to get tle on some cases. suppose input is (1,2) (3,4) ... (n-1,n) (1,2)(3,4) ... (n-1,n) every pair can fit in both sets, and if you choose (1,2) into the first set, the only step your method can do is add another (1,2) into the second set, and have to loop again and again.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 constraints: ai,bi<=n i think that we will never get such cases
•  » » » » 3 months ago, # ^ |   0 i don't think the case break the constraint let n = 100first 50 pair are (1,2) (3,4) ... (99,100) last 50 pair are (1,2) (3,4) ... (99,100)isn't it
•  » » » » » 3 months ago, # ^ |   0 you are right , for your test case time complexity is O(n*n), that leads to tle for sure.
 » 3 months ago, # | ← Rev. 3 →   0 Why can't my code?Why is this question E used Kruskal？ Can you look at my code?thanks. linK:https://codeforc.es/contest/1702/submission/163631990
•  » » 3 months ago, # ^ |   0 I'm not sure that Kruskal is needed, I think any valid set of nodes either needs to be a path or an even cycle.