### antontrygubO_o's blog

By antontrygubO_o, 22 months ago, translation,

• +150

 » 22 months ago, # | ← Rev. 2 →   +43 My last hour of yellow name :(
 » 22 months ago, # |   +3 wow thank you for the fast editorial :D
 » 22 months ago, # | ← Rev. 7 →   +222 F can be solved in $O(n^4)$. And I guess it can be solved in $O(n^2)$ per test case.If $(a,b)$, then $(a+k-1, b+k)$ with $k\geq 4$ or $(a+k-1, b+k*(k+1)/2)$ with $k\geq 2$.There is a tree structure about the permutation, which is called 析合树 in Chinese, named or invented by CommonAnts. We can derive this result directly from the tree structure. You can see these two 1 2 in Chinese for details.And there are some similar problems with this combinatorial structure of the permutation, like NEERC 2018 I, and China Final 2018 B.
•  » » 22 months ago, # ^ |   +316 The Chinese have a Data structure for everything.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +51 Nobody:Chinese people: Let's make a Data Structure based on this problem.
•  » » 22 months ago, # ^ |   +23 I think it is PQ-tree?
•  » » » 22 months ago, # ^ |   0 no you can do it by segment tree
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +11 No, I think they look similar. PQ-tree tries to find a valid permutation with some given consecutive subsets, but “析合树” is to describe all consecutive subsegments of a permutation. The tree structure has two types of nodes, which are similar to Q-node and "P-node which is not Q-node" respectively. I mean, values of all sons of a first-type node (“合点”) are monotonic, and those of a second-type node (“析点”) form a simple permutation.I introduced the tree and an $O(n)$ algorithm to construct it for a given $n$-permutation on RAM (with linear RMQ). So that many such problems could be solved in linear time. For example, CF997E.In fact, this problem F could be solved in $O(n)$ time. We can make a valid permutation with at most $n$ items at first with greedy. After that, replace a leaf with remain items as a simple permutation. It's $O(n)$ by adjusting those conflicts of constant size (including corner cases of greedy, the extra one consecutive subsegment for the simple permutation and inexistence of a simple permutation of length $3$).Another similar structure I've ever seen is "separation tree for permutations". It only cares about the second-type nodes, and are for problems about simple permutations.A simple permutation is a permutation without consecutive subsegments.
•  » » » 22 months ago, # ^ |   +11 If a PQ-tree successfully constructs a permutation, it can be regarded as a virtual tree for a subset of nodes in the permutation's “析合树”, each Q-node is a first-type node “合点”, and each P-node can be either type, “析点” or “合点”, depending on which permutation you choose in construction.
•  » » 22 months ago, # ^ |   +23 Problem setter & tester be like
•  » » 22 months ago, # ^ |   +10 I also solved it with $O(n^4)$ preprocessing with $O(n^2)$ per test case — I know how to improve this to $O(n)$ but I didn't bother. This is my idea, I have no idea why but it seems to work:If there is a solution for some $n,k$ then there is also a solution such that you start from some "disorderly" permutation of length $m \leq n$, and then in $n-m$ steps you either append a new maximum element to the permutation or append the new minimum to the permutation. A permutation of length $m$ is "disorderly" if its beauty is exactly $m+1$. I used dynamic programming to track the longest "increasing subsegment" suffix of the permutation, this tells me how many new good subsegments are added when the new maximum is appended. Code: 59129441
•  » » 7 months ago, # ^ |   0 So my mans created his own data structure now
 » 22 months ago, # |   +8 Fastest Editorial I have seen in a while! Thanks :)
•  » » 22 months ago, # ^ |   +40 So fastest that it was pulished 2 days ago!
 » 22 months ago, # |   0 I was able to solve Div2: C with some example that I wrote in the paper. I was trying to understand the derivation of editorial, but I am not able to understand it. Can someone please elaborate it more like why n even always has no answer?
•  » » 22 months ago, # ^ |   +16 Consider taking some array from the circle. Then take next value and remove last value, on the same circle. The sum cannot stay the same, because that means what we removed and what we added is equal, and we cannot do that. So it either goes up or down by 1. Imagine sum increases by 1. We can write +1 near that number. After that, with same logic, next move has to decrease sum by 1, because increasing number twice gives us three numbers on blackboard: sum, sum + 1, sum + 2. So we can write -1 near that number. Now consider a circle with +1 and -1 instead of numbers. If it is odd, it starts and ends with same value — easy to see. And if it is even, is ends with different value and we are back at the sum. No two consecutive numbers (+1 or -1) must stay the same, as it is easy to see.
•  » » » 22 months ago, # ^ |   0 I didn't quite get the last paragraph of your answer, about the circle of -1 and +1. Can you elaborate a bit please? thanks in advance.
•  » » » » 22 months ago, # ^ |   0 Let's create second circle of the same size, but with +1 or -1 inside, instead of numbers we put in. If it has length of n, we can label its nodes from 1 to n inclusive. Even ones have same sign, and all odd — labeled ones have different sign. The only place when it could go wrong is connection of n'th node to the first one. If they are both odd, they will have the same value, and we don't want that, as we showed. So 1 is odd and n has to be even
•  » » » » » 22 months ago, # ^ | ← Rev. 2 →   0 but the question asked to check in 1 to 2n. it doesn't matter if n is even or odd the last node and first will have a different sign. please explain why the n even is not possible??
•  » » » » » » 22 months ago, # ^ |   +1 Yes, the borders work well since the circle is of even length. But there is another problem with even n.Consider doing one step around the circle I mentioned. Let's denote sum of all numbers on the circle S, and previous sum in our chosen interval A. The sum of elements we have not chosen will be B = S — A. If we get +1 as result, new sum is A + 1. What happens to B then? Since S stays constant, new B = B — 1. If we choose the second interval as initial one, we would have to write -1 on the next node. So if we have +1 on one side, then we need to have -1 on opposite side (and vice versa). If n is even, we get two sequences (+1 -1 +1 -1 ...) (+1 -1 +1 -1 ...) of length n each. Their first elements will have the same sign, which is contradictory
•  » » » » » » » 22 months ago, # ^ |   0 thanks bro.
•  » » » 10 months ago, # ^ |   0 Thanks bro
•  » » 22 months ago, # ^ |   0 Solution 59065438 How do you think ?
•  » » 22 months ago, # ^ |   0 Iv got a simple proof for that.If input is n we have 2n numbers to arrange .the sum of these 2n nos is s=2n*(2n+1)/2 =n*(2n+1).since 2n+1 is always odd,s depends on n.now if n is even ,s can be divided in two equal parts(eg 18+18 for n=4) which we dont want as sum of no two consecutive n nos can not be equal.so n is odd.
•  » » » 10 months ago, # ^ |   0 But some of two consecutive n nos can be equal to each other.
 » 22 months ago, # |   0 Is the answer to the bonus of Div1.A yes when k is odd
•  » » 22 months ago, # ^ |   -11 yes
•  » » 22 months ago, # ^ |   0 no. consider k=1
•  » » 22 months ago, # ^ |   0 When k=1,it is impossible to find such an answer
•  » » » 22 months ago, # ^ |   0 When $k=1, n=2$ it is possible
•  » » » » 22 months ago, # ^ |   0 You are right.I didn't think very carefully
 » 22 months ago, # |   -40 can someone please help me with my code. There is something strange.
•  » » 22 months ago, # ^ |   -20 Why downvote? I post it because I am not able to understand why it is not printing all the $n$ strings. I had run the last for loop n times. But in the output it is printing only 3 rows. If someone can help then Please help!
•  » » » 22 months ago, # ^ |   0 probably your code print something other than 0/1 (-1 or something)
 » 22 months ago, # | ← Rev. 2 →   0 Can someone explain me what is the logic of Div-2 C problem?
•  » » 22 months ago, # ^ |   0 Look for a pattern. Let's start simple. If k = 3, n = 6, "1 4 5 2 3 6" would be the solution. Look at 1 4 5. This equals 10 for first 3 numbers. Look at 4 5 2. This equals 11 for next 3 numbers. What did we do between both steps? We removed a smaller number to replace with a number that is 1+removed number. Look at 5 2 3. This equals 10 again for next 3 numbers. We removed a larger number and added a number that is removed number-1.By doing this we get a pattern of 1%n, (1+3)%n, (1+3+1)%n, (1+3+1+3)%n... Please correct me if I explained wrong.
•  » » » 22 months ago, # ^ |   0 Thank you very much.
 » 22 months ago, # |   0 Somebody pls check and tell what's wrong with my code for Div 2 problem B !! code
•  » » 22 months ago, # ^ |   +5 input : 3 -1 0 1 output: 1 yours: 3
•  » » 22 months ago, # ^ |   0 Try your code with case -2 0 2 the answer is 3, 0's distance to 1 and -1 is same so it does not makes any diffarence to make 0 1 or -1. So if the count of negatives % 2 is equal to 1 you can make that 0 with a zero. I couldn't look well to your code but it may be the wrong thing, I hope it helps.
•  » » 22 months ago, # ^ |   0 Currently, you are ALWAYS making 0 go to 1. However, 0 can also go to -1 for the same cost (1).
 » 22 months ago, # |   0 Can anyone explain how to solve problem Div2 D?? I am not able to understand the editorial...
•  » » 22 months ago, # ^ |   +1 I did it this way- The maximum number in the input is 10^18 which can be represented in 64 bits. The minimum possible cycle can be of length 3. If we have the xth bit set in any 3 numbers, then we are done! (all 3 will be mutually connected because of non zero "and") There are at max 64 bits. => If we have more than 128 non zero numbers (By PHP) in the array, then we will get a cycle of length 3.Now for <= 128 non zero numbers. We can check by actually making a graph. It will take O(m^2), which will be well within the bounds.
•  » » » 22 months ago, # ^ |   0 How do you come up with the "128 non-zero numbers" logic?
•  » » » » 22 months ago, # ^ |   +8 10^18 fits well inside 64 bits. We need a minimum of 3 set bits at any common position. By Pigeon Hole Principle if we have more than 64*2 = 128 numbers (non zero because zero has none of the bits set) then at least one of the position will have 3 set bits. (The bound of 128 can be made stricter if you calculate the exact number of bits needed to represent 10^18)
•  » » » » » 22 months ago, # ^ |   0 Thanks
•  » » » » » 21 month(s) ago, # ^ |   0 how does having >128 numbers guarantee that there will be at least 3 numbers having set bit at the same position? (I'm not saying the answer is wrong, i wanted to know how php is used here)
•  » » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 in this problem Max(Ai) = 10^18 which has 60 bits, and as they said > 128 numbers guarantee that there will be at least 3 numbers having set bit at the same position.what if i change Max(Ai) = 7 then it only has 3 bits and > 7 numbers guarantee that there will be at least 3 numbers having set bit at the same position. how can it happen?here is the example N = 74 4 2 2 1 1 4and then i convert all of them to Binary Form100100010010001001100sum of column: 3 2 2as you can see, at the last input, no matter what number you add (as long it <= 7), the sum of column will be >= 3
•  » » » » » » » 20 months ago, # ^ |   0 i had already figured it out but thanks!
 » 22 months ago, # | ← Rev. 2 →   -8 For the problem, Shortest Cycle ,in the test case with n=10^5 and large numbers, making an adjacency list is causing Memory Limit Exceeded Error. How to prevent this?Edit: Just note if too many edges (thus giving memory limit exceeded) then there is a triangle.
 » 22 months ago, # |   0 div1 a. i noticed a beautiful pattern by connecting numbers on circle sequentially. my solution was 0 3 4 7 8..., i.e., +3 +1 under modulo 2*n,now join 0->1,1->2..2*n-1->1and so on it makes flower like pattern on paper.really amazed after seeing that.
 » 22 months ago, # |   +1 Thank you for your challenging problems and educative tutorials! But I was caught with some trouble at problem D... 59056716 I tested this submission with test 15 both on my local Windows machine and codeforces custom invocation. Both are resulted in 3. But every attempt to submit turned out to be Wrong answer on test 15...
•  » » 22 months ago, # ^ |   0 OH I thought I have made some mistakes...
•  » » 22 months ago, # ^ |   0 Maybe I pasted some other test data by mistake... Finally I found out my fault, then I formed a bfs tree, to judge the size of rings by LCA！[submission:59058541]
 » 22 months ago, # |   0 For 1206 D, 1205 B Another way, If the no. of non-zero elements > 120 ( 2*log2(10^18) ) then we must surely have a 3-cycle. Otherwise, for all vertices v, do BFS traversal to find length of shortest cycle through v and take minimum. This will be in O(V*(V+E)) time and O(V+E)(max O(V*V)) memory. Not much efficient though.
•  » » 22 months ago, # ^ |   0 My solution 59056716 is very close to that, but I strangely recieved a WA on test 15, while I surely got the correct answer in codeforces custom invocation...
•  » » » 22 months ago, # ^ |   0 Custom Invocation gives 5!=3.
•  » » » » 22 months ago, # ^ |   0 Awwww I see... I'm going to keep debugging...
•  » » » » 22 months ago, # ^ |   0 Thank you! Finally I formed a bfs tree and judge the size of rings by LCA！[submission:59058541]
 » 22 months ago, # |   0 Why am I getting WA on test 5 59056925 in problem D ? I think I misunderstood the problem. Can someone show me how the answer for test 5 is 4 ?
•  » » 22 months ago, # ^ |   +2 Your massive a is int, but should be ll.
•  » » » 22 months ago, # ^ |   0 Thanks. It worked.
 » 22 months ago, # | ← Rev. 3 →   0 In Div-2D, can someone explain why using set as Adjacency list gives AC int the following code 59059506 whereas using Vector as Adjacency list gives WA in this code 59057776
•  » » 22 months ago, # ^ |   +1 Given that you are getting WA on TC 14, it is probably because two values can share more than one bit, so the vector representation would have multiple edges going between the same two nodes, which would allow a cycle of length two.
•  » » » 22 months ago, # ^ |   0 Yeah, got it. Thanks.!!
•  » » » » 22 months ago, # ^ |   0 In problem D of div 2, I am getting TLE, in a test case where each input is 0, so basically I am getting TLE while reading 10^5 numbers, which are zeros. code: https://codeforces.com/contest/1206/submission/59088647
 » 22 months ago, # |   +2 Finally I left div2.. Nice problems, but solving them from smartphone is incredible as usual :(
 » 22 months ago, # |   +25 For div2,D If the number of non_zero numbers is more than or equal to 119 ,we can just output 3.（Pigeonhole Principle,think of each bit as a pigeonhole,and think of each non_zero number as a pigeon） If it is less than 119,we can just use Floyd algorithm,we can solve it in O(n^3).This might be a little bit easier to understand.
•  » » 22 months ago, # ^ |   0 In problem D of div 2, I am getting TLE, in a test case where each input is 0, so basically I am getting TLE while reading 10^5 numbers, which are zeros. Strange!! code: https://codeforces.com/contest/1206/submission/59088647
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 I tried to implement Floyd in the contest but failed coz I discover a problem: say there's an edge u -> v, Floyd will find a cycle path of "u -> v -> u" coz this is an undirected graph. And I don't know how to counter this problem. Do you know if there's any tweak I can do to make Floyd work?
•  » » » 22 months ago, # ^ |   0 http://codeforces.com/problemset/submission/1206/59043624 This is my solution.I hope it can help you.
•  » » » » 22 months ago, # ^ |   0 Thanks for the reply, is it ok for you explain these two lines of code?  for(int i = 0;i < k;i++) for(int j = 0;j < i;j++) 
•  » » » » » 22 months ago, # ^ |   0 It's not quite easy to explain. It's just a way to avoid the situation you said above.
•  » » » » » 22 months ago, # ^ |   0 Kindly explain the above lines if you have understood them!
•  » » » » » » 22 months ago, # ^ |   +1 This loop is essentially enumerating all the pairs that satisfies 0 <= i,j < k. The shortest path between any pair can only include Vertex 1 ... Vertex k — 1 according to the property of Floyd algo. So here we can enumerate all the cycles that contains Vertex 1 ... Vertex k. When k iterate from Vertex 0 to Vertex n, we basically covers all the possible cycles in the graph.
•  » » 22 months ago, # ^ |   0 Can you please explain how to use Floyd's algorithm for finding the shortest path? (I read somewhere it couldn't be used for undirected graphs). It would be of great help. Thank You.
•  » » » 22 months ago, # ^ |   0 http://codeforces.com/problemset/submission/1206/59043624 This is my solution.I hope it can help you.
•  » » » » 22 months ago, # ^ |   0 What is the logic behind (mincircle = min(mincircle,d[i][j] + e[j][k] + e[k][i]) this line? and Thank You for your help.
 » 22 months ago, # |   0 Can someone explain me the proof of div2 C,i basically did some cases and realized that if the number is even there is no solution, but i cant prove it.
•  » » 22 months ago, # ^ |   0 "Now, if n is even, we get a contradiction, since ai+n−ai=−(a(i+n)+n−ai+n)ai+n−ai=−(a(i+n)+n−ai+n), but due to the alternating they must be equal."
 » 22 months ago, # |   +12 Problem B.Div2 is interesting.59065083 :D
 » 22 months ago, # |   0 Hi could someone tell me why this is failing for "Make Product Equal One" https://codeforces.com/contest/1206/submission/59025115 locally I'm getting correct answer for the same input, is it some IO issue with Golang?
•  » » 22 months ago, # ^ |   0 int -> long long ??
•  » » » 22 months ago, # ^ |   0 Thank you, now it's solved when I made it int64 https://codeforces.com/contest/1206/submission/59126313
 » 22 months ago, # |   0 Also, what you could do in DIV 2 problem B was to first find the cost to convert all the numbers (ie. arr[i]) to 1 (ie. costOne) and -1 (ie. costMOne) and let the difference between the cost to convert to 1 and to -1 be c[i] (costOne — costMOne) for the element arr[i]. This means that you have 2 sets of numbers, first : the set which is closer to 1 (ie. arr[i]>0 or c[i]<0) and the second : the set which is closer to -1(ie. arr[i)<=0 or c[i]>=0)Assume all elements to be closer to 1 and convert all the elements to 1 (ie summation of abs(arr[i] — 1) ) which assigns the value 1 to the current total product 'totalProduct'. Now, just convert those numbers that were closer to -1 (ie. arr[i]<=0 or c[i]>=0). Meaning, you now have to greedily remove EVEN number of elements such that your product in the end still remains 1 (ie. sort c[i] in descending order and remove EVEN maximum number of elements you can from it. let the number of elements in c be n, so remove n elements if n is even or n-1 if it is odd). Removing these elements from c means decreasing the value of totalProduct by c[i] for each element removed. This is in asymptotic O(n) time.
 » 22 months ago, # |   0 In Problem D, I first checked for the 3 length cycle case as given in editorial and then I'm finding the minimum length cycle for the other case by taking each vertex as root and seeing if it is in the cycle or not, cases with some non-zero inputs and n = 100000 are passing but the case with all zero inputs and n = 100000 is giving TLE. I'm unable to understand why in case of all zeros it is giving TLE.Submission — 59060203
•  » » 22 months ago, # ^ |   0 Instead of declaring vis and par vectors of size n every time in the loop, declare map of vis and par and for each iteration of loop, clear both the maps. Hope this helps.!
•  » » » 22 months ago, # ^ |   0 Yeah it helped, thanks. But yet I'm unable to understand why previous thing didn't worked.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 I am getting TLE, in a test case where each input is 0. https://codeforces.com/contest/1206/submission/59088647
 » 22 months ago, # |   +11 Can someone explain the first approach of div1C in more depth? Apart from the dp part. Thanks in advance.
 » 22 months ago, # |   0 Div1 D solution doesn't seem natural I think.
 » 22 months ago, # |   0 How can solve 1D in $O(n)$? I think "divide the subtrees of the childs into two groups" need $O(n\log n)$...
•  » » 22 months ago, # ^ |   0 Oh, I know...
 » 22 months ago, # | ← Rev. 2 →   0 In problem D of div 2, I am getting TLE, in a test case where each input is 0, so basically I am getting TLE while reading 10^5 numbers, which are zeros. Strange!! code: https://codeforces.com/contest/1206/submission/59088647
 » 22 months ago, # |   +1 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 :)
•  » » 22 months ago, # ^ |   0 So assume a bit can hold either a 0 or a 1. Basically its a digit within a binary sequence. If you know base conversion from binary to decimal, then you understand that 2^60 is roughly greater than 10E18. This also means that you can have a total of 60 binary digits (aka bytes).Now, the AND operator returns true if any byte overlaps with a 1. Now, note this: You can only have 60 non zero numbers that do not have any byte overlaps. If you have greater than 60, then you are guaranteed at least one byte overlap. Now, if were to assume each byte has an overlap once with another number's byte, then we would have 120 non zero numbers. Any number added beyond 120 non zero numbers would mean, 2 overlaps for a certain digit. This would mean the shortest cycle is 3.If you have < 120 non zero numbers, then you can use BFS on each vertex to find the shortest cycle.
 » 22 months ago, # |   0 Many of you can't solve Div2 C. When you need to construct an array to solve a promblem,just construct it boldly. Don't be afraid.For this problem, let v be some number of the array(a[i]),let v' be the number opposite v(a[i+n]). Then the circle was cut into halves.let s1 = a[i+1] + ... + a[i+n-1],s2 = a[i+n+1] + a[i+n+2] + ... + a[i-1]. if n is an even number,it means that 2 is a divisor of the sum of all numbers,let it be 2k. The sum of any n consecutive numbers must be k.So,v + s1 = k,v' + s1 =k.v = v'!It's impossible.if n is an odd number,it means that the sum of all numbers can be written as 2k+1. Then |(v + s1) — (v' + s1)| must be 1.It means v — v' = 1 or -1. Just construct it boldly.I said to my self when I was trying solving this. What we want is for any i,s1 = k or k+1.Now we have n groups:(1,2)(3,4)...Why not let s1 for v = 1 1 + 4 + 5 + 8 + 9 + 12 + 13 + ... ? (We choose the first one in the first group,second one in the second group,first one in the third group...)It can be proved right.I won't write down the proof.(I didn't prove the algorithm at all when I was participating the contest,but luckily my thought was corret. :D )The proof was already given in the editorial.(I'm a Chinese student,there might be some grammar mistakes.Please forgive me for this and upvote for me.Thanks.)
 » 22 months ago, # | ← Rev. 4 →   +28 Div1 Problem E can be solved in the time complexity of O(n log n) with Möbius inversion formula : let define that $[ P ]= \begin{cases} 1, & \text {if P is true} \\ 0, & \text{if P is false} \end{cases}$try to enumerate i1,j1 , whose gcd is d , and simplify the formula it with Möbius inversion now we have $Answer=\sum_{i_1,j_1\in [1,n-1],d=gcd(i_1,j_1)}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$ $Answer=\sum_{d=1}^{n-1}\sum_{i_1,j_1\in [1,n-1]}[d=gcd(i_1,j_1)]([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$using the inversion: $[n=1]=\sum_{p|n}\mu(p)\ \ ,\mu(x)is\ Möbius\ function$ $gcd(a,b)=d\ <=>\ gcd(\frac ad,\frac bd)=1$we can derive that $Answer=\sum_{d=1}^{n-1}\sum_{i_1,j_1\in [1,n-1]}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})\sum_{p|gcd(i_1/d,j_1/d)}\mu(p)$ $\because p|gcd(i_1/d,j_1/d)<=>pd|i_1\ and\ pd|j_1$ $\therefore Answer=\sum_{d=1}^{n-1}\sum_{pd  » 22 months ago, # | 0 Can anyone pls prove this in Div1E?The case of i1+j1≤n is obvious: in this case, by subtracting and adding i1,j1 we can show that the string has period gcd(i1,j1), in this case comps=gcd(i1,j1). We now consider the case when i1+j1>n.`  » 22 months ago, # | 0 Can someone help me figure out the complexity of D problem. There could be at max 60 edges and for each edge we perform a BFS to find the shortest distance between its end points. And there are n vertices, so total complexity of performing repeated bfs would be 60^2*(n+60). And in order to construct the graph the work would be n*(log10^18) so overall — n*(log10^18) + 60^2*(n+60). Could someone tell me if my analysis is correct. Thanks in advance. •  » » 22 months ago, # ^ | 0 No!! There are at most 60 edges in a graph and removing each edge and doing bfs would cost me at most 60 operations . so overall our complexity would be (60)^2. You could have also used bellman ford for this but there time complexity would have been (60)^3 in worst case. •  » » 22 months ago, # ^ | ← Rev. 4 → 0 60 edges can connect at most 120 vertices. So rest of the vertices have zero degree, you don't have to do BFS on them. For example, you can do BFS on the connected component of source only. So my guess is, depending on the implementation the complexity may vary. •  » » 22 months ago, # ^ | 0 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 :)  » 22 months ago, # | 0 Anyone got the answer for the above chanllenge (1205A)? I dont see any comments about it  » 22 months ago, # | 0 Can anyone please explain to me how to find the shortest cycle using the Floyd Warshall's algorithm?? •  » » 22 months ago, # ^ | ← Rev. 9 → 0 Define$dp[i][j][k]$as the shortest path from$i$to$j$using upto prefix$k$of vertices, then shortest cycle length is$dp[i][i][n]$.So basically you find the shortest path from vertex$i$to$i$itself. Make sure during initialization you set,$dp[i][i][k] = \infty, \forall k \in [0, n]$and during transitions, avoid going from$i$to$i$through$i$(Well, actually this happens automatically if you set$dp[i][i][0] = \infty$).(Prerequisite: Basic version of Floyd Warshall)Setting$dp[i][i][0] = \infty$is mathematical way of saying that there is no path from vertex$i$to$i$without going through any vertex.EDIT: This only works for Directed graphs, in undirected graphs, this won't work(Since each edge of Undirected Graph == 2-length cycle of Directed Graph), see explanation here, https://qr.ae/TWreWj •  » » » 22 months ago, # ^ | +6 I did not understand what did you mean by "upto prefix k of vertices", could you please explain that part in detail?. It would be of much help. Thank You. •  » » » » 22 months ago, # ^ | ← Rev. 3 → +1 Prefix$k$of vertices, means possibly using vertices from set {$\,1, 2, 3,..., k$}.Read more details from Wikipedia, https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Algorithm  » 22 months ago, # | ← Rev. 3 → 0 For Div 2 D, can I assume that finding the MST and adding one of the remaining edges will give the shortest cycle?If not, why? Thank you.  » 22 months ago, # | 0 DIV 2 1206 C PROBLEM: I can't understand editorial's last line, can any one help me. Please: If n is odd, then it's now easy to build an example: for i from 1 to n ai=2i−1, ai=2i, if i is even, and ai=2i , ai=2i−1 if i is odd.  » 22 months ago, # | +3 How does the checker work fast enough to determine whether there exists a palindromic path if I query distant points in Div.1 problem C? •  » » 22 months ago, # ^ | ← Rev. 2 → +10 I come up with an idea look at this :if dp[i][j][k][l]=1 means there is a Palindromic Paths from (i,j) to (k,l),0 otherwise.update: dp[i][j][i][j]=1,dp[i][j][i+1][j]=(a[i][j]==a[i+1][j]),dp[i][j][i][j+1]=(a[i][j]==a[i][j+1])if(a[i][j]=a[k][l]) dp[i][j][k][l]=dp[i+1][j][k-1][l]|dp[i+1][j][k][l-1]|dp[i][j+1][k-1][l]|dp[i][j+1][k][l-1];elsedp[i][j][k][l]=0;Do you think it's right? •  » » » 22 months ago, # ^ | 0 And complete is O(n^4),it's fast enough  » 22 months ago, # | 0 Could anyone please explain the second solution of Div.1 C more clearly?"Thus, the algorithm is as follows: choose any path between$(1,1)$and$(4,4)$, find on it four cells with a xor of numbers equal to$0$, and ask a question about it."Why does there exist a path from$(1,1)$to$(4,4)$such that the xor is equal to$0$?  » 22 months ago, # | 0 How did you guys come up with generating the sequence for odd numbers in Problem C-Almost Equal?  » 22 months ago, # | ← Rev. 2 → 0 http://ideone.com/5bc3Ib code if you don't understand any solutions and explanations of Div2 C problem like me(just brute force which shows you valid sequences)  » 21 month(s) ago, # | 0 for B wouldnt the answer always be 2 since if a[i] & a[j] != 0, then in the graph there will be an edge of weight 1 from i to j. since a[j] & a[i] != 0 as well. we will get an edge from j to i, which is a back edge of weight 1. this would mean the shortest cycle is of weight 2 always? •  » » 21 month(s) ago, # ^ | 0 In the announcement they mentioned this :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. •  » » » 21 month(s) ago, # ^ | 0 didnt read the announcements, thanks  » 21 month(s) ago, # | ← Rev. 2 → 0 .  » 21 month(s) ago, # | 0 Can someone please explain the Problem 1205B(Shortest Cycle) ; I am unable to understand the editorial , It would be helpfull if someone explains it in a simple way . Thanks in advance !  » 21 month(s) ago, # | 0 Useful for 1206C/1205A  » 19 months ago, # | 0 antontrygubO_o In the editorial of problem F, the part with "statement 1" and "statement 2" are duplicated.  » 19 months ago, # | ← Rev. 3 → 0 Cool.  » 13 months ago, # | ← Rev. 2 → 0 For div1.B, why does this TLE give TLE for input with 1e5 0s, which forms an empty graph, while this gives AC.  » 10 months ago, # | 0 Regarding 1206B: I'm getting a wrong answer on the 7th test. But on my system I'm getting the correct answer.Here is the link to my submission 89636952I have tried using unsigned long as well but still didn't get accepted.Thanks in advance !  » 3 months ago, # | 0 Could anyone prove an upper-bound of the answer to Div1D? Is$\frac{2}{9}n^2+O(n)\$ optimal?