Anus1373's blog

By Anus1373, 5 weeks ago, In English

Thank you for participating. I hope you enjoyed the contest!

1401A - Distance and Axis

Tutorial
Solution Code
Behind Story

1401B - Ternary Sequence

Tutorial
Solution Code
Behind Story

1401C - Mere Array

Tutorial
Solution Code
Behind Story

1401D - Maximum Distributed Tree

Tutorial
Solution Code
Behind Story

1401E - Divide Square

Tutorial
Solution Code
Behind Story

1401F - Reverse and Swap

Tutorial
Solution Code
Behind Story
 
 
 
 
  • Vote: I like it
  • +221
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 3   Vote: I like it -105 Vote: I do not like it

Video Editorial of Problem C: Mere Array

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -45 Vote: I do not like it

    Thanks for the fast editorial!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +74 Vote: I do not like it

    I tell you and other video editorial makers one thing honestly , if you really want to help people help in problem D , E (and F some times) . Just see the number of submissions in problem A,B,C . Almost everyone did them and those who did not would have got by now.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      Yes, most of the participants in cp community belong to average level and hence need help in difficult problems (need explanation of problems above C in cf) in order to increase thier level.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -27 Vote: I do not like it

        Thanks , it's not difficult for any person of any level to upsolve A,B,C .Real difficulty starts from D.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +53 Vote: I do not like it

          To upsolve definitely not, given the fact, that tutorial essentially give you exact way how to code them. But to understand WHY those solutions are correct might not be that easy and this is much more important if you want to improve your cp skills.

          Moreover no matter on your skill level it does happen, that you come up with a more complicated solution/same solution but more complicated way to understand why it works/have something like "my intuition tells me something like this should work but I have no idea how to prove it" even for a relatively simple problem, and then it might be worth it to see the simpler solution

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

          There are many begainers !

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

          Some people think that the difficult part starts from E or F, it's different for everybody. Yes, A, B, C tend to be easy for most people but there are others who celebrate, if they solve C and we as a community got to help each other not make fun of.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 4   Vote: I like it +31 Vote: I do not like it

      Hi @Boron Why are you pulling him down? Maybe you can help the community by making video editorials of D,E,F

      He is putting in efforts to give back to the community,atleast appreciate what he is doing, it may not be helpful to you, but to someone out there it may be immensely helpful.

      Btw no doubt your feedback does also make business sense, because if we look at it like a CP Question (:P), the number of views that he gets on a video editorial of Question X would be = Number of people who solved Ques(X-1) — Number of people who solve Ques(X)

      So for this contest, the audience for Editorial of C is 2000 whereas the audience for an editorial of D is 6000 :D

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

      while u got a point, still this is no reason to demotivate him.

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

      you do see that 23k particiated and only 14k solved the 1st question.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I overkilled it with DSU :/ saw that some set formation is there and quickly started coding. Now I know Div2C is not meant to write large amount of code. Nice video tutorial :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    sir if we take all numbers who are not at the right position and then take out their gcd finally check weather that gcd is equal to the minimum number so is it correct ??

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -23 Vote: I do not like it
    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      try this array

      2 3 8 4

      ans should be YES

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

        in A) why are we searching for an m such that 2*m<=n only why not 2*m>n. The equality would give the answer: m=(n+k)/2 why is it not possible?? Though i understand the condition of checking parity will still hold, why was 2*m>n part not mentioned. Is it obvious??? or am i missing something? :D

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

          It possible & you can do question in this way also. But after calculating m you will need to calculate |OB — AB| & check whether its equal to k or not. Refer this you will get an idea.

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

      Take a test case 2 3 8 4 min element = 2 element not at correct position = {8, 4}

      your answer = gcd(4, 8) = 4

      the problem here is we have to check if gcd({2, 4, 8}) = 2 which is true here.

      So either take check if gcd(your answer, min element) = min element

      or

      initialize gcd with min element and then calculate gcd({min element, .......)

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

        where did they mentioned that we have to take gcd{[2,4,8]}?

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

      2 4 8. The answer should be yes because even though 2 is at the correct place, we can still use it to swap the other values. your solution would be correct if you just check whether the gcd of the calculated gcd and the minimum is equal to minimum or not.

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

      what u can do here is find gcd of the minimum element and the elements not in their correct position (can easily be done by comparing with sorted array) one by one if any of these elements donot have minimum element as their gcd ans is no else yes.

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

          in A) why are we searching for an m such that 2*m<=n only why not 2*m>n. The equality would give the answer: m=(n+k)/2 why is it not possible?? Though i understand the condition of checking parity will still hold, why was 2*m>n part not mentioned. Is it obvious??? or am i missing something? :D

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    You made a great video for solution thanks

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Great video tutorial really helpful thanks

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

    why the fuck people are down voting this

»
5 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

Great problem set Anus1373!

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

In F, is solution O(n^2 q) solution supposed to fail? strict time limit :(

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

https://codeforces.com/contest/1401/submission/90613864

can someone tell the error in this solution....i think it has same idea as in editorial :(

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

    Ummm.... I think you didn't have the code for handling the m < n-1 part.

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

      for m<n-1 case i'm just assigning 1 to rest of the lowest visited edges ... is it correct?

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

        Oh oooops sorry I meant the m > n-1 part ;)

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

          till then priority queue will become empty right?? and before it i will greedily assign values?

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

            According to the problem, "the product of all n-1 numbers should be equal to k;", which means you have to use up all numbers in p[]. But in your program it seems to leave them unused though.

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Thanks for a good round and fast editorial!

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Problems are too interesting...

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks a lot for the fast editorial 😀

»
5 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

Anus1373 I really liked your round!

»
5 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Editorial came quicker than most people solved the first question :P

»
5 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

I think, The third problem was the easiest xD as A & B took too many times than C. Btw awesome contest.

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

Can someone tell me a testcase where my code for problem B is failing? https://codeforces.com/contest/1401/submission/90608794 Thankyou

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

    absolutely wrong, try another approach

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

      How so? I am also making pairs of (a2, b0), (a0, b2) and (a1, b0). Just like they did. Please give any testcase where it is failing. Thanks

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

        There you go,

        1
        2 2 0
        0 3 1
        

        Answer is 0 but your program gives -2, Also you are making arrays of x1+y1+z1 length which can through Memory Exeption or TLE.

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

    Basically you have to maximize using z1 & y2. Also try eliminating z2 with x1, y1 with x2. At last y1 & z2. Solution

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

Pretests are too strong..

»
5 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

Swapping problem A & C would be the correct easy to hard order xD.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    difficulty level according to me B==C < D <= A < E < F

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Fast editorial !!!! Great problems specially D problem . Thanks codeforces community

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

In problem E:

"∙ When a segment intersects with two sides (facing each other) of the square, the number of pieces increases by one."

Doesn't the number of pieces in this case increase by two?

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

    Think about the simplest case: you only add one segment going across the square. Initially there is one piece (the whole square) and after adding the segment, there are two pieces, above and below the segment. So, the number of pieces increased by one.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Right, in my head the inital number of pieces was zero lol. Thanks!

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

      But, suppose you then added another segment vertically touching both the opposite sides and intersecting the previous drawn line. Now,the number of peices is 4 (increased by 2). How?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Because you also have a new piece from the intersection of the two segments.

        "∙ When a segment intersects with two sides (facing each other) of the square, the number of pieces increases by one."

        This statement is not counting new pieces from internal intersections.

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Can anyone help me?

My code for Problem D here(https://codeforces.com/contest/1401/submission/90610162)

Like editorial's method, I was trying to get answer. but i don't know why it does not work.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    You take the weights modulo 10^9+7 before sorting them, so the order can come out wrong.

    I made the same mistake during the contest but gave up trying to figure it out. No motivation when the contest is unrated :D

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

      what............?!!!!!?

      i have never thought about that LoL...

      Thank you very much, and i will never modulo before sorting :(

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

      thanks man i spent 1 hour during the contest to find the same bug in my code and also after contest i couldn't find that.

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

      Can you please tell what's wrong in this code for problem d Maximum distributed index.

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

        I think the mistake is in this part of the code:

               for(int i=1;i<n;i++){
                    pq.push({sub[i]*(n-sub[i]),i});
                }
        

        Actually here for each edge between node i and j, the number of times that edge is traversed is sub[i]*(n-sub[i]), where i must be the child in the DFS tree representation of the tree, but in your case you are taking every i. For reference, see my submission: https://codeforces.com/contest/1401/submission/90657259

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

          I found the bug.....I was adding the contribution of extra primes instead of multiplying....

          As for what you are saying that piece of code is completely fine....as every node will be a child to some node except for the root(note I start with i=1 and don't count the root). Thanks anyway though!

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

      I am not even sorting it before multiplication still getting wrong answer on test 5 can you please check this

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

      My Submission , I checked for this but still my submission is giving WA on tc5 , please help me find the error .

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

About E: in the editorial, is it segment tree or interval tree?

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

    It's the efficient segment tree implementation https://codeforces.com/blog/entry/18051

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

      I meant: is it a segment tree (to do operations with numbers), or it is an interval tree (to do operations with intervals)

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

        It is definitely a segment tree (if by "interval tree" you mean the Wikipedia definition). I don't think I've ever seen an interval tree used in a contest problem. But it's confusing because some people refer to segment trees as interval trees.

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

          Thank you. My solution was to construct interval tree (from horizontal segments), then for each vertical segment find the count of horizontal segments which contain its x coordinate. But I haven't done that.

          If it is a segment tree I will try harder to understand this solution:)

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

in PROBLEM D those who are getting wrong answer please check for the case when no of prime factors is greater than no of edges .

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

Can someone share his/her approach for solving problem E. The editorial is too breif for me.

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

    Here's what I did:

    First put all the horizontal lines down in the square. For every line that spans $$$x = 0$$$ to $$$x = 10^6$$$, the number of regions increases by 1 (originally 1).

    Then, we can start putting vertical lines from left to right. We run a line sweep from left to right and maintain a data structure of "active" y-coordinates during every vertical line. I included $$$y = 0$$$ and $$$y = 10^6$$$ as always active lines. You can then notice that for every vertical line $$$V$$$ added, if the number of horizontal lines intersecting $$$V$$$ is $$$z$$$, then the number of regions increases by $$$z - 1$$$. For this part using a Fenwick tree would be a simple data structure that works.

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

      Can you please provide the link to your code. It would be very helpful to understand .

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Your idea and implementation both are awesome. Just 1 small thing, I was checking your code and saw that there is sorting of lines done which is not required, I guess.

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

            Yeah the sorting is not required, I just never removed them from my code :)

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

      I used the same logic just switching roles of horizontal and vertical lines. I used ordered set for querying. But getting wrong answer on 5th test case. Can u please help?? 90619940

      Found !!

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

:)

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

Very nice problems!

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

What's special in Pretest 5(Question number D). Can anybody provide a smaller test so that I can manually verify my code? My submission I had considered the case when m>n-1 too. Any help will be highly appreciated.

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

    Pretty sure it's overflow. I had the same WA, and switching some of my ints to long longs fixed the problem.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    You take mod before sorting frequencies.

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Ratings are calculated already , this contest is fast.

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

The editorial was fast. Ratings was fast. Awesome round. Great.

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

what is the wrong with my solution for D

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

B using recursion (when you don't want to use brain but want to do labour work) https://codeforces.com/contest/1401/submission/90623923

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

    This is written in your code"//.size() return unsigned int so never use i<v.size()-1 in loop"

    What is the risk of doing that ?

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

      I never thought someone will ask about the commented part.

      In some question, you have to loop till the third last character of string. So you will write i<s.size()-2 But when string size is 1, then s.size()-1 will give wrong result as .size() always give in unsigned int.

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

        Ok, I got it. I tried it in c++. It was unexpected value, but for java it is fine.

        Thanks for your time.

»
5 weeks ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

Really Enjoyed the contest man ! Keep up the great works Anus1373 especially and all other co-ordinators too in general :)

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

Please somebody expalin me in more detail, how to prove that we should multiply numbers in both cases in exactly this way. Sorry for my English

»
5 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

During the contest I submitted solution for F and it passed pretests. But I quickly realized that it works in $$$O(2^n \cdot q)$$$, though it was easy to fix so it would work in $$$O(nq)$$$ and I resubmitted. But then I submitted initial slow solution after the end of the contest, and it passed systests! So I quickly hacked it 90619845 But I'm quite disappointed that systest didn't manage to break my initial slow solution(

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

The idea behind D was exactly same as 1280C - Jeremy Bearimy.

And thank you for the contest.

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

My poor puny brain still didn't understand problem A. Could anyone kindly explain a bit more as to why ans would be 0 or 1 in case of k<n ?

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

    When k is less than n, consider B is x distance left of A, then k = n — 2*x. So x = (k — n)/2. If if the difference is odd, you need to move 1 unit, otherwise, with 0 steps you can do it. Visualize it with an example and you might understand better.

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

    if k<n, we can either generate all odd values of k(less than equal to n) if n is odd or we can generate all even values of k(less than equal to n) if n is even

    if n=8: {(b=8, k=8) (b=7, k=6) (b=6, k=4) (b=5, k=2) (b=4, k=0)}

    if n=9: {(b=9, k=9) (b=8, k=7) (b=7, k=5) (b=6, k=3) (b=5, k=1)}

    Hence if n is even and the desired k is even then ans=0,else increment n and ans=1

    else if n is odd and the desired k odd then ans=0, else increment n ans ans=1

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

Can anyone explain in Problem D, why should we do the "product of the number of vertices belonging to each of the two components divided when the ith edge is removed from the tree"? I understood that the edge removed will be visited that many times, but am not getting the intuition or reasoning behind that.

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

    all vertices to the left of edge x, right of edge y for each vertex in left side that edge is used when visiting y vertices on the right. so in total that edge is used x*y times

»
5 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

If you understand what is required in D, the implementation is not trivial, but still easy. So the tutorial should explain what is needed. Instead, the wording is even more bulky than the problem statement.

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

C can also be solved in segment tree 90626651

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

How to prove the equivalence of the two segments in Problem F?

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

In problem B: Ternary sequence, along with the pairs 1,0 0,2 2,1 , I am also maximising the pair 2,2 to decrease the pairing of 1,2. But I am getting wrong answer. Please explain.

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

    if you maximize 2,2 pair you might consume some 2 from (2,1) pair which has potential of adding +2 where as in 2,2 pair it will add 0 .

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

      if we firstly make as much (2,1) as possible and then we use (2,2) then?

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

    you should increase 2 1 pair as this will add 2 to the answer , 2 2 pair will add 0, i hope you get the points.

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

wow fast editorial fast rating change.. thanks for fast

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

Can someone help me with a smaller test case which fails my submission 90615069. Or point the mistake?

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

For problem B it says — "we can make (1,0) pair, (0,2) pair, and (2,1) pair as much as possible. After that, pairing the remaining values doesn't affect the sum" But after making (1,0),(2,0),(2,1) pairs shouldnt we also make (1,1) pairs to reduce the negative terms while summing?

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

https://codeforces.com/contest/1401/submission/90627708

can anyone please help me with this code getting WA in test case 5

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

    You're taking modulo before sorting, so the order is wrong.

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

      Thanks a lot.. :) stuck for more than 1 hour

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Good problem set !! :)

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

You can find elaborate video solutions to A-E (not F) here if you like videos, timestamps are in the description

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

My Solution for D resulting in memory limit exceeded. I can't figure out what went wrong. Please look into it. Thank you. https://codeforces.com/contest/1401/submission/90628962

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

Though the problems were good. But It would have been much better if at least one sample tests was considering the case m>n-1

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

For problem A,if the parity of n and k is same the answer is 0, otherwise the answer is 1 why it will always work?

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

    Suppose n=7 and I fix B at 6 and O is at 0 ,then k will be k=6-1=5 ; now fix B at 5 we get k=5-2=3 now suppose n=8 and fix B at 7 we get k=7-1=6 ; now fix B at 6 we get k=6-2=4 If you observe for n=7 we get k=5,3,1 ie. all odd numbers which can be easily found using 0 operation similarly forn=8(even) we got 6,4,2,0 (all even) for zero operations . So same parity of n and same parity of k for zero operation else 1 operation

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

In problem D, can someone tell me why my solution fails, please? I checked all the common mistakes (modulo before sort, more factors than edges), it doesn't seem that I fall into any of those categories.

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

    Never mind, worked it out myself — I had a problem with dfs, for chrissake

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

How not to mess up implementation of problem D today if you have one hour to solve it? I got the solution in 5 minutes but couldn't finish it You see my code during contest and after a slight change in it.

And tell me what improvement should I do, to not repeat them in future.

code during contest ->90617959

code after slight change -> 90630780

hoping someone will help me.

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

WA on test5 problem D .checked all common erros overflow,not taking mod for storing frequencies. D wa on test5

sorry didnt check properly.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    sort(all(fans),greater<lli>());
    

    after

    fans.pb((ans[i]*(n-ans[i]))%mod);
    
»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem E, I used ordered_set, but the same logic as in the editorial but it doesn't seem to be working for large test cases. Code — here

Help would be appreciated.

Edit — Found ! Thanks !

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

Best codes written. Hats off to you brooooo. Other editorialists use dirty templates. Templates so dirty that no one is able to understand. Why don't they understand that it is difficultto read codes, when untidy templates are used. Thanks for giving such clean codes.

Thank you so much. Again thanks.

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

Can some one elaborate on the proof for the second case in problem D ? Why is it guaranteed that the n-1 primes that are obtained from [p 0 , p1 ,p2 ,p 3, ... , p n-1 * p n *....*p m-1 ] are the maximum group of primes that can be obtained? I can see why if there is no MOD taken, but shouldn't the mod make things different?

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

    You're not trying to find the answer with the highest mod value, you're trying to find the exact answer first, and then mod it because it's too big

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

      Do you mean that because of the wording of the problem, this is the required answer but not necessarily the maximum answer that can be achieved ?

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

        The problem exists independent of the mod. You only take mod for the answer becuase handling such big numbers is hard(probably impossible).

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

Any idea why does this code not work for D? Code

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

I think there is another interesting way to solve the problem F using a lazy segment tree. The idea is to maintain the "lazy array" as a "segment tree" and then, the querie 2 and 3 are equivalent to updates in a range in the "segment tree" and the others queries are normal ones in the lazy segment tree. You have to keep in mind that you obtain the values of the "lazy array" with the "segment tree" in every moment. This way you can even do queries of type 2 or 3 in a certain range of blocks. What I mean is that not only works for the whole blocks of subarrays (update in the whole block of subarrays), but for certain range of blocks of subarrays. The complexity is O(n^2*q). Anyway, nice problemset bro!.

»
5 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

My solution for E:

By Euler's polyhedron formula, we have $$$V-E+F=2$$$ in a planar graph. We want to compute the number of faces of our planar graph, excluding the outside of the square, which is $$$F-1 = E-V+1$$$. For each segment (including the edges of the square), let's suppose that it has $$$v$$$ vertices lying on it. Then it contributes $$$v-1$$$ edges. Summing over all segments, $$$E = \sum v-1 = 2V-n-m-4$$$, since each vertex lies on exactly two segments and there are $$$n+m+4$$$ segments. Thus, $$$F-1 = V-n-m-3$$$. Computing $$$V$$$ is easy using sweepline.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    *In planar connected graph, which is why we need the assumption that all segments touch one side of the square. Without it the formula becomes: $$$V - E + F = 1 + C$$$

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

Humble Request. I am facing issue with understanding D problems how have we calculated no. of nodes in the separated component(d) of which we are calculating d*(N-d). Actually I did it using Dfs N-1 time on each node. I knew that it will give TLE. Whereas here it is done in one Dfs only. Can someone explain to me whether this is a general algorithm or anything like that or where can I learn it from more intuitively?

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

    Root arbitrarily the tree. Now let's compute $$$sz[u]:$$$ the amount of nodes on u's subtree.

    $$$sz[u] = 1 + \sum_{v\in G[u]} sz[v]$$$

    Now, for an edge $u, v$ (with $$$v \in G[u]$$$), the amount you want is $$$sz[v]\cdot(n-sz[v])$$$.

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

      Thanks i got it !!

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

      Hey why is sz[v].(n-sz[v]) coming? Like i didnt got the reason why it came.

      Thanks in advance

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

        edge parent->cur(or p->v) will be used sz[v]*(n-sz[v]) times in given function.

        Which is no nodes connected to edge p->v.(sz[v]=no nodes connected to v and n-sz[v]=nodes connected to node p

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

        Let's see, $$$G[*]$$$ donotes adjacency list of in the rooted tree. The directed edge $$$u \rightarrow v$$$ (with $$$v \in G[u]$$$), is counted on any path between each node in $$$v$$$'s subtree and each node not in $$$v$$$'s subtree. This amount is $$$sz[v]\cdot (n-sz[v])$$$.

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

My solution to D is running well on pc but giving wrong answer when submitted. Can anybody help me please https://codeforces.com/contest/1401/submission/90616879

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

.-. does anyone think that problem C is easier than B?

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

    yes, implementation wise B was hardest among A, B, C.

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

      yeh, I did B with a lot of if-else statements, but it still accepted XD

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Hindi Video Solution for Problem D 1401D — Maximum Distributed Tree Youtube Video Solution Link for Prolbem D (hindi)

please have a look

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

problem b ->

 long long int a0, a1, a2, b0, b1, b2;
        cin >> a0 >> a1 >> a2 >> b0 >> b1 >> b2;
        long long int ans = 0;
        ans = 2 * min(a2, b1);// we get +2 by this only
        // after that
        a2 = a2 - min(a2, b1);//number of 2 will be decrease by min(a2,b1)
        b1 = b1 - min(a2, b1);//number of 1 will be decrease by min(a2,b1)
       // then we have to handle -2 and this can be handle by converting 
/*-2 into 0 and this can be done by seeing the number  of 0 in a and number of
2 in a then (no. of 2 in b -(no. of 2 in a +no.of 0 in a)) is the number of -2 that we greedly convert it into  0.   */   
        if (a0 + a2 < b2)
            ans = ans - 2 * (min(a1, b2 - a0 - a2));
        cout << ans << endl;

code==>

 long long int a0, a1, a2, b0, b1, b2;
        cin >> a0 >> a1 >> a2 >> b0 >> b1 >> b2;
        long long int ans = 0;
        ans = 2 * min(a2, b1);
        a2 = a2 - min(a2, b1);
        b1 = b1 - min(a2, b1);
        if (a0 + a2 < b2)
            ans = ans - 2 * (min(a1, b2 - a0 - a2));
        cout << ans << endl;
»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Nice problems

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

In Problem B, I am using the same logic, then why I am getting the wrong answer.. https://codeforces.com/contest/1401/submission/90655781

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

Can anyone help me in finding why my code is giving WA on testcase 5. I used dfs to find the subtree size of node i, for all i, 1<=i<=n. Then used that subtree size to find the number of times some edge contributes to the answer. Then used greedy to find the maximum possible answer, and it matches the approach of the editorial.

Here is my submission.

90656681

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

    refer to this.

    It solved my problem for testcase 5

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

    I also had similar mistake try changing sort(all(e),greater<int>()) to sort(all(e),greater<long long>())

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

Can some body point out what's problem with my solution to Problem D.

upd- problem was taking mod before sorting resulted in wrong results. Refer to this

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

I got the thinking process of D but I am not able to prove it for $$$m \gt n-1$$$, someone please help in making the proof more simple. Thanks !

In particular I am not able to see why all the big primes will go to first weight and other all weights get only single primes...

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

    Let us consider $$$n$$$ weights and $$$m$$$ primes.

    I'm using 1-indexed arrays.

    We must take into account 2 facts.

    Let $$$W_i$$$ be the $$$i$$$th smallest weight, i.e. sorted in ascending order. Let $$$c_i$$$ be the coefficient of $$$W_i$$$. Let us prove $$$c_i<=c_j$$$ if $$$i<j$$$. We can swap any two coefficients and retain the total product. Let us assume $$$c_i>c_j$$$ and $$$i<j$$$. Then we can show $$$c_iW_i + c_jW_j <= c_jW_i + c_iW_j$$$. So it is optimal for $$$c_i$$$ to be non-decreasing.

    We can show that $$$c_iW_i + c_nW_n <= c_iW_i/k + kc_nW_n$$$ for some $$$k>1$$$. So optimal structure has all primes in $$$c_n$$$, as each prime shift is essentially just substituting $$$k$$$ as $$$p$$$.

    But since we need to minimize the number of ones, we need to give some primes to the previous values. So it also obvious that if there is more than 1 prime on some $$$c_i$$$ for $$$i<n$$$, it is optimal to shift it to $$$c_n$$$.

    Let us say that we gave a prime $$$p_j$$$ such that there exists $$$p_k$$$ such that $$$p_j>p_k$$$ and $$$p_k$$$ is in $$$c_n$$$. It is optimal to swap $$$p_j$$$ and $$$p_k$$$ as shown in the previous equation, $$$k$$$ for this swap is $$$p_j/p_k$$$ which is greater than $$$1$$$. Therefore the mentioned structure is optimal.

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

Can someone help me with a more formal proof for E?

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

    Hi Aditya,

    Here is a semi-formal proof. I mixed in graph and non-graph words, and realised midway that we do not really need the terminology for the problem.

    For each of the intersection points of the line segments, and each of the "dangling" endpoints of a line segment, we put a vertex there. The edges between these vertices are naturally formed. This gives us a planar graph which is also connected, as each line segment has one endpoint on the outer square. This gives, by Euler's formula,

    V-E+F = 2. This 2 includes the outer, infinite face, so F_finite = 1+E-V.

    Now, consider a "dangling" vertex (that is, a leaf vertex). We can delete this vertex along with the edge joined to it. This does not change the answer, as removing it decreases E and V both by 1.

    Now, consider two "internal" line segments (that is, one of the line segments other than the segments of the outer square) that intersect. This intersection increases E by 2, but increases V only by 1.

    Also, consider a line that completely crosses the outer square. Such a line segment increases E by 3 and increases V by 2.

    Therefore, our answer is

    1 + (number of intersections amidst the internal lines) + (number of internal lines that completely cut through the outer square).

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

Could the contest setters start giving solution code in Python too please?

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

If anyone need detail explanation & implementation of D Here

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

In problem D can someone explain why we are multiplying the largest prime numbers together(the case when m > n-1)? How do we prove that this is the optimal way?

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

Can anyone point what is the mistake here...as I have spent too much time on this problem and still unable to figure the bug out.

here is my code

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

https://codeforces.com/contest/1401/submission/90678039 My E submission is failing on test 5 :( Could use some help :P

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

Could anyone help me with debugging my code submission for problem D https://codeforces.com/contest/1401/submission/90679884 failing on test case 5 ? It seems ok to me.

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

    In your vector coef, don't take modulo. else { (10^7 + 4 ) < (5) } after computing modulo. Take it while computing the final answer.

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

problem C(Mere Array) can be done in one for-loop instead doing much stuff as given in editorial my submission link - https://codeforces.com/contest/1401/submission/90681298

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

    Yeah, I did it similarly. Sadly, after the contest ended :( .

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

    still nlogn time, you've used sort :)

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

    Can you please help with this solution of yours I'm not able to understand this approach

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

Can someone explain the intuition behind the $$$w_i$$$ and $$$z_i$$$ in D? How can I mathematically prove that it gives the correct distribution index for a particular tree?

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

in A) why are we searching for an m such that 2*m<=n only why not 2*m>n. The equality would give the answer: m=(n+k)/2 why is it not possible?? Though i understand the condition of checking parity will still hold, why was 2*m>n part not mentioned. Is it obvious??? or am i missing something? :D

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

this is my python solution

plz help me to find the error in my code. my solution gives runtime error in 6th test. thanks in advance

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

Can someone help me please I'm not able to understand how to approach this C problem.. Please..

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

Can someone tell me why this solution is giving TLE test 5{question D}. https://codeforces.com/contest/1401/submission/90657948

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

E is easier than I thought. What a pity, I had silly trouble with problem D and did not have enough time for E :((

»
4 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Here's a more straightforward approach for F:

Let's build a standard range sum Segment Tree. Aditionally, we will store which powers of 2 have been swapped (in a simple boolean array).

Note that a reverse operation of power $$$k$$$ is simply swapping of all powers $$$i$$$ such that $$$i < k$$$. We have now reduced the problem to just range-sum with updates and swaps.

Whenever you swap a certain size, just flip its value in the boolean array we created. Now, because a segment tree is based on dividing the array into segments of powers of two, it's pretty easy to perform the swaps. Let's say you have assigned children of node $$$p$$$ to be $$$2*p+1$$$ (left child) and $$$2*p+2$$$ (right child).

While traversing the segment tree for anything (updates or sums), you just need to flip the children if needed. That is, if the power of two that this node is responsible for is swapped, your left child will now be $$$2*p+2$$$ and right child will be the node $$$2*p+1$$$.

This is pretty straightforward, and only adds a couple of lines to your standard segment tree implementation. Handles swap queries in constant time, and the other two in $$$O(n)$$$.

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

    Nice approach!

    About: "Note that a reverse operation of power $$$k$$$ is simply swapping of all powers $$$i$$$ such that $$$i<k$$$". How did you notice this?

    Mmm I see, like it says in editorial reverse is doing xor with $$$2^k - 1$$$ and swap is doing xor with $$$2^k$$$. So $$$2^k - 1 = 2^0 \oplus 2^1 \oplus \ldots \oplus 2^{k-1}$$$.

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

      Maybe one of those things that just click :)

      I didn't think of the XOR approach explicitly as mentioned in the editorial (although it is pretty intuitive if you think about it). The equation you mentioned also makes sense.

      I initially tried to simplify the problem by only considering queries of one kind. Swapping seemed pretty easy to do with a segment tree, and naturally I realised that reverses are also just swaps!

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

    This is awesome. I was thinking on the same lines but just couldn't realize that reverse operation can be seen as swap.

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

There is a mistake in the editorial for F, $$$[l,r]$$$ should map to $$$[l\text{^}(x\&\text{~}(2^k-1)), r\text{^}(x\&\text{~}(2^k-1))]$$$ instead.

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

A very subtle mistake which can be done in the D question is that, while calculating the frequency of the edges, you might use modular multiplication, which will give the wrong answer, as very high edge frequency, under modulo might become somewhat lesser, and in the end when sorting the frequency array, it might be more towards the smaller side and hence answer obtained will be lesser than the actual answer.

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

Auto comment: topic has been updated by Anus1373 (previous revision, new revision, compare).

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

I still barely understand the proof of case m > n — 1 in problem D, that is why labeling the (m — n + 2) largest pi to the largest wi and the rest to the remaining wi results in a maximum answer? Let (w[1] > w[2] > ... > w[n — 1]) and (p[1] > p[2] > ... > p[m]). I'm able to prove that labeling a subsequence of pi of length (n — 1) to all wi and the remaining pi-s go to w1 will be optimal, but no idea for the remaining largest pi-s (those are p[1], p[2], ..., p[m — n + 2]). Could someone kindly elaborate on this more? Thank you in advance.

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

https://codeforces.com/contest/1401/submission/90728899 can anyone tell me what is wrong with my code.

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

Can someone please help me with this submission codeforces DIV 2 contest 665 problem D Link to Submission: https://codeforces.com/contest/1401/submission/90741918

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

The editorial solution of problem D, exceeds time limit.. What should we do now...90745003

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

I am curious about can we solve the problem C by using C++ sort() and passing a comparator function? And then checking whether it's sorted or not.

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

What is wrong with my submission?

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

Once again,I'm very much willing to recommand my blog for the Chinese editorial

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

In que C, it is given that we can rearrange only if the gcd(a1,a2) is the minimum element but the tutorial says only being divisible by the minimum is enough, can someone explain??

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

    Let a be the minimum element, and b,c two multiples of a. Then you can swap (b,c) by doing the three swaps (a,b),(a,c),(a,b).

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

Can anyone check my code of problem D 90800991 ?.Could you suggest how to overcome these type of errors while taking mod.

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

    You should use 64 bit type instead of 32 bit. Ie long long instead of int.

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

      We are taking modulus right I thought it would fit in int.Anyway tried but still not working 90801804.Is there anything wrong in the logic?

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

        You sort the edges by frequency, which is correct. But you sort after taking them mod, which is not correct.

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

can someone please tell me why there is tle in my code ,i think that every thing almost matches with the editorial,my code-> https://codeforces.com/contest/1401/submission/90820204 PROBLEM -D

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

What is wrong with my submission for B problem https://codeforces.com/contest/1401/submission/90863117

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

For Question E wouldn't the runtime complexity for a sweep algorithm using a segment tree set be O((m+n)*log(m+n)) instead of O(nlogn + mlogm)?

Suppose we are sweeping from left to right. Then we would need to stop at every x value that corresponds to {beginning of horizontal segment, end of horizontal segment, or a vertical segment}. This adds up to (2n+m).

And for the segment tree, if we were to use index compression, we would still have to include leaf nodes for both the y-values corresponding to horizontal segments and the top/bottom y-values for vertical segments to be able to efficiently obtain a range query. So this would add to (n+2m).

Another possible solution is to use an ordered set instead of a segment tree, and we would only store the y-values of active horizontal segments. And for every vertical segment we can perform the range query using lower and upper bound, which would be O(logm). But this would still lead to a runtime of O((n+m)*logm).

I'm mainly just thinking out loud here, but if anyone can confirm/refute what I have here your help would be greatly appreciated!

Edit: So I just realized that using lower and upper bound with an ordered set would require O(m) instead of O(logm) since finding the distance between two iterators in a data structure without random access is linear. So this would mean that the segment tree is the fastest option. But my point still stands that the time complexity is O((n+m)*log(m+n)).

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

How does Problem C solution work for

Ex. 4 24 12

Although 24 and 12 are divisible by 4 they can't be swapped as their GCD is 12 but from the tutorial it looks like they can be swapped.

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

1401D — Maximum Distributed Tree. My solution is failing on 5th (where n=100000) test case, I think its most probably because of overflow. I am not able to debug it. It would be kind if someone could explain where I went wrong.

Thanks in advance!

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define int long long
const int mod = 1000000007;

using namespace std;

const int lim = 100005;
int m,n;
vector<int> nodes[lim];
short visitedNodes[lim];
priority_queue<int> q;
priority_queue<int> p;

int dfs(int node) {
    visitedNodes[node]=1;
    int t,subs=1;
    for(const auto& i : nodes[node]) {
        if(visitedNodes[i]==0) {
            t = dfs(i);
            subs=(subs+t)%mod;
            q.push((t*(n-t))%mod);
        }
    }
    return subs;
}

int32_t main(void) {
    ios
    int T;
    cin >> T;
    int x,y;
    for(int i=0;i<lim;i++) {
        visitedNodes[i]=0;
        nodes[i].clear();
    }
    for(;T--;) {
        cin>>n;
        for(int i=0;i<n-1;i++) {
            cin>>x>>y;
            nodes[x].push_back(y);
            nodes[y].push_back(x);
        }
        dfs(1);
        cin>>m;
        for(int i=0;i<m;i++) {
            cin>>x;
            p.push(x);
        }
        x=1;
        for(int i=0;i<m-n+2;i++) {
            x=(x*p.top())%mod;
            p.pop();
        }
        p.push(x);
        x=0;
        while(!q.empty()) {
           if(!p.empty()) {y=p.top();p.pop();}
           else y=1;
           x=(x+((q.top()*y)%mod))%mod;
           q.pop();
        }
        cout<<x<<"\n";
        // cleanup
        for(int i=1;i<=n;i++) {
            nodes[i].clear();
            visitedNodes[i]=0;
        }
        q={};
        p={};
    }
    return 0;
}
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone find out where i'm going wrong. I did everything by following editorial and i dont know where im going wrong. Link-https://codeforces.com/contest/1401/submission/91049767

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

problem c: mere array:- how is it nlogn ?

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

i am new in cp but any one see in problem C that their clearly mention *If gcd(ai,aj) is equal to the minimum element of the whole array a, you can swap ai and aj * .but when i see tutorial answer was without mention about GCD. so is tutorial was wrong OR Problem.

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

Can anyone explain problem 2 for me I am really unable to understand why he eliminated (1,0) and (0,2) and didn't even consider (2,0) or (2,1). I am new to this any help would be great. Thanks!

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

DIV 2 PROBLEM B

My solution...

My solution is working but I am doing more calculations than editorial, please explain where I am wrong.

Am I doing unnecessary calculation in my code?? HOW??

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

Anus1373
I wonder why you use for(;t--;) unusual isn't it? Is there any special reason? I have seen most of the people using while(t--).

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

In problem C, suppose we have {2,3,9,6}. Then how will your code as given in tutorial work?

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

Alternate O(nq) solution for F:

Make a standard RSQ segment tree. Define the 'level' of a node in the tree as log2(size of range covered by node). The level of the root is obviously n.

An operation "swap k" can be simulated by swapping the left child and right child of all nodes with level = (k+1).

An operation "reverse k" can be simulated by swapping the left and right child of all nodes with level <= k.

The swap and reverse operations can be done fast with a lazy propagation type optimisation. After this, it's just basic query and updates on a segment tree.

My code for this: https://codeforces.com/contest/1401/submission/92201994

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

EDIT: found the mistake

Help needed !

Can someone please help me find my mistake in problem E's solution? I have been stuck on it for many days now, so help would be much appreciated!

My WA submission: 92319896

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

For problem D, when counting the number of vertices after removing one edge, don't we get a complexity of n². Since there are n-1 edges, and n vertices ?