Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

vovuh's blog

By vovuh, history, 3 months ago, In English,

1328A - Divisibility Problem

Idea: MikeMirzayanov

Tutorial
Solution

1328B - K-th Beautiful String

Idea: MikeMirzayanov

Tutorial
Solution

1328C - Ternary XOR

Idea: vovuh

Tutorial
Solution

1328D - Carousel

Idea: MikeMirzayanov

Tutorial
Solution

1328E - Tree Queries

Idea: MikeMirzayanov and vovuh

Tutorial
Solution

1328F - Make k Equal

Idea: MikeMirzayanov

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +127
  • Vote: I do not like it

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

Thanks for the editorial

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

Could someone please elaborate the tutorial for question B? Specifically, from where did we get the equations k<=n-i-1 and n-i-1?

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

    Starting at the end, for every index, let's imagine some string such that it looks like aaaaaabb.

    Now imagine the left-most b moving to the left. For each move to the left, the right-most b has one more possible location. For example, aaaaaabb has 1 position for the second b, aaaaabab has 2, and so on.

    This remaining k value can also help us calculate the position of the right-most b because of the fact that it's remainder once it is less than n-i-1 hints at where it should go.

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

      Got your point. Thank you! :)

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

        Can you please explain it again. I still did not get why are we using 'k'. 'k' is just the position of string that we need to print right ?. Why are we checking if k<=n-i-1 to find the left occurrence of 'b'?

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

          With every K , position of B is changing and notice how...look at first 10 permutation provided in the problem itself. It's not arbitrary there is a pattern. Now value of K will tell us how the final change might look like if you get the pattern.

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

      I still didnt got your point. How we are forming these equations k<=n-i-1 and n-i-1?

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

        Consider a string s of length n. First, number the positions of the letters from 1(rightmost letter) to n(leftmost letter).

        Lexicographically, the smallest string will have a 'b' in positions 2 and 1. It is easy to observe that there will be i - 1 strings having leftmost letter in the ith position. So, all you need to do is k -= (i - 1) as long as k > 0 and i goes from 2 to n. Suppose, j is the smallest value of i for which you weren't able to perform this operation. That means the leftmost b will be at position j. Since, this is j from the right, it will be equivalent to n - j + 1 from the left. This will be s[n - j].

        Now, if you would have k = 1 then rightmost b will be at position of 1. In general, for some remaining value of k, the rightmost b would be at position k. So, that would mean n - k + 1 from the left. That would mean s[n - k].

        For eg: n = 7 and k = 5. You can do k -= 1 and k -= 2 to get k = 2. j will be 4. That means s[7 - 4] = 'b'. Also, if k = 2 then s[7 - 2] = 'b'. Thus, s = "aaababa" for k = 5 and n = 7.

        I hope this helps. It will be easier to understand it if you work it out a bit more on paper with examples of your own.

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

    If you notice carefully here k <= n-i-1 is really k <= (n-1)-i. And this (n-1)-i indicates the available position for right most 'b'.

    Now lets try to find a pattern from the given example in problem statement.

    when the left most 'b''s position is 3 we have 1 available space for rightmost 'b'

    when the left most 'b''s position is 2 we have 2 available space for rightmost 'b'

    when the left most 'b''s position is 1 we have 3 available space for rightmost 'b'

    when the left most 'b''s position is 0 we have 4 available space for rightmost 'b'

    K   STRING  POS.
    1   aaabb    1
    2   aabab    2
    3   aabba    2
    4   abaab    3
    5   ababa    3
    6   abbaa    3
    7   baaab    4 
    8   baaba    4
    9   babaa    4
    10  bbaaa    4
    

    Notice if k > available position for 2nd 'b' that means we have to increase the available position and to increase it we have to shift our 1st 'b' 1 position left. And if we shift our 1st 'b' 1 position left that means we have already considered all the position for 2nd 'b' for the available position. So we simply just subtract available position from k

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

nice contest :)

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

I am unable to understand third part of D's code . Any hint .. it seemed very easy ,but still i got wa at tc 2.

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

    you can always get an answer if you color every odd vertex with 1 and every even with 2 but when n is odd then first and last will have same color.so if you have a consecutive pair with same value then you can color both of them with same value which will change parity of all subsequent numbers.EX: 1,2,2,3,4 can be colored as 1,2,2,1,2 instead of 1,2,1,2,1. and if no such pair exist then you have to use 3rd color.

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

    u must have forgotten to check if first ans last are same.

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

I had a different approach for 1st problem but it did not accept And when I compile on my idea it worked good.please help me

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

    I checked your code, the idea is absolutely correct. However, you need to print a newline after every distinct answer otherwise answers for all test cases would be shown side by side. cout<<count_<<endl; Make this change in your code and it should work fine!

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

      \n is faster than endl

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

        Yes, but that's a different topic. Since he wrote the previous terms in CPP manner, I suggested using endl. And for this problem, this is not even a big deal!

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

      even apply this I think his code gives TLE because of constraint 10^9.

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

      will definitely timeout

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

    Your solution will not work for large cases.

    Let me expand the solution given, i.e how this equation came up b - a%b — let's derive it.

    We know we can write a as a = b * k + a%b where k is the quotient. k can also be written as k = (a - a%b)/b. We are interested to find the next k for which remainder is zero, so we need k+1.

    So, a + c = (k+1)b + 0 where c is the count/number of steps (+1) to add to a to make a%b zero. Substituting k from above to find c:

    a+c = b * ((a- a%b)/b + 1)) = (a - a%b) + b

    a+c = a - a%b + b

    c = b - a%b. There it is!

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

The constraints for problem B were weak many o(k) solutions passed. Example — https://codeforces.com/contest/1328/submission/74509641. I tried to hack it but can't

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

I did B in O(1) per test case

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

    sqrtl() is actually O(lg n)

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

    Printing the string is O(n)

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

      Oh Yes. I was so much excited to solve t[he main part in O(1). I completely forgot to consider that.

      Thanks Srk1C

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

        Yes, I also used quadratic equation to solve the main part. Cheers!

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

        nah, I also think that I did it in O(1) till reading these comments :D

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

    hey harsh_joeyit can you explain your solution of B Problem

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

      Sure:)

      K   STRINGS    pos of 1st 'b'(from left)
      1   aaaabb -   1
      2   aaabab -   2
      3   aaabba -   2
      4   aabaab -   3
      5   aababa -   3
      6   aabbaa -   3
      7   abaaab -   4
      8   abaaba -   4
      9   ababaa -   4
      10  abbaaa -   4
      ......
      ...
      ..
      
      Observation - 
      Position of first 'b' follows a sequence of 1, 2, 3, 4, 5......
      Similarly, the position of second 'b' can be traced out if we find the position of first 'b'. for every block(i.e 1, 2, 3, 4.....) second 'b' starts from 0 and goes to 1 less than the position of first 'b'.
      
      for sequence 1, 2, 3, 4, 5......
      so we use (n+1)*n/2 = k   ---- for finding position of first 'b'
      
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am still having a problem understanding. What I understood for first 'b' is that it will be 1 time in 1st position, 2 times in second position and so on, but how do I find out that what will be the answer when I have only the info of 'k'.

        Though thanks for the observation.

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Position of first b stays at -
          1 - for 1 time , k = 1
          2 - for 2 times, k = 2, 3
          3 - for 3 times , k = 4, 5, 6
          4 - for 4 times , k = 7, 8, 9, 10
          ...
          ..
          this suggested me to use the formula for series 
          1+2+3+4...n = n(n+1)/2
          to find which block does the k belong to 
          
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I understood why you used this formula, but Sorry, I can't understand how you used this formula when only 'k' and 'n' are given.

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

              we have to run n from 1 to find the value.

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

              @MahinHossen See the position of the first/left 'b' from the right is 2 for the first term, 3 for the next two terms etc.,

              i.e., for n = 5

              aaabb

              aabab aabba

              abaab ababa abbaa

              baaab baaba babaa bbaaa

              Iterate from i = 2 to n from the right side. Stop when i*(i+1)/2>k; then the value of i from the right gives the position of the left 'b'. Then do val = k-i(i-1)/2. The position corresponding to val from the right side gives the position of right 'b' .

              For example, in the above case where n=5, take k= 4; then i = 3, is the min number such that i*i+1/2>4. So the position of left 'b' is 4th from the right Now, 4-i*i-1/2 = 4-3= 1 So the position of the right 'b' is 1st from the right. Here the indexing from right is considered to start from 1.

              Hope this clears

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

                Your explanation is great. It very much clears everything. Thank you very much from the bottom of the heart.

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

                from where you find the expression k-i*i+1/2to find the position of right b;

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

        Thanks harsh_joeyit nice explanation, got ur method

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Beautiful approach for E!

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

Is there a name for the technique used in E? Or where can I read more on it (formal proofs, etc.)?

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I have a different approach for B.
We know that after n*(n-1)/2 permutations, both b's will be together. So we can basically make an array of all such numbers (1,3,6,10,..),and for a given k, we can find an n s.t n*(n-1)/2<=k (by binary search). Let j be the pos of that n. We can clearly see that for this value the no. of a's after the 2 b's will be exactly j (i.e, we can determine that particular permutation).
So, from that permutation, we can lexicographically check next permutations till we reach k and print that kth permutation.

C++ soln:74461692

»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it

" Write some LCA algorithms and other hard stuff or write about 15 lines of code and solve the problem " — One of the best editorial (E problem)!

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

can anyone explain me problem F in simple words like how to solve the problem. i am not able to clearly understand the tutorial please help thanks in advance

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

I believe E can be solved by just maintain an array of vertex while do dfs. When you enter a vertex mark it and all it son in the maintained array, when you leave a vertex remove all it sons from the array. Now we can answer the queries in the order we visit the vertexes in the dfs. When we enter to a vertex v , we know exactly which vertexes appear on the path to it or in dist 1 and we can answer all the queries where u = v.

My mistake, I changed the problem in my head and made U alway the last vertex of the query.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • when you leave a vertex remove just all it sons from the array but not the vertex you just left.
»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't understand the solution for E after it explained how to figure out if vertex u is parent of vertex v. Can somebody explain it please ? (I don't want the explanation for checking if one vertex is ancestor of another, I want explanation for AFTER it).

  • »
    »
    3 months ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it
    1. if Vertex A is ancestor of Vertex B, on the way of reaching B we will cross A

    2. In dfs(), we mark every vertex by its parent. (say u is parent of v, we mark v with u).

    3. On the path to reach the deepest vertex(say vertex x) in each query:

    3a. we mark all vertices with parent vertex 1(because vertex 1 is always on the path , therefore we can reach all of the immdediate children of vertex 1, since they all have distance of '1 unit' from the path )

    3b. we mark all the ancestors of 'x'( cause we will cross them to reach 'x')

    3c. we mark all the immdediate children of these ancestors we found( because we still can reach them as maximum distance from the path to x is '1')

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

My solution for Question D without using Graphs and DP.

https://codeforces.com/contest/1328/submission/74499296

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

The site is too f#cking slow today, it's taking minutes to logout/login, all links are loading really slow, is this normal or is this new??

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

    because of the quarantine that is in place in a lot of countries a lot of people have more time to practice CP so the site gets a lot more people on it.

»
3 months ago, # |
Rev. 5   Vote: I like it +2 Vote: I do not like it

Anyone else used Quadratic equations to solve the main part of Question B in O(1) for each test case??

My solution :- https://codeforces.com/contest/1328/submission/74439092

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

    Yeahh...me....that give the position of "b"'s in O(1)

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

    Me. But as someone suggested above, sqrt is O(logN). Even I got excited and overlooked this tiny detail . No O(1) but AC nevertheless , so who cares !!

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

    How can quadratic equation be used to solve 1328B - K-th Beautiful String ? can you explain the logic ?

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

      Let q and w be positions of "b" in the final string from right side.

      Then refer to this image given below.

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

Can someone suggest some good resources to learn how to make changes in DFS methods amd efficient graph algorithms...like many a times I see dfs1 and dfs2 kimd of functions.... Expecting genuine help!!

»
3 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Dear MikeMirzayanov and Vovuh, nice problems. But Someone stole my rating after this round. I was dark blue color, so i should be unrated for this Div 3 !

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thank MikeMirzayanov and Vovuh for interesting problems and fast editorial!

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

I had used StringBuilders for the problem C. Here is my submission https://codeforces.com/contest/1328/submission/74463191 Can any java coder tell me why did it give a TLE?

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

this is my solution 74533033 to problem C in yesterday's contest. i dont understand what's wrong with it. it seems to work fine. can anyone help?

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

    I have fixed your solution: 74544016. You need only to resize your strings such as x, a and b.

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

      thanks:)

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

      vaaven I generally take whole string as input at once and not by each character. So I have a doubt that while taking character wise input(cin>>s[i]), why resizing the string to n, was not needed for smaller inputs(n~5) as in test cases 1 and 2. Runtime error came in test case 3 for n=250.

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

    you should take input "string x" outside the for loop I guess, and then access each letter of x by x[i]. It will work.

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

Can anyone explain the concept behind Problem 'F' in Editorials or any simpler version that you know, I looks Easy But hard to connect logics?

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

For problem F, I sorted the array and used the difference between consecutive elements and the number of moves required to make all the numbers before a particular number to make all of them equal to that number. I did this for both prefix and suffix part and only counted the required number of moves. 74541622

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

    how do you sure that you have " at least k equal elements in the array." in each step?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      for that part i take the sum of steps from both left side(represented by 0) and right side (represented by 1) on a particular element(representing that all n-1 elements are converted to that element )and subtract it by n-k (meaning that these elements are extra element that were converted).
      

      for initialization part i took first k elements that means that first k-1 elements are converted to the the kth element and subtracted the answer with the number of occurrences of the kth element. i also did the same thing for the kth element from the last.

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

        Why you subtracted the number of occurrences of kth element?

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

          Suppose

          k = 5,

          Ar = 2 4 5 6 6 6 7 8

          m[6] = 3

          dp[0] = 0 cost for all element to become 2

          dp[1] = (4-2 * 1) + 0 = 2 cost for all element to become 4

          dp[2] = (5-4 * 2) + 2 = 4 cost for all element to become 5

          dp[3] = (6-5 * 3) + 4 = 7 cost for all element to become 6

          dp[4] = (6-6 * 4) + 7 = 7 cost for all element to become 6

          Now m[6] = 3-2 = 1

          our answer is dp[4] — m[6] = 7 — (1) = 6

          How answer is 6 ?

          Keep in mind that we already have three 6's so we need not to convert 5 -> 6

          Final answer = 6 , 6, 5, 6, 6, 6, 7, 8

          Total cost = 6-2, 6-4, 5, 6, 6, 6, 7, 8

          We only need to convert those which are required so if our Kth element is x and we are suxh more x already present ? we can use that too.

          Similarly

          k = 4

          for ar = 1,1,1,2,3,3

          3,3,2,2,3,3

          answer = 5

          We can do this for both sides and select the minimum one

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

Please explain what exactly is happening in the B problem?how are we knowing the position of b by decreasing by n — i — 1?

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

Can someone please help me figure out why am I getting timeout even if my complexity is O(N + sum(K)) for problem E? Here's a link to my solution. https://pastebin.com/y9Fx5day. Thanks in advance!!

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

    Maxi can be equal n in worst case. So your solution is O(n^2)

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

can somebody please explain how the scoring works in codeforces? start off by explaining what's does it mean by +,+1,+2.

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

Anyone who has done D using DP ? Please share your solution

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

This was my solution for B.

Solution- 74469154

i used the concept of "Sum of first n terms" So if the string size is n then the the total lexicographical strings produced will be sum of first n-1 terms.

for ex- n=5 so total number of lexicographical strings produced will be sum of first 4 numbers 1+2+3+4=10

Then I made a vector pair consisting of lower range and the upper range of k.
1 contains (1,1)  leftmost b will in the position n-2
2 contains (2,3)  leftmost b will in the position n-3
3 contains (4,6)  leftmost b will in the position n-4
4 contains (7,10) leftmost b will in the position n-5

(The concept is For every movement of leftmost b , Following will be the movement of rightmost b till the its position one more than the position of the leftmost b.

For ex-string-abaab the rightmost b will have positions 3 and 4.

)

Rightmost b's position will depend on the distance between k and its lower range
for ex n=5,k=8
5 will lie in the range(4,6)
leftmost b will in the position 1 (1 based indexing)
rightmost b will in the position n- (difference(n-lower range))  ie 5-(5-4)=4
so the string is 'baaba'

Complexity — O(n)

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

    Me too

    My simple Implementation for problem B

    My Submission

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

Hello and thanks for contest. I was EXPERT before the contest DIV3 but my rate change -20, WHY? Thanks again.

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

    Similarly I've seen an EXPERT coder get his rating increase for about 20 in the last div.3 round.Maybe it is a bug?

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

    probably because you had registered yourself for this contest before rating change of last round (when you were<1600)

»
3 months ago, # |
  Vote: I like it -9 Vote: I do not like it

It says time limit exceeded but is the logic correct?

void solve()

{ int n, k;

cin >> n >> k;

int l = n * (n - 1) / 2;

string s(n, 'a');

int b1 = n - 2, b2 = n - 1;

    for (int i = 1; i < k; i++)
    {
       if ((b2 - b1) == 1)
       {
         b1--;
         b2 = n - 1;
       }
       else
       {
         b2--;
       }
    }



s[b1] = 'b';
s[b2] = 'b';
cout << s << endl;

}

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

    Yes, logic is correct but it works very slow because you have O(k) where k can be equel 1e9.

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

Can anyone tell me what's the reason of getting TLE for the following solution of problem E? https://codeforces.com/contest/1328/submission/74550098

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

    Max depth can be n. So you will make n iterations to check only 1 node. Your solution work in O(nm)

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

    Because you iterate over the whole longest path every query, so the complexity may be O(mn) instead of O($$$\sum\limits_{k = 1}^mk_i$$$)
    The testcase may be a linear chain tree with every query contains a far node from the root

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

Problem : E My submission : 74555362 Verdict: WA on TC 56 Can anyone tell what is the mistake? I cant figure it out. Used the same method as told in Editorial. My code is very short. Thanks a lot :)

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

    I fixed your solution:74558555

    I just add this:

    reverse(temp.begin(), temp.end());
    

    and edit this:

    if(temp[i].F>st or temp[i].S<en)
    
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone who has done D using DP ? Please share your solution

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

C) Why if x[i]=2 or x[i]=0, then a[i]=b[i]=1 or a[i]=b[i]=0 relatively? Who can explain it? Please.

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

    because max(1, 1) < max(2, 0) when x[i]=2 and max(0, 0) < max(1, 2) when x[i]=0

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

Can someone please explain this part Of problem E

It lies on this path if the root is the parent of u (it is always true) and u is the parent of fv. This approach can be used for each vertical path (such a path from x to y that lca(x,y) is either x or y).

And this code of problem E

int u = v[0]; for (auto it : v) if (d[u] < d[it]) u = it; for (auto &it : v) { if (it == u) continue; if (p[it] != -1) it = p[it]; } bool ok = true; for (auto it : v) ok &= isAnc(it, u);

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

Help needed in E: My approach-: Check if there is path from root containing all the parents. Sort all the parents of given nodes according to their height. Then find lca of every adjacent pair, suppose x and y are adjacent , then if lca(x,y)==x then path exists else not. I am getting runtime error in test case 100. Can anyone help me out in this?
My submission 74567267

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

****_Problem B_ Can someone tell me the logic behind k<n-i-1 and k-=n-i-1; why k and what we get from k in every time in loop

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

I used rint(sqrt(k * 2)) to solve B. What do you think?

scanf("%lld %lld", &n, &k);
    firstb = rint(sqrt(k * 2));
    secondb = k - (((firstb * (firstb - 1))) / 2) - 1;
    for(int i = 0; i < n - firstb - 1; i++){
       printf("a");
    }
    printf("b");
    for(int i = 0; i < firstb - secondb - 1; i++){
       printf("a");
    }
    printf("b");
    for(int i = 0; i < secondb; i++){
       printf("a");
    }
    puts("");
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

somebody plz explain B...

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

    I also didn't know it before, got the solution by generating few cases while contest.Generate 6/7 cases and you will find the pattern.

    • See this case: n = 5; k = 5; "a B a b a"
    • Take minimum integer x so that k <= (x)(x+1)/2;
    • For the first B , pos1 = (n — x)th index from left side.
    • Keep = (x)(x+1)/2 — k;

    • For the second b , pos2 = (pos1 + keep + 1)th index from the left side.
    • Without pos1 and pos2 all positions will be a.
»
3 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Editorial solution for E is nice, but there is a solution that requires much less thinking. Handle the queries offline, and then you simply need to do a dfs from the root and add all the neighbors you pass on the way down to your current set (to add to your current set, just mark them as visited in all the queries that contain this vertex. if a query has everything marked as visited, then it is good) and remove the neighbors on your way back up. This way you can just check all the paths in O(n+m) time (fairly high constant but still runs < 1s).

74575633

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

    can you plz elaborate how you use add and remove in your code

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

      He has made a vector of vectors qs where each entry(qs[i]) is a vector which stores queries in which i-th vertex has been mentioned.

      Then in add function, for a vertex v, all the queries are traversed in which v-th vertex was mentioned and another vector qc is being increased for those queries (++qc[query];). When value of qc for a particular query reaches number of vertices in that query(denoted by qn[query]), it means that all the vertices in that query are neighbours of some path from root to some vertex. This count of vertices which are neighbours, was kept by qc[query].

      Now remove fn is easy to understand as it is basically removing the neighbours count.

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

      Yes, amangupta's description is correct. Just to clarify a bit more on the specific variables:

      qn[i] — the total number of vertices in query i (qn = query number)

      qc[i] — the number of vertices in query i that have been currently marked (qc = query current)

      qg[i] — 1 if query i is achievable, 0 otherwise (qg = query good)

      qs[i] — a list of queries that vertex i appears in (qs = queries)

»
3 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it
My simple Implementation for problem B

My Submission

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

Thanks MikeMirzayanov and vovuh for awesome editorial specially problem E.

»
3 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

vovuh MikeMirzayanov how can we prove this fact for problem F.

** The second observation is that we first need to take elements from one end (only less or only greater) and only then from the other (if needed).**

why it will give correct answer and why we can't expand from both side. say if we need x, and we take y from begining first then we will take x-y from end. similarily for the same index, if we take a from beginning , we again take x — a from right.

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

in q3 , in the else statement how did the statement

a[i] = b[i] = '0' + (x[i] — '0') / 2;

work?

please explain

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

    When x[i] = '2', then x[i]-'0' will give 2 and this divided by 2 will give 1 and this added with '0' will give '1'. So a[i]='1' and b[i]='1', as required. When x[i] = '0', then x[i]-'0' will give 0 and this divided by 2 will give 0 and this added with '0' will give '0'. So a[i]='0' and b[i]='0', again as required.

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

I feel like C was too easy :/

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

I am not getting approach of problem F. Can anyone explain it?Thanks in advance:)

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

CAN ANYONE EXPLAIN THE ERROR I HAVE REPLACED V[] WITH THEIR PARENT // TO OVERCOME THE DISTANCE FACTOR OF 1 I HAVE SORTED THE V[] ACCORDING TO THE LEVELS THEN CHECKED EVERY CONSECUTIVE WHETHER THEY LIE IN SAME PATH OR NOT

include<bits/stdc++.h>

using namespace std;

define ll int

define pb push_back

define fi first

define se second

define mp make_pair

ll in[200007],out[200007]; vector adj[200007]; ll level[200007]; ll par[200007]; ll k=0; ll k2; ll timer=0; int flag; pair<ll,ll> p[200007]; ll v[200007]; void dfs(ll u,ll lv) { level[u]=lv; ++timer; in[u]=timer; for(int i=0;i<adj[u].size();i++) { par[adj[u][i]]=u; dfs(adj[u][i],lv+1); } ++timer; out[u]=timer; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll n,m; cin>>n>>m; level[0]=0; in[0]=INT_MIN; out[0]=INT_MAX; for(int i=0;i<n-1;i++) { ll x,y; cin>>x>>y; adj[x].pb(y); } dfs(1,1); par[1]=0; for(int idx=0;idx<m;idx++) {

    cin>>k;


    flag=0;
    for(int i=0;i<k;i++)
       cin>>v[i];
    for(int i=0;i<k;i++)
    {
       v[i]=par[v[i]];
    // cout<<v[i]<<" ";

    }
//  cout<<endl;
    for(int i=0;i<k;i++)
       p[i]=mp(level[v[i]],v[i]);
    sort(p,p+k);
    // cout<<flag<<"\n";

//  cout<<in[p[0].se]<<" "<<out[p[0].se]<<" "<<p[0].se<<endl;

    int nop=0;
    for(int i=1;i<k;i++)
    {
       if(in[p[i].se]>=in[p[i-1].se]&&out[p[i].se]<=out[p[i-1].se])
         nop++;
       else
       {
         flag=1;
         break;

       }
    }

    if(flag==0)
       cout<<"YES\n";
    else
       cout<<"NO\n";

}

}

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

    Sharing your code via one of the text storage sites like pastebin or ubuntu paste might significantly increase your odds of getting a help

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

    Or simply include the submission id like 74594978

    This gives you TLE, wich means your solution runs out of time, hence is to slow. I think for every query you recreate the whole path from root to deepest node. This makes it basically $$$O(n^2)$$$ wich is to much for very deep trees.

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

For Problem F i didnt understood what is needl=min(need,prefcntprv) i:e prefcntprv

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

hello i submitted a solution for kth beautiful string problem.i got runtime error for that during the contest.but today i submitted that same file from my pc without any edit and it got accepted.where can i complain regarding this? this is my first contest on codeforces.please help.

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

    I think it is not the same code, you changed the types of your integers. Most likely the runtime error was caused by overflow.

    Aside from that, would be useful for such question to include the both submission ids.

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

      i didnot change anything bro...i just submitted the file that was there in my pc.without even opening it in the editor.and it got accepted this time

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

Hi @vovuh, I have a question regarding 1328F and sorry if disturbing you.

I think I may have triggered some wired behavior of Java 11, with which Arrays.sort(int[]) becomes extremely slow. From my attempted submission https://codeforces.com/contest/1328/submission/74614186, you will see that it's TLE with Arrays.sort(a) at the top part of the solve(n,k,a). If I switched from Arrays.sort(a) to use an ArrayList of tmpA to sort and assign back to a, which becomes submission https://codeforces.com/contest/1328/submission/74613801, it's accepted.

I tried to reproduce this on my local machine by randomly generating 200000 numbers between 100000 and 200000 and failed, it's super fast with Arrays.sort(int[]). This may due my usage of openjdk 11, which differs from that used by codeforces, or due the data itself.

Could I have the 3rd testcase so I can verify it on my local machine?

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

    Quick sort is known to have $$$O(n^2)$$$ in worst case.

    see some link

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

      Yeah I know that basic info.

      But:

      1. from what I see, the 3rd testcase is not already sorted or even mostly sorted.
      2. as we all know the worst cases of traditional quicksort, sure does the designers of java standard library. In fact, there are lots of technics to deal with the worst case of quicksort in Arrays.sort() or Collection.sort(). And from Java 7, the dualpivotquicksort for primitives is introduced to further improve the performance under traditional worst cases, as the implementation notes said: "The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations."

      But you made your point, and I already suspect that this specific testcase may be one of the rare bad case for this implementation. That's why I need this case to experiment on my local machine. And if it is I may report this to jdk team as a bug.

      Anyway, thanks for the reply.

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

        Hi, MikeMirzayanov and vovuh, I did further experiment on this issue.

        As in submission https://codeforces.com/contest/1328/submission/74698017, I deliberately force the 3rd test case to use ArrayList.sort(...) and let rest of the test cases use Arrays.sort(int[]), everything goes well and it's accepted. This makes me more confident that the 3rd test case happens to be one of the rare bad case for DualPivotQuicksort in Java 11's standard library, which actually has been there since Java 7.

        It would be great if I can have the 3rd test case and confirm it on my local machine. Anyway I can have it?

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

Could anyone tell me what's wrong with string c_str in GNU C++?

My two submissions of problem C:

https://codeforces.com/contest/1328/submission/74623565

https://codeforces.com/contest/1328/submission/74623526

They're exactly the same code with only difference is the lang(one is GNU C++17, the other is Clang++17 Diagnostics). I get WA with GNUC++, but passed with Clang++. Why did this happen?

And I get AC using cout to print string with GNU C++:

https://codeforces.com/contest/1328/submission/74623915

That's weird... at least to me...

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

74633006 TLE on tc 58 can someone help me

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
     while(note!=-1)
            {
                mpp[note]=1;
                note=par[note];
            }
    

    This loop could reach O(n) so your solution has a worst complexity of O(n*m)

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

where are the ratings of this contest?? My rating was incresed by 57 but it is not showing now.

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

i need help in problem E. I'm getting wrong answer in test 43 and i don't know the reason why here is my code: https://codeforces.com/contest/1328/submission/74652500 my answer is 253243 but expected answer is 253245

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

    if you know the problem can you tell me.

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

      finally i found it after few hours! if you are having same problem as me you have to check this test my previvious solution was giving me answer 10 but answer is 11 test: 5 4 1 3 5 7 9 good luck!

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

    the same thing is happening to me :'v

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

Hello, this is my first message on Codeforces, so apologies if it violates any community guideline. I am getting wrong answer on test case 2 for Problem D. My submission id is 74659654. I have looked at it a lot but I am unable to find the problem. Can someone please help me. Thanks in advance. Happy coding !

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

    drag you submission page to the buttom, there's checker comment to show which case you didn't pass.

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

In problem E i am getting runtime error on test 100. I am not able to find the mistake in my code. Can someone help me out with error. link to my code:-74663766

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

In question E why we are choosing depeest node among the tree please explain

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

Could someone help me with C? I keep getting a runtime error and I don't know what's causing it. Here's my submission:

https://codeforces.com/contest/1328/submission/74690659

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

Can anyone explain how we are forming the equations k<=n-i-1 and n-i-1 in B(kth beautiful string)??

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

I know my approach should result in TLE, but I am getting wrong answer in Problem E. Could someone please help. 74696152

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

My Fair simple approach for E Prerequisites:-LCA of Two nodes in log(N) time in a tree. Step1:- Running dfs traversal on tree and noting down level of each node in the tree and also the parent of each node in the tree and also obtaining the sequence of dfs traversal with which you can get LCA of two nodes tutorial link:LCA Finding tutorial

Step2:-Now for each query we have to answer in YES or NO .So what I did is for each node in a particular query find parent of that node and if node is 1 skip it simply. Store two things for a node particularly its parent number and its level . Sort the obtained vector accorsing to level of parents of all nodes in decreasing order.

Step 3:-Start from top and find lca of top 2 nodes and then with this obtained lca find lca of nodes successively coming and check if obtained lca value is similar to coming value and if it is then move forward till end and else break and print NO otherwise print "YES".

Solution link Implementation

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

    Could you explain why did you skip the node if its parent is 1.

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

      Because when parent is 1 after that LCA of every node is gonna 1 as 1 is root and also as we started in bottom up fashion

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

        Could you please check what is wrong with this piece of code. I'm creating a dummy root, I expected the code to get TLE, but it's giving wrong answer. Thanks in advance. 74696152

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

          Hello __Apocalypse__.

          @Line 48: g[x].push_back(y);

          You forgot add this g[y].push_back(x);.

          I added it here: 75222286 and now it gets a TLE instead of a WA.

          Hope this helps. :)

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

            My submission Can u tell why this giving tle. I have sorted the vertices which are input in m queries according to the height of the tree given by 'dp[i]',which is the only thing different from the solution ,so my complexity is mlog(m),but still tle

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

              Hi Chodermal1.

              @Line 6:

              void dfs(vector<vector<ll>>  ma,ll dp[],ll par[],ll src,ll p){
              

              Here, you're passing ma by value although it is not being modified there. Hence, it is taking more time to copy the data.

              I changed it to:

              void dfs(vector<vector<ll>>&  ma,ll dp[],ll par[],ll src,ll p){
              

              Notice the & used to pass ma by reference to prevent copying of the data and it gets an AC here.

              Hope this helps. :)

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

I dont know whats wrong with the code,It passed all the testcases and verified the logic.It seems to give an error as unintialised value at line 56 due to which i am getting an wa.Please help!!!!

here is my soln: https://codeforces.com/contest/1328/submission/74730546

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

Can anyone explain why this answer for test case in D(Carousel) is wrong? Input

4 5 1 2 1 2 2 6 1 2 2 1 2 2 5 1 2 1 2 3 3 10 10 10 my output 2 1 2 1 2 1 2 1 2 1 2 1 2 3 1 2 1 2 3 1 1 1 1 Jury's output 2 2 1 2 1 1 2 1 2 1 2 1 2 3 1 2 1 2 3 1 1 1 1

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

    Input:

    1 2 1 2 2
    

    Your output:

    1 2 1 2 1
    ^       ^
    |       |
    

    These are the same but not in the input. Assume that after the $$$n$$$-th figure the figure $$$1$$$ goes.

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

In problem F (1328F - Make k Equal — Make k Equal), Can someone please explain why the answer to the following custom test case is 29 and not 21?

12 8

1 3 3 6 6 6 11 11 11 11 11 11

Answer as per given Editorial Code = 29. Possible answer = ( 1*(6-1) + 2*(6-3) + 2*(11-6) = 21 ). {by making all 8 elements equal to '11'}

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

    After making all the elements 6, you can't directly increase two elements to 11, because once you increase it by 1, it becomes 7 and is no longer the smallest element in the array....

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

Why in the solution of ternary xor we are adding '0'+(x[i]-'0')/2 is it to convert it in to string so that the number is in the string format

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

I submitted the same source code to problem C twice, the first time it failed, and the second time it is accepted. Has anyone got similar problem before?

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

can anyone help me find what i am doing wrong in this code of problem E

75035885

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

I have solved "Problem E" using the Lowest Common Ancestor Concept. Straight forward lowest common ancestor logic.

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

    My submission Can u tell why this giving tle. I have sorted the vertices which are input in m queries according to the height of the tree given by 'dp[i]',which is the only thing different from the solution ,so my complexity is mlog(m),but still tle

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

In problem D. why if n is even coloring always can be done like [1,2,1,2,..2] For n = 6 , 1 2 2 1 2 3 should give 3 , 1 2 2 1 2 3 instead of 2 , 1 2 1 2 1 2

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

    u can have different colours for same number. So when n is even just alternatively put 1 and 2 so each adjacent position will have different colours regardless of the fact that they are same or different

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

//TRee queries solution //BISMILLAH

include <bits/stdc++.h>

using namespace std;

define sz 2*100009

map < int, int> dd; map < int,int> ff; map <int , int > cost; vector adj[sz]; int vis[sz]; int T = 0; int par[sz]; void dfs( int source){ int i,j; int len; vis[source] = 1; dd[source] = T++; len = adj[source].size(); for(i = 0;i<len;i++){ if(!vis[adj[source][i]]){ par[adj[source][i]] = source; cost[adj[source][i]] = cost[source] + 1; dfs(adj[source][i]); } } ff[source] = T++; return; } int main(){ int len; int n,q,m,i,j; int u,v; int temp,maxx = -1; int y,w; int b,c; int flag = 0; int k; int res; cin >> n >> q; m = n-1; for(i = 1;i<=m;i++){ cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } par[1] = -1; dfs(1); while(q--){ flag = 0; res = 0; cin >> k; int a[k]; for(i = 0;i<k;i++){ cin >> a[i]; a[i] = par[a[i]]; if(a[i] == -1) continue; else if(a[i] == 1) continue; else if(a[i] != 1 && flag == 0){ u = a[i]; flag = 1; } else if(a[i] != 1 && flag == 1){ if(cost[a[i]]>cost[u]){ v = u; u = a[i]; } else v = a[i]; if(ff[u]<dd[v] || ff[v]<dd[u]) res = 1; } } if(res) cout << "NO" << endl; else cout << "YES" << endl; } return 0; }

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

A doubt please on C part although i got accepted in python in test case 5 in C language i was getting Wrong output format Unexpected end of file — token expected....... my approach was correct........as with same logic python code was accepted........1328C][YOUR TEXT TO LINK HERE... - Ternary XOR(https://codeforces.com/contest/1328/submission/75352334)

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

Can anybody please explain the reason for doing this Let's take every non-root vertex (except fv) and replace it with its parent. Thanks

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

can someone help me with the code when i was running it it was fine as hell but in codeforces it's showing a runtime error please help me with it.... This is the division 3 5th Question's Answer:

Code Made By Rap_coder in python 3

75464011

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

Where could I find more information about the Technique used for E, such as proofs or different applications?

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

can anybody tell what is wrong in my code for problem D https://codeforces.com/contest/1328/submission/75753056

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

test

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

awesome contest...!!

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

my solution for 1328C is written below but i get runtime error on test case 3. Could anyone please help me with it? Thanks in advance.

include <bits/stdc++.h>

using namespace std; int main() {
int t; cin>>t; while(t--) { int n,temp; cin>>temp; cin>>n; vector vec; long long int vec1=1; long long int vec2=1;

while(n>0)
    {
        vec.push_back(n%10);
        n=n/10;
    }
    reverse(vec.begin(),vec.end());
    int flag=0;
    for(int i=1;i<temp;i++)
    {   if(vec[i]==0)
        {
            vec1=vec1*10;
            vec2=vec2*10;

        }
        else if(flag==0)
        {
            if(vec[i]==2)
            {
                vec1=vec1*10+1;
            vec2=vec2*10+1;
            }
            else if(vec[i]==1)
            {
                vec1=vec1*10+1;
            vec2=vec2*10;
                flag=1;
            }
        }
        else if(flag==1)
        {
            if(vec[i]==2)
            {
               vec1=vec1*10;
            vec2=vec2*10+2;
            }
            else if(vec[i]==1)
            {
               vec1=vec1*10;
            vec2=vec2*10+1;

            }
        }
    }
   cout<<vec1<<endl;
   cout<<vec2<<endl;
}
return 0;

}

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

This is regarding prob C of this contest. What is wrong with this piece of code?

include

include

include <bits/stdc++.h>

define ll long long

using namespace std;

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; int n; int x; string f; while(t--) { cin>>n; cin>>x; // cout<<n<<"\n"<<x<<"\n"; string f; f=to_string(x); int c=0; string a="1"; string b="1"; for(int i=1;i<n;i++) { if(f[i]=='1') c++;

if(f[i]=='1'&&c==1)
             {
                a.push_back('1');
                b.push_back('0');    
             }
            else if(f[i]=='1'&&c!=1)
            {
                  a.push_back('0');
                  b.push_back('1');
            }
            else if(f[i]=='2'&&c==0)
            {
                  a.push_back('1');
                  b.push_back('1');
            }
            else if(f[i]=='2'&&c!=0)
            {
                a.push_back('0');
                b.push_back('2');  
            }
            else if(f[i]=='0')
            {
                a.push_back('0');
                b.push_back('0');     
            }
        }
        cout<<a<<"\n"<<b<<"\n";
  }
  return 0;

}

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

Can anyone help me why I am getting wrong answer for the question D. Carousel. Here is my code https://codeforces.com/contest/1328/submission/77173034

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

can anyone tell me which algorithm is used in B problem

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

In problem E,why are we not updating the deepest node to its parent while the rest of the nodes are updated to its parent?

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

Now we have a beautiful structure giving us so much information about the tree

Mike got emotional here xD.

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

found a solution for problem B that's a bit easier to understand and also runs in O(N) time: here instead of combinatorics, it uses quadratics. should be easier to understand the problem

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

solution of E is hott!!

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

On E editorial.

"Let's take every non-root vertex (except fv) and replace it with its parent."

I think that you mean: "Let's take the k vertices vi (except if vi is fv, and except if vi is the root) and replace it with its parent.".

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My code appears to work up till test case 100 for problem E. I've spent a while looking at my code to debug it but I haven't been able to identify the issue. If anyone has any idea, I would appreciate suggestions. My Submission