### antontrygubO_o's blog

By antontrygubO_o, 3 years ago, translation,

Hello again, Codeforces!

I am glad to invite you to Codeforces Round 580, which will take place on Aug/18/2019 16:45 (Moscow time). Round will be rated for both divisions.

All problems in this round were created and prepared by me, antontrygubO_o. I tried to make them interesting and hope that you will enjoy them!

A lot of thanks to arsijo for the excellent coordination of the round, mhq, gepardo, danya.smelskiy, re_eVVorld, Xellos, Mediocrity, I_love_tigersugar, KAN for the testing and valuable comments, and to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon.

Participants in each division will be offered 6 problems and 2 hours 10 minutes to solve them. As usual, I strongly recommend reading statements of all problems!

I wish you good luck and high rating!

UPD1:

Scoring distribution of Div $2$ round: 500 — 1000 — 1500 — 1750 — 2250 — 3000

Scoring distribution of Div $1$ round: 500 — 750 — 1250 — 2000 — 2500 — 3000

UPD2:Editorial

UPD3 Congrats to winners!

Div 1:

1. TLE

2. Um_nik

3. mnbvmar

4. Benq

5. slime

Div 2:

1. kkkkk11

2. sucuk

4. zzffxx

• +1343

 » 3 years ago, # |   +134 What are my chances of becoming a legendary newbie candidate after this contest?
•  » » 3 years ago, # ^ |   +26 0.5
•  » » 3 years ago, # ^ |   +48 i know it
•  » » 3 years ago, # ^ |   +80 What chance that problem on a heavy cycle flow centroid decomposition on bitsets will appear in the contest?
•  » » » 3 years ago, # ^ |   +21 If you decide to submit some of that, it will definitely appear in the contest.
•  » » » 3 years ago, # ^ |   -18 See.. This is the type of question that drives an innocent ass Titan down the path of Thanos
 » 3 years ago, # |   +6 What to do a Sunday evening, take a walk with friends or write a contest from antontrygubO_o? Of course I will write a contest from antontrygubO_o)
•  » » 3 years ago, # ^ |   +150 This Sunday life -17:30 IST — Participate in ABC.19:05 IST — Participate in CF Round.21:30 IST — Participate in Cook Off.
•  » » » 3 years ago, # ^ |   +13 Very busy indeed :) What's an ABC btw?
•  » » » » 3 years ago, # ^ |   +30
•  » » » » » 3 years ago, # ^ |   0 Oh okay! Thanks, will do...
•  » » » 3 years ago, # ^ |   -17 00:00IST rip
•  » » » 3 years ago, # ^ |   -18 I have a quiz of algorithms the next day. :(
•  » » » 3 years ago, # ^ |   -19 *Goldman Sachs
•  » » 3 years ago, # ^ |   -15 Dry and wack. Try again
 » 3 years ago, # |   +3 When you are waiting for the contest on codeforces and suddenly codeforces announced there will be a contest :)
 » 3 years ago, # | ← Rev. 2 →   +18 Unfortunately, the Atcoder Beginner Contest 138 conflicts with this for 5 minutes. Is it possible to shorten the ABC or shift this contest by 10 minutes? (Mentioning chokudai for the ABC)
•  » » 3 years ago, # ^ |   +308 We decided to do the following: The contest will be shifted by 10 minutes. The contest length will be 2 hours and 10 minutes. Therefore, there are 5 minutes between ABC and CF and other 5 minutes between CF and Cook-Off.
•  » » » 3 years ago, # ^ |   +52 Thanks! I know it's hard scheduling with contests on different platforms. I appreciate all the hard work you and the CF team do!
•  » » » 3 years ago, # ^ |   +6 Thank you for your kindness.
•  » » 3 years ago, # ^ |   +24 That's ABC 138, not 038.
•  » » » 3 years ago, # ^ |   +6 Thanks haha, fixed the text.
 » 3 years ago, # |   +37 Usually I keep my vote after the contest is over, but for this one I will give you my up-vote now just for the lovely image <3
 » 3 years ago, # |   +38 Good luck to all of you!Btw,wish I can become a candidate master.What I need is only +1 rating.I think I can achieve that:D
•  » » 3 years ago, # ^ | ← Rev. 2 →   -35 。。。
•  » » » 3 years ago, # ^ |   +8 Why not? You can have a try!!
•  » » 3 years ago, # ^ |   -34 You will not get it
•  » » » 3 years ago, # ^ |   +17 hello,do not discouraging any others from candidate masters,, this person has a greatest chance at a candidate master,generally a rule if u wish other persons to get a highest ratings as possible,, then u will also be high rating,wish u high rating, u can do it, rajeshwar~
•  » » » » 3 years ago, # ^ |   -17 No he will lose -100 delta in this Contest
•  » » » » » 3 years ago, # ^ |   +17 losing -100 deltaa, is that what you say,,yes that is, u have the lost -100 delta, but that is mean in it that he will gain! 100 delta,,this is type of thinking u must have, not about the "he will fail" because if u think he will fail u might also have a fail,,,,,therefore, you must wish a high rating, like i wish u and all other contestants to this round,,,,wish u high rating,,rajeshwar~
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +15 there's no need of arguing with those people who are always expecting others to lose rating and stuff.And also wish zrmpaul's rating can be greater than mine!
•  » » » » » » » 3 years ago, # ^ |   +8 wish zrmpaul become international grand pupil
•  » » 3 years ago, # ^ | ← Rev. 2 →   +22 Those people who says things like "you won't" and stuff are really annoying, zrmpaul may become purple if he has a try. And also it's really mean of them to say such words.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -7 [Deleted]
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +4 It has been deleted by the managers.
•  » » » » » 3 years ago, # ^ |   -8 66666!
•  » » 3 years ago, # ^ |   +41 Just imagine having a zero change. This will be legendary!
•  » » » 3 years ago, # ^ |   -6
•  » » » » 3 years ago, # ^ |   0 That's not what I meant. He needs just +1 to get purple, but getting a zero in such a situation is very rare. I personally have a contest with zero rating change, you can see that.
•  » » 3 years ago, # ^ |   0 good luck :)
•  » » 3 years ago, # ^ |   0 congrats...give me some good luck also for becoming an expert...
•  » » 3 years ago, # ^ |   0 Congrats..!
•  » » 3 years ago, # ^ |   0 Good job!
 » 3 years ago, # |   +22 Hope I can become a master after this contest even if the probability is so small.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -34 [deleted]
»
3 years ago, # |
-54

Spiderman: Wherever I go, I see Iron Man. Me: Wherever I go, I see tourist.

# BestMotivation.

•  » » 3 years ago, # ^ |   0 LOL Motivation :3
•  » » 3 years ago, # ^ |   0 So who's Mysterio?
 » 3 years ago, # |   +25 Div 1 orz
 » 3 years ago, # |   +27 First div 1 Round for me and hope the result won't be bad:)
•  » » 3 years ago, # ^ |   +7 Me too! I hope that I won't be Expert again after this contest. Good Luck!
•  » » » 3 years ago, # ^ |   +13 GLHF
 » 3 years ago, # |   +43 Every time I see a Division 1 contest, I get excited about it, participate in it and end up in Division 2. But that does not stop me from participating in Division 1 again. :)
•  » » 3 years ago, # ^ |   0 I wish to have the same spirit for a long time :)
 » 3 years ago, # |   0 Wow, I didn't know you created rounds too! Will participate using your vscode extension for sure
 » 3 years ago, # | ← Rev. 7 →   +11 Participants attending the contest at 23:45PM https://i.imgur.com/KxJ7aAI.gif
•  » » 3 years ago, # ^ |   0 It says image not found for me.
•  » » » 3 years ago, # ^ |   0 updated
 » 3 years ago, # | ← Rev. 3 →   +3 i hope i can do well, good luck for all
 » 3 years ago, # |   +10 three consecutive contest for me today :)
•  » » 3 years ago, # ^ |   +3 I find it really hard to focus for that long. I've tried doing two contests in a day before and that didn't end well; this is just crazy :o
•  » » » 3 years ago, # ^ |   +5 i once did 2 consecutive before, and my performance in second was better than usual . So i am gonna try three tonight XD
 » 3 years ago, # |   -33 I am late to comment this time.
 » 3 years ago, # | ← Rev. 2 →   +4 Well!This contest started early (relative to most other contest). I think I will have better energy to solve the problems in this contest.
 » 3 years ago, # |   0 I worked all Day in constructions thinking about this contest. Hope it will worth.
 » 3 years ago, # |   +3 That 10 minutes can be lifesaver :)
 » 3 years ago, # |   0 Ten minutes == (this->score += abs(y) && this.rating.delta += abs(x)) :)
 » 3 years ago, # |   +36 Programming Final tomorrow! ^_^ Probably my last contest:)))
 » 3 years ago, # |   +3 I hope the problem statements are short and clear.
 » 3 years ago, # |   +3 Guys check this out: https://codeforces.com/blog/entry/68888
•  » » 3 years ago, # ^ |   0 a good blog's id in Chinese!
 » 3 years ago, # |   +3 GOOD LUCK
 » 3 years ago, # |   0 Participating in a contest after nearly 50 days. Hope this goes well!!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   -27
 » 3 years ago, # |   +18 Huge waiting times! please look into it.
 » 3 years ago, # |   +19 Long queue time anyone?
 » 3 years ago, # |   +17 Another $Queueforces$ Round!! :(
 » 3 years ago, # | ← Rev. 2 →   0 Two consecutive Queueforces. :(
 » 3 years ago, # |   0 I can't submit any answer. When I'm trying to submit, the web page say "You have submitted exactly the same code before". How can I solve this problem?
•  » » 3 years ago, # ^ |   0 try writing a comment and then submit
•  » » » 3 years ago, # ^ |   0 It doesn't work. It is not allowing me to submit even my first attempt. It is always showing "You have submitted exactly the same code before", but there is no submission in queue.
•  » » » » 3 years ago, # ^ |   0 try changing the name of a variable
•  » » » » » 3 years ago, # ^ |   0 It doesn't work too. The system always prints the same message even I submit "Hello, world". I hope it will not be reflected in my rating....
 » 3 years ago, # |   0 Guys, when would good tests appear?)
•  » » 3 years ago, # ^ |   0 yes, A contest with good problems on algorithm and datastructure with less/NO guess work or pattern finding stuff...
 » 3 years ago, # | ← Rev. 2 →   0 Could this round unrated or semi-rated?I tried to solve div1C,and I succeedBut then，the problem changed,and I got WA on test 1????
•  » » 3 years ago, # ^ |   +37 Actually it is a problem, but not a really serious one which can make the round semi-rated.It is solved after 6 minutes the contest starts.and not many people was doing C that time.By the way, actually it doesn't waste much time. Isn't it? :P
 » 3 years ago, # |   +4 Speedforces I miss the days when C was an interesting problem
 » 3 years ago, # | ← Rev. 2 →   +19 Absolutely love the feeling when I have to wait for 3 minutes in queue just to receive the verdict, wrong answer on test 1
•  » » 3 years ago, # ^ |   +1 I think it's fixed now.
 » 3 years ago, # |   +3 I am waiting for Julia to be supported to compete in these rounds.
 » 3 years ago, # |   +12 Mathforces?
 » 3 years ago, # |   +10 OMG...that didn't went well. How can everybody solve C and I do not see how?
•  » » 3 years ago, # ^ |   0 I think because there exists cheating cases in rounds and this problem was like find pattern and get AC. Can anyone prove it with math or etc?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I wrote a brute force that worked in n*((2*n)!), and found a pattern (Only used cases n<=5).
 » 3 years ago, # |   +4 How to solve D?
•  » » 3 years ago, # ^ |   +52 The idea is the same as Problem Source, Spoiler WarningIOI 2019 Day 1 SplitFirst, we solve for star graph. Choose a constant $C$ in the range [N/3, N/2], then assign edge weights 1, 2, ..., C and (C+1), 2(C+1), ..., (N-1-C)(C+1).How to solve for general graph? Root the tree at centroid. We claim that there exist a subset of children of the centroid so that their subtree sizes sum up to [N/3, 2N/3]. If one of the direct child of centroid has subtree size >= N/3, we're done. Otherwise, keep adding subtrees until the sum is >= N/3. Since each subtree size < N/3, total sum does not exist 2N/3.Now, we use the same idea as star graph within these two sets and we're done.
 » 3 years ago, # |   +7 Hey guys, how did you solve Div 2 D?
•  » » 3 years ago, # ^ |   +15 Let's ignore all vertexes with $a_i = 0$ because they never be in any cycle. So if there left more than something (I don't know exactly how many, choosed 500) that answer is 3. If there less vertexes then you can run $n$ bfs'es to find shortest cycle.
•  » » » 3 years ago, # ^ |   +22 Why downvotes? It's pretty correct solution.
•  » » » » 3 years ago, # ^ |   0 Yeah, I solved it this way — by limiting number of vertices (and I think 120 is enough). Maybe the downvotes are from people who had the idea to limit the number of edges (like in the editorial) and think this is wrong.
•  » » » 3 years ago, # ^ |   0 Thanks. But can anyone please explain the bit part I have no idea of binary represntation or bit may be thats why I didnt understand the solution. Can anyone please explain it easily from scratch. Sorry for my poor english. Thanks a lot :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   +20 The approach is simple compute for each bit i from 0 to 64, which all numbers have the i th bit set. Then if any of bit i have less than 2 numbers with that bit set, it will not affect and will not result to any connection. Otherwise if any of bit i have more than 2 elements, then the answer will be 3 always(take any 3 elements among those).The case rises when we have bits with 2 entries. So maximum edges resulting from these bits will be 64. Considering these edges we can use out edge removal approach explained here :Find minimum weight cycle in an undirected graphIf no cycle then answer will be -1.
•  » » » 3 years ago, # ^ |   0 i copy pasted the code, still got WA in test 5 XD
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0
 » 3 years ago, # | ← Rev. 5 →   0 [Delete]
 » 3 years ago, # | ← Rev. 2 →   0 How to solve Div2 D?If I used a vector to store the connected nodes I would get MLE.And after that I got TLE by searching in O(n) for the connected nodes :/https://codeforces.com/contest/1206/submission/59044914Can anybody please share his / her approach?
•  » » 3 years ago, # ^ |   0 If there exist three number with common bit you got the answer. Else build the graph which contains only few edges. Find shortest cycle in it.
•  » » » 3 years ago, # ^ |   0 How do you know which edges to include?
•  » » » » 3 years ago, # ^ |   0 Which have a common bit in them. And bits are just 18*log(10)/log(2).
•  » » » » » 3 years ago, # ^ |   0 Thanks a lot!
 » 3 years ago, # |   +28 Nice zeroes in D.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -11 Zero, nice body
 » 3 years ago, # |   0 is div 2 D based on that there will be max 18 edges ?
•  » » 3 years ago, # ^ |   +11 max 60
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 how ? i think for every bit there can be only one edge .if 3 or more nodes have a bit in common then it answer will be 3, right ?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 right, but there's like max 60 bits in 1e18
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 oh right, sorry my bad
 » 3 years ago, # |   0 can someone please tell me why my solution for E got WA?I tried on my terminal and it works fine I guess. Can someone please find the mistake?
 » 3 years ago, # |   0 Welcome to Speedforces!!
 » 3 years ago, # |   +8 I think, question Div2-C has some patterns about numbers but I could not solve it :( Could you guys tell me, if you've already solved it?
•  » » 3 years ago, # ^ |   +5 $a_i = a_{n+i} \pm 1$
•  » » » 3 years ago, # ^ |   +18 Thank you so much
•  » » 3 years ago, # ^ | ← Rev. 3 →   +8 Think about it as a window of length n. In one turn a number enter and a number leaves. Alternate the difference = number enter — number leaves between 1 and -1, you can find then when the condition will be impossible.
•  » » » 3 years ago, # ^ |   0 Thanks a lot
 » 3 years ago, # |   +4 The queue is dead, long live the queue!
•  » » 3 years ago, # ^ |   0 The queue is feeble during the contest. And now it's gone. R.I.P
 » 3 years ago, # |   0 Can anyone figure out what is the meaning of n odd in div2 E?
•  » » 3 years ago, # ^ |   0 if n is even, then the problem is much easier! (try to think about it)
•  » » » 3 years ago, # ^ |   0 Oh tks. I figure it out.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Please ignore
•  » » » 3 years ago, # ^ |   +13 Why is this true? Don't both corner squares still have the same parity?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Ah, you're right. I am misremembering stuff (I got pretests passed in last 10 seconds so adrenaline rush). My solution relies on the fact that there exists a 3x3 square in following pattern: patterns: 1xx xxx xx0 or 0xx xxx xx1 which is not necessarily true in even case, but true in odd case. Maybe that is author solution?
 » 3 years ago, # |   0 Div 2 D there these two pieces of code should be accepted :(
•  » » 3 years ago, # ^ |   +6 if (n < 500) { gate(); return 0; } puts("3"); Wrong. If there just 500 zeroes then answer is -1.
 » 3 years ago, # |   +9 Mathforces，Guessforces（
 » 3 years ago, # |   +14 Thank you so much for this contest! Although have not done my best but really enjoyed it. Love problem E!
 » 3 years ago, # |   +104 An outstanding round! Enojyed all the problems, especially D. My screencast will appear here as soon as it's processed.
•  » » 3 years ago, # ^ |   +56 Thanks :D
 » 3 years ago, # |   +86 Editorial is published!
 » 3 years ago, # |   +22 Really intriguing contest.With the fact that I will get -108 rating for this contest, I still give it my up-vote
 » 3 years ago, # |   +47 Why something like "Note that the graph does not contain parallel edges. Therefore, one edge can not be a cycle. A cycle should contain at least three distinct vertices." was accounced in B? It's clear that it has nothing to do with making statement clear since it is crystal clear in this matter, it's just a hint to the solution about supposedly popular bug.
•  » » 3 years ago, # ^ |   0 Oh really? I did not even pay attention to it lol
 » 3 years ago, # |   +4 Div2 D, E very good problems! Thanks for this round!
 » 3 years ago, # | ← Rev. 2 →   +32 Thanks for extending this contest by 10 mins than usual. Finally, in last 30 seconds D1C got AC and I became master after a long wait :)
•  » » 3 years ago, # ^ |   +21 Same shit bro!
•  » » 3 years ago, # ^ |   0 Told u, even 1 minute might be lifesaver :D
 » 3 years ago, # |   +3 For those of you who get WA on test 14 for problem D on Div 2. You probably add some edges more than once.
•  » » 3 years ago, # ^ |   +8 Realized it after 6 wrong submissions :(
 » 3 years ago, # |   +3 For problem D of Division 2, I would like to point out to everyone the existence of this problem: Problem: Find the Length.The problem asks you to calculate the length of the shortest cycle containing a given vertex. Furthermore, N, the number of nodes, is limited to only 300.How to limit the number of nodes you ask? In our problem, N can be 200,000! Well, for any given a_i, its representation in binary can be no longer than 60 characters long (2^60 > 10^18), the problem limit. Store the binary representation of the N numbers in an array, of dimensions Nx60. Now, we have two cases. If there are more than 2 ones in any single column of our 2D array, then it means that 3 or more numbers are all connected to one another. This means that the minimum cycle length is 3, so we can output 3 and end. Otherwise, the graph is extremely sparse. If there are only 2 ones in 60 columns, it means that there are a maximum of 120 ones in the binary representation of 200,000 integers! An integer must have at least 1 one in its binary representation. This means that, in the worst case, N is at most 120!At this point, problem D becomes identical to the other problem. Simply use BFS or Dijkstra's algorithm to solve the problem. The runtime will likely vary, but most runtimes on the reduced graph will pass.
•  » » 3 years ago, # ^ |   0 Note that the fact that a_i can equal zero can be a problem. Since 0 bitwise-AND with anything (including another 0) is 0, you can simply ignore that a_i.
 » 3 years ago, # |   +64 Thanks to this contest, I learnt that depth first search doesn't generate all simple cycles of the graph(which maybe a common sense for lots of people, but wasn't for me)
•  » » 3 years ago, # ^ |   +5 It implicitly does, you just need exponentially more time to actually find them.
 » 3 years ago, # |   +3 Got WA on test case 28 in Div2D. Can anyone figure out the mistake ? Link
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 you need to clear "vis" before every dfs, i had the same problem
•  » » » 3 years ago, # ^ |   0 I have refreshed the vis array.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Using DFS to search for shortest cycle in a graph doesn't work. Consider this graph: 1-2, 2-3, 2-4, 4-5, 5-6, 6-1, 6-3Say you start your dfs from 1 and it traverses like this:- 1->2->4->5->6->3Back-edges found are 6-1 and 3-1, both of which give longer cycle length.
•  » » » 3 years ago, # ^ |   -8 But dfs is done from all the vertices So it should find the smallest cycle.Right?
•  » » » » 3 years ago, # ^ |   0 Its all due order of adj vertexes.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 With enough bad luck, your order of vertices in adj list could be such that dfs can't find shortest cycle starting from any node.
•  » » » » » 3 years ago, # ^ |   0 Thanks. Got it !!
 » 3 years ago, # |   +8 Loved the problems: less coding, more thinking. But I was confused by the phrase "It can be shown that the answer always exists" in 1205C - Палиндромные пути. It led me to thinking that the answer is not unique — but there is actually no condition that it has to satisfy, so it was not clear how is our output validated (as soon as it does not contradict with out queries).I would phrase it like "Your set of queries should unambiguously determine all cells of the grid". Actually the first time I would appreciate something like "Vasya filled the grid with ones and zeroes, and you have to figure out the entire grid by asking him queries" :) Anyone had troubles with this or is it just me?
•  » » 3 years ago, # ^ |   +8 When the goal is to print a correct solution in an interactive problem, there must be at most one correct solution.My solution, which was "find 2 possible grids, find a query where they give different answers", makes it clear that you can decide if there are 2 indistinguishable solutions or a unique one. That's a big benefit of this approach.
•  » » » 3 years ago, # ^ |   0 True. My solution was exactly the same, it is just before the last step I started thinking: do I really need to choose between two? Probably I am just spoiled by no-brainer statements like in 1023E - Вправо или вниз.
•  » » 3 years ago, # ^ |   +8 Yes, I noted it as well that saying "It can be shown that the answer always exists" is a complete nonsense xD. Checker has some hidden board and answers some questions about it, such a statement makes no sense at all, it is not some constructive problem where answer satisfying some constraints may exist or not.
 » 3 years ago, # |   0 Could someone explain why am I getting an overflow error despite using long long which can store a number upto 10^18. This is my submission 59048621
•  » » 3 years ago, # ^ | ← Rev. 5 →   +1 use: ll nw = 1ll<
•  » » » 3 years ago, # ^ |   0 Thanks for the help. Could you help me figure out the reason for the TLE. I think my code should pass given the constraints. Thanks in advance 59052813
•  » » 3 years ago, # ^ |   0 long long has limitation as well. usually it's 64 bits. and if you try to shift number 4 (which in binary form looks like 100) 63 times — then you'll get an overflow. docs
•  » » » 3 years ago, # ^ |   +1 but he's saying 1<
•  » » » » 3 years ago, # ^ |   +1 my bad, didn't notice, that thought it was not i << j
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Just remember, every time you use long long and want to write a number like 1 or 0 put an ll after it like 1ll or 0ll
 » 3 years ago, # |   0 Long queue(4-5 mins) during the contest is an upsetting thing :(
 » 3 years ago, # |   0 Could someone explain why I am getting TLE. I think my complexity is within limits. Thanks in advance. Here is my submission 59052813
•  » » 3 years ago, # ^ |   0 Maybe :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Because you use cin. Add the following lines: ios_base::sync_with_stdio(false); cin.tie(0); Or use scanf();
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 because you wrote N^2. imagine a big TestCase where every number is the same and they're binery form is 1111.....111. in every DFS you look at all of them, even though you dont visit them. so N nodes visited in DFS, in which you look at all of the N other nodes to check them if you have visited or not, so N^2.
•  » » 3 years ago, # ^ |   0 there is a trick to this problem, don't want to spoil it, but imagine what would happen if you had 3 numbers who would share the same 1 bit an 100000 other nodes...... what would the answer be, and why? think :D
•  » » » 3 years ago, # ^ |   0 Are you hinting towards the fact that the dfs should be performed in order of component size for faster execution, If yes, how would that improve the time complexity. I still feel it would remain the same, ans is the answer to your question 3?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +1 yes the answer is 3. so in your vector vals[64] for every i if(val[i].size>=3) the answer will be 3 either way. so in worst case every one of them will have size 2, it means in worst case you would have 128 nodes in total. so..... you could make and Adj_List for those 128 nodes, so you only have the nodes you need and their relations.......
•  » » » » » 3 years ago, # ^ |   +1 Yeah I just understood the trick.But I don't know why my code is failing at Test case 75, I find everything fine. 59054630
•  » » » » » » 3 years ago, # ^ |   0 i checked the TC. I suspected that dfs wouldn't work for this problem, I'm actually suprised it got to TC75 :D if you draw the TC, you'll see what the problem is. but for how to solve the problem use bfs, and use the fact that bfs visits every node in shortest time possible while the edges are the same size, dfs doesn't have this property, it just merely visits every node. if you check the TC, you'll understand what I'm saying..... good luck :D
•  » » » » » » » 3 years ago, # ^ |   +1 I completely got what you said.Thanks for helping out so much and being so patient.
•  » » » » » » » » 3 years ago, # ^ |   0 no problem, happy to help :)
•  » » » » 3 years ago, # ^ |   0 i did not mean that about dfs, i just meant you have made number of edges in total something like N^2...... so dfs turns to (N^2+N)
 » 3 years ago, # |   0 can someone tell me the name of algorithms that solve the contest question? I would like to study them
•  » » 3 years ago, # ^ |   +10 For problem D,you can use floyd or tarjan to find the minmum circle
 » 3 years ago, # |   -19 In problem C the judge is not printing -1 for more than n^2 queries... wasted so much time thinking i am getting wrong answer instead of qle.. :(
 » 3 years ago, # |   +24 I wanna know whether the problem in Div.1 C has a solution when the element (1,1) isn't 1,element (n,n) isn't 0.For example,(1,1)=0,(n,n)=0.
•  » » 3 years ago, # ^ |   +13 Consider the grid where it's all 0s or the grid where it's all 1s. You can't distinguish these via any queries.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +25 Grids101011111and111110101are undistinguishable So 1 in top left and 0 in bottom right were important.
 » 3 years ago, # |   0 I'm rk1 in Div2 untill D&F FST.now I'm nearly rk1000 TAT
 » 3 years ago, # |   0 Why i am rated? I registered for the div2 contest 10 minutes after the start of the game！
•  » » 3 years ago, # ^ |   0 you're still an official participant.
 » 3 years ago, # | ← Rev. 4 →   0 how we can know the path that we ask in Problem E (div 2) ?antontrygubO_olike ? 1 1 3 3path A : (1,1) , (1,2) , (1,3) , (2,3),(3,3)path B : (1,1) , (2,1) , (3,1) , (3,2) , (3,1)the rule for move is known as move to right or down and both follow ruleso which one is correct ? i read problem statement like 5 times and i didn't find anything guided me to know which one is correct ...please help me ^^ and sorry for bad english ...
•  » » 3 years ago, # ^ |   0 If at least one of all the paths is palindromic, you will get 1, otherwise you will get 0