PikMike's blog

By PikMike, history, 6 months ago, translation, In English,

1093A - Dice Rolling

Tutorial
Solution (Vovuh)

1093B - Letters Rearranging

Tutorial
Solution (Vovuh)

1093C - Mishka and the Last Exam

Tutorial
Solution (PikMike)
Naive (PikMike)

1093D - Beautiful Graph

Tutorial
Solution (Ajosteen)

1093E - Intersection of Permutations

Tutorial
Solution (PikMike)

1093F - Vasya and Array

Tutorial
Solution (Ajosteen)

1093G - Multidimensional Queries

Tutorial
Solution (BledDest)
Solution (PikMike)
 
 
 
 
  • Vote: I like it
  • +55
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone link this editorial to the contest materials?

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the Intersection of Permutations editorial in more detail?

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    You can read about 2D-BIT at topcoder.

    The idea about offline trick comes from the treap implementation. With treap you would do something like: for each BIT x in query sum up the amount of numbers which are less than or equal to y. Imagine processing the same thing with BIT. At first glance it seems like you would need to do operations "add 1 in y" and "get prefix sum up to y". However, you don't need all the points up to max coordinate. You can compress the numbers in each BIT and find needed position with binary search.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      deleted

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      PikMike I have solved D with dp and am very proud of myself as it took me 2 hours to figure out the dp state . Here is my submission 51760005

      Don't downvote just wanted to share another approach. If there is any component which is not bipartite then the answer is 0 as it means graph contains a cycle of odd length and we can never satisfy the condition otherwise I stored in dp[i] the number of ways when we put 1 in ith vertex , 2 in ith vertex , and 3 in ith vertex .

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help me why I m getting Runtime Error On Test Case 9 in The Most Discussed Beautiful Graph Problem My solution.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me why I got TLE in problem D? Here's my submission. Thanks a lot!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Number of test cases = 3e5, and for each test case you memset the whole colour array and first array, which are also 3e5.

    It is stated that it is guaranteed that summation N over all test cases doesnt exceed 3e5, so for each test you should manually loop on array 0->n and clear it yourself, which gives a total accepted complexity of 3e5 over all test cases.

    Here is your 47162894 updated :D

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for your detailed explanation, which helped me a lot :D

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Its okay :D, I also got time limit for this reason in the contest :(

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It's giving me runtime error on Scanner Class.

https://codeforces.com/contest/1093/submission/47155880

Every time I got stuck with this scanner shit.Please give me any alternative.

»
6 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Is there a recursive(with memoization) implementation of Problem F? I didn't fully get the editorial.

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    You can code it recursively but it won't look easier. I can tell you my more straightforward approach.

    Let it be the same dp and sdp definitions. Now you want to update dp[i][lst] by making the last segment of value lst. That means that there is some position prv, where the segment of maximum length of value lst could start (this length is found with len and position of the rightmost element not equal to  - 1 or lst.

    Thus you want to sum up all the dp[j][l] for j = prv... i - 1 and l = 1... k, that is sdp[j]. However, the previous segment couldn't end with lst, subtract dp[j][lst].

    Add a little bit of maintaining partial sums over both dp and sdp arrays and you'll get the same complexity.

    Code

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for your fast Editorials

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain to me why problem F's solution is right?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the reason behind solving 2^a+2^b in problem D ?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    The last sentence explains it? If the graph is bipartite then the only coloring exists (color vertices of the first partition white and the second is black). White is one of {1, 3}, black is {2}. That is 2size colorings. And then change white to {2} and black to {1, 3}.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hard to Understand the solution of D. What have changed if there were only two numbers 1 and 2(not 3).Please explain the reason for 2^a + 2^b .

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        1 and 3 are the same in terms of making pairs. So you can put either 1 or 3 on each vertex, that is 2 options. Thus it's 2size. With only 1 and 2 you'll have a single option for each vertex, it would be just 1.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Then why, 2^size for both parts. By your explanation it should be 2^a for one part(1,3) and simply 1 for another part(2).

          Can also you explain why res = res * cur for each iteration on Node in Code.

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            It is 2a for part {1, 3} and 1 for part {2}. But then you swap parts and color the first part {2} and the second part {1, 3}.

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks, I understood it clearly. Can you explain why res = res * cur for each iteration.

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The colorings on each connected component are independent, so we multiply their answers.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me out with my code? I did exactly what is mentioned in the tutorial however couldn't pass the second pretest during the contest. Here is the link to my code: https://ideone.com/jWlp4l

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Shouldn't fl be the other way around? The answer is 0 if at least one connected component isn't bipartite.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! Didn't take care of that. Thanks, it worked by changing fl the other way round. Was a little bit confused.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me out with my code? It kept getting Runtime Error on Test Case 10 in problem E. I'm using persistent segment tree and I can't find anything wrong with it. Here is my code. Thank you so much if you could help me figure out the problem.

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Another approach for problem F:

Let dp[i][j][k] : the number of ways of fill the firsts i elements where j is the last element and appear k times, this is O(N * K * N) in memory, but only need dpi - 1 for update dpi so the memory become O(N * K).

Looking what happen into the transition when a element x come? There is two cases:

x ≠  - 1: how the element is fixed dp[j][k] will be 0 except for j = x, more precisely dp[j] should be shift one position because all the ways of end with j increase by 1, and a new value should by put in dp[x][1], these value is such that l ≠ j , in other words all the ways of end with other element, and if dp[x][len] become greater that 0 then make it 0, because this is a invalid array.

x =  - 1: fix every possible element and do the same as for x ≠  - 1 K times.

So i need something that support insert one element in the front and delete in the back, and have the sum of all of it's values, this is possible with a deque!!!

Keeping K deque one for each possible element the transition can be done in O(K), and the time complexity become O(N * K).

For more details of the implementation see my code:

Solution
»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Can someone explain me, In the F problem.. Why are we subtracting dp(cnt-len,lst) as well and not only sdp(cnt-len). Thank you.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If you don't connect new correct segment of color lst with some previous one then you'll never break any conditions. And if optimal answer has these segments merged then you'll still visit this state.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      Where does this color come from? Are you saying that gray is much far from Red? :P

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem F... I still can not understand why the number of the bad status is sdpcnt - len-dpcnt - len, lst,can you explain it more specifically?Thx...

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyone,

Just wanted to say that this was my 1st rated competition on Codeforces and I am really enjoying the learning process. Also wanted to mention that everyone in the comment section are quite helpful and give constructive feedback, so thank you :) !

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

From what I understand, the soln for G will NOT work if the queries is asking for minimum distance, right? Is there some other way to solve it if the problem asks for minimum?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if((col[v] ^ col[to]) == 0) bad = true; anyone please explain the working of the statement from the editorial of BEAUTIFUL GRAPH??

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If two neighbor vertices have numbers 2 or {1,3} both then sum would become even. So it's checking this only. Like col[1]=1 and col[2]=1 then col[1]^col[2]=0.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any one can help me with graph problem. I have no idea how to get started

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one help me figure out why my submission is failing on test-case number 10 (for beautiful graph problem) https://codeforces.com/contest/1093/submission/47175967

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can please anyone explain me problem E editorial here, I am unable to get it even after reading the editorial. Please share any other approach if you have got. Thanks a lot, Problem Link...

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem E, I don't understand what the tutorial is talking about. What is "update in point and sum on rectangle"? And how exactly are we remunerating the numbers?

Edit: Finally got it, I was imagining you meant reordering rather than renumbering. So for example if

a = [5, 1, 4, 2, 3, 6] b = [2, 5, 3, 1, 4, 6] then the new b should be [4, 1, 5, 2, 3, 6], changing each number in b to the position of the corresponding element in a. So the first element in b becomes 4 because the index of 2 in a is 4.

»
6 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Despite what they said in the editorial sqrt decomposition is fast enough to pass E. General idea split a and b into chunks. Each chunk of b has a segment tree that keeps track of how terms the chunk has in common with all other chucks of a. Updates take , since you have to update at most four segment trees. For the other type of query you brute force part of the query so you only have to deal with intersections between whole chunks of a and whole chunks of b. Then for each chunk of b contained in the query you use the segment tree to find the number of terms it has in common with all chunks of a contained in the query. Worst case complexity for queries is . Final complexity , and yes this is fast enough to pass. My code 47287195.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I used a similar sqrt-decomposition technique with BIT. One important thing to note is block size you choose can have a big impact on your runtime. For my implementation, I was updating the BITs for each block frequently, so it was advantageous for me to choose a larger block size. With a block size of , I was able to get it to run under 2000 ms, faster than the official soln. 47315299

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      That makes sense to use a larger block size. It seems like the trade off is between how far you travel to get to the ends and starts of blocks in the brute force part which favours a smaller block size and how many blocks you have to iterate over in the segment tree/BIT query part which favours a larger block size. The second part is more costly because there is an extra log factor when you do the queries. I suspect you could use calculus to figure out the optimal block size.

      For my implementation a block size is much slower (3931 ms) than (2558 ms). The best block size that I have found for my implementation is it gets (1825 ms) 47317374.

      It is interesting how a similar sqrt-decomposition approach can have such different optimal block sizes.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem D Can someone help me? My solution is giving TLE on test case 13 https://codeforces.com/contest/1093/submission/47291028

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1093A

https://codeforces.com/contest/1093/submission/47239530

Why was this solution not accepted? Can somebody help?

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

nice questions...

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody please explain why 2^a+2^b work in problem 1093D — Beautiful Graph.I need mathematical proof.Please help

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have two parts of size a and b, we want to proof that one of them should be totally odd and one of them should be even. We obtain this fact using induction on length of a path. We assume that vertices of this path should be like: odd,even,odd,even,... now erase the last vertex and we can apply to induction hypothesis, after that add this vertex and the erased edge. Since one of the endpoint of that edge is odd(for example), this vertex should be even. So for each two vertex in same part, they should be as same cause length of every path between them is even. Now there is two case: 1:part with a vertices be odd, we have 2^a to choose that every vertex should be 1 or 3. 2:part with b vertices be odd, we have 2^b like previous case.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for problem G, short and nice.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Need help for problem G, from what i understand from the tutorial, we will build 2k segment tree, each tree will be based on the value of , then we will take the maximum and the minimum of each 2k and take optimal distance as the result, is this right? and how can do this since each of |ax, i - ay, i| already has their fixed ci?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain me the last statement in pikmike solutions forn(mask, 1 << k) ans = max(ans, abs(bst[(1 << k) — 1 — mask] + bst[mask])); printf("%d\n", ans);

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In bst I have the minimum value for each mask (the values of ci of editorial). And I also know that ci will have all its signs turned if I replace 0 with 1 in mask and 1 with 0. That is the same as doing (2k - 1)^mask (or minus as I do). Thus bst[(2k - 1)^mask] will have the maximum value of mask but with multiplied by -1. I wanted to update the answer with (max - min) and I have min and ( - max). So I can do ( - ( - max) - min) or |max + min| (as I surely will have the non-negative value in a result).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In tutorial for problem G, should time complexity be for the code you give? I think they are quite different.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What makes you think that?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In your code, it cost you time on the segment tree and O(2k) time to modify or update bst after it for each modification or query. The time used when building the tree is O(n2k). Thus the time complexity is . To get the result , we could build 2k segment trees, and I got TLE when implementing this(my submission). Actually, the difference occurs when dealing with query and modification, one is each time and the other is , which makes me think they are quite different.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It costs me on both update and get queries. There are loops of 2k iterations on each of these functions. I also do have 2k segment trees, it's just the traversal order that differs. I have the other submission, which does about the same as yours and it works twice as slow. It seems, you should consider the time spent jumping around in memory while implementing it.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I got it. Thanks for your explanation and sorry to take up your time.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

While I (somewhat) understand how the solution to problem E works, and I've also read the article on Topcoder (about BIT, and another about RMQ),

I really don't understand how to come up with such a solution , the rectangle method seems quite non-intuitive .... can someone give any suggestions on this based on their own experience ?

Thanks a lot !

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    To be fair, problems of kind "answer something on a segment" don't come in lots of different forms. Like all of them are divided into:

    • precalculate something on prefix
    • segment tree
    • Mo

    This problem clearly doesn't fit into Mo category, prefix is also kinda weird here. Thus is probably segment tree or some other online structure.

    And there is another common trick. When you have several synchonized permutations but the exact values on them doesn't matter, you can renumerate one of them to identity permutation. I personally met this technique quite a few times.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi PikMike,

      Thank you for taking out the time to answer my question.

      Could you kindly clarify what you mean when you say "renumerate one of them" ? Do you mean getting rid of one of the permutations by finding a common property of the elements of the permutation (like in this question we reduce 2 permutation arrays to a single array by representing each number as a coordinate) ?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Yeah, essentially it is getting rid of one permutation. In some cases you can just abandon this one, in some you will still need it (but at least in will be 1, 2, ..., n). The latest problem on this trick I remember should be 1043D - Mysterious Crime.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for your replhy ... also, it was an interesting question so thank you for the problem as well.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Need help for problem G, from what i understand from the tutorial, we will build 2k segment tree, each tree will be based on the value of , then we will take the maximum and the minimum of each 2k and take optimal distance as the result, is this right? and how can do this since each of |ax, i - ay, i| already has their fixed ci?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't take arbitrary ci but the opposing ones. Take the easiest case — point x is larger on each coordinate than point y. Thus, you'll need cx be all ones and cy be all minus ones. However, for any other pair of opposing in each position values of c the sum will not exceed the appropriate pair. This concludes that the right values of cx and cy will have the maximum result of all candidates. The other cases of relative positions also follow the same principle.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the naive solution for Mishka and the Last Exam is not correct. It's getting TLE on the 9th test case. http://codeforces.com/contest/1093/submission/47462619 Or Should it get a TLE that's why it is the naive solution?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, it's TL but much simpler logic. That's why it's called naive.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain PROBLEM E in easier manner? i really confused.

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Try reading the topcoder article and then read this on SO: https://stackoverflow.com/questions/15439233/bitusing-a-binary-indexed-tree

    I think the SO explanation was decent. Visualize the

    1) Query operation: going backwards (from a leaf node) on the right link.

    2) Update operation: going backwards (from a leaf node) along left link,

    The solution to problem E will simply extend this to both x and y dimensions. The GeeksforGeeks article also explains this well with a diagram: https://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree/

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks for the article, but what is addupd and addget for? Especially the i |= i+1 part and why do we have to sort them?

      • »
        »
        »
        »
        6 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Actually even I did not understand the editorial and didn't bother to after some attempts. I wrote my own solution, and it is more straightforward compared to the editorial: https://codeforces.com/contest/1093/submission/47477762

        it is a direct approach taken from the articles I linked above. This solution does NOT pass after test 10 because of memory space usage but you can still read it to see how the 2D BIT is implemented (it is very easy in terms of implementation ...)

        The final solution that worked used a GNU PBDS "ordered set" data structure called tree (since a set can be implemented using AVL trees) ... I'm not too familiar with it but I saw some codeforces posts about it after the contest.

        Here is the link to the final solution: https://codeforces.com/contest/1093/submission/47479386

        It uses the standard BIT for the x-dimension but uses the GNU PBDS "ordered set" for the y-dimension. As you will read in other Codeforces posts about this, this solution will only work if you wish to "count" something (in this case, points inside a rectangle), since the solution uses the "index" of the item in an ordered set, which is a shortcut for finding the prefix sum if you simply have to count the number of elements before a certain element. (I found this the best way to understand the usage of the GNU PBDS ordered set.).

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem E, square root decompsition + binary indexed tree solution is getting accepted, when block_size is fixed about 800, but getting TLE when block_size is used by sqrt(n). In both solution each update is O(4*logn) and each query is O(2*block_size + (n/block_size)*logn) and pre build is O(nlogn).

So, is data set weak for problem E? Isn't it possible to create such input so that this solution can't get accepted?

Accepted using block_size = 800: 47504503
TLE on test 16 using block_size = sqrt(n): 47504554

**Update: ** Accepted solution runs in about 2.5 sec, when block_size is 1700.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I keep getting TLE in D on test case 22. Can anyone tell me what's the problem? Here's my solution.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u should set by hand, not memset ! With memset u get a complexity of O(N) so a total of O(N ^ 2). setting it by hand would result in a complexity of O(N) because the sum of N over all test cases is smaller than 3e5

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I realized memset can be bad at times. Thank you!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain me Q1? Why x//2 is the solution??

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain QC : Mishka and the Last Exam question! How is the greedy approach working?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dice pulling sample output looks wrong...What do you think guys??

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody help me with my code on F ? I checked myself many times with the provided code but i find nothing suspicious. I get WA on test 4 47825046

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please, someone, suggest me some material of how to compress numbers in a 2D BIT. I am unable to get how Editorialist of the Problem E is compressing the numbers in each BIT.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting wrong answer in prob. D, test case 3,that is , for some cases my code is giving output 0, anybody got any ideas? Link to the code :

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone please help in beautiful graph??dont know why i m getting wrong answer in test case3 here is my link https://codeforces.com/contest/1093/submission/49533934

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, can anyone explain to me why my code of problem "D-Beautiful Graph" is not working? I tried to make it as similar to example code as possible but still does not work. my code