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

mohammedehab2002's blog

By mohammedehab2002, history, 4 months ago, In English,

1325A - EhAb AnD gCd

$$$a=1$$$ and $$$b=x-1$$$ always work.

Code link: https://pastebin.com/ddHKD09B

First AC: Sevlll

Bonus task: can you count the valid pairs?

1325B - CopyCopyCopyCopyCopy

Let the number of distinct elements in $$$a$$$ be called $$$d$$$. Clearly, the answer is limited by $$$d$$$. Now, you can construct your subsequence as follows: take the smallest element from the first copy, the second smallest element from the second copy, and so on. Since there are enough copies to take every element, the answer is $$$d$$$.

Code link: https://pastebin.com/hjcxUDmY

First AC: socho

1325C - Ehab and Path-etic MEXs

Notice that there will be a path that passes through the edge labeled $$$0$$$ and the edge labeled $$$1$$$ no matter how you label the edges, so there's always a path with $$$MEX$$$ $$$2$$$ or more. If any node has degree 3 or more, you can distribute the labels $$$0$$$, $$$1$$$, and $$$2$$$ to edges incident to this node and distribute the rest of the labels arbitrarily. Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges, since there will be a path with $$$MEX$$$ $$$n-1$$$ anyway.

Code link: https://pastebin.com/u4H7Dtbd

First AC: vintage_Vlad_Makeev

1325D - Ehab the Xorcist

First, let's look at some special cases. If $$$u>v$$$ or $$$u$$$ and $$$v$$$ have different parities, there's no array. If $$$u=v=0$$$, the answer is an empty array. If $$$u=v \neq 0$$$, the answer is $$$[u]$$$. Now, the length is at least 2. Let $$$x=\frac{v-u}{2}$$$. The array $$$[u,x,x]$$$ satisfies the conditions, so the length is at most 3. We just need to figure out whether there's a pair of number $$$a$$$ and $$$b$$$. Such that $$$a \oplus b=u$$$ and $$$a+b=v$$$. Notice that $$$a+b=a \oplus b+2*(a$$$&$$$b)$$$, so we know that $$$a$$$&$$$b=\frac{v-u}{2}=x$$$ (surprise surprise.) The benefit of getting rid of $$$a+b$$$ and looking at $$$a$$$&$$$b$$$ instead is that we can look at $$$a$$$ and $$$b$$$ bit by bit. If $$$x$$$ has a one in some bit, $$$a$$$ and $$$b$$$ must both have ones, so $$$a \oplus b=u$$$ must have a 0. If $$$x$$$ has a zero, there are absolutely no limitation on $$$u$$$. So, if there's a bit where both $$$x$$$ and $$$u$$$ have a one, that is to say if $$$x$$$&$$$u\neq0$$$, you can't find such $$$a$$$ and $$$b$$$, and the length will be 3. Otherwise, $$$x$$$&$$$u=0$$$ which means $$$x \oplus u=x+u$$$, so the array $$$[u+x,x]$$$ works. Can you see how this array was constructed? We took $$$[u,x,x]$$$ which more obviously works and merged the first 2 elements, benefiting from the fact that $$$u$$$&$$$x=0$$$.

Code link: https://pastebin.com/7XuMk1v8

First AC: MiFaFaOvO

1325E - Ehab's REAL Number Theory Problem

Notice that for each element in the array, if some perfect square divides it, you can divide it by that perfect square, and the problem won't change. Let's define normalizing a number as dividing it by perfect squares until it doesn't contain any. Notice than any number that has 3 different prime divisors has at least 8 divisors, so after normalizing any element in the array, it will be $$$1$$$, $$$p$$$, or $$$p*q$$$ for some primes $$$p$$$ and $$$q$$$. Let's create a graph where the vertices are the prime numbers (and $$$1$$$,) and the edges are the elements of the array. For each element, we'll connect $$$p$$$ and $$$q$$$ (or $$$p$$$ and $$$1$$$ if it's a prime after normalizing, or $$$1$$$ with $$$1$$$ if it's $$$1$$$ after normalizing.) What's the significance of this graph? Well, if you take any walk from node $$$p$$$ to node $$$q$$$, multiply the elements on the edges you took, and normalize, the product you get will be $$$p*q$$$! That's because every node in the path will be visited an even number of times, except $$$p$$$ and $$$q$$$. So the shortest subsequence whose product is a perfect square is just the shortest cycle in this graph!

The shortest cycle in an arbitrary graph takes $$$O(n^2)$$$ to compute: you take every node as a source and calculate the bfs tree, then you look at the edges the go back to the root to close the cycle. That only finds the shortest cycle if the bfs source is contained in one. The graph in this problem has a special condition: you can't connect 2 nodes with indices greater than $$$sqrt(maxAi)$$$. That's because their product would be greater than $$$maxAi$$$. So that means ANY walk in this graph has a node with index $$$\le\sqrt{maxAi}$$$. You can only try these nodes as sources for your bfs.

Code link: https://pastebin.com/4ixLQyvg

Bonus task: try to prove the answer can't exceed $$$2\sqrt{maxAi}$$$.

1325F - Ehab's Last Theorem

Let $$$sq$$$ denote $$$\lceil\sqrt{n}\rceil$$$.

A solution using DFS trees

If you're not familiar with back-edges, I recommend reading this first.

Let's take the DFS tree of our graph. Assume you're currently in node $$$u$$$ in the DFS. If $$$u$$$ has $$$sq-1$$$ or more back-edges, look at the one that connects $$$u$$$ to its furthest ancestor. It forms a cycle of length at least $$$sq$$$. If $$$u$$$ doesn't have that many back-edges, you can add it to the independent set (if none of its neighbors was added.) That way, if you don't find a cycle, every node only blocks at most $$$sq-1$$$ other nodes, the ones connected to it by a back-edge, so you'll find an independent set!

Code link: https://pastebin.com/b9phCSW8

First AC: imeimi

A solution using degrees

There's a pretty obvious greedy algorithm for finding large independent sets: take the node with the minimal degree, add it to the independent set, remove it and all its neighbors from the graph, and repeat. If at every step the node with the minimal degree has degree $$$<sq-1$$$, that algorithm solves the first problem. Otherwise, there's a step where EVERY node has degree at least $$$sq-1$$$. For graphs where every node has degree at least $$$d$$$, you can always find a cycle with length $$$d+1$$$. To do that, we'll first try to find a long path then close a cycle. Take an arbitrary node as a starting point, and keep trying to extend your path. If one of this node's neighbors is not already in the path, extend that path with it and repeat. Otherwise, all of the last node's $$$d$$$ neighbors are on the path. Take the edge to the furthest and you'll form a cycle of length at least $$$d+1$$$!

Code link: https://pastebin.com/1VwZYPCj

First AC: imeimi after only 11 minutes!

There are probably other solutions and heuristics. Can you share yours?

 
 
 
 
  • Vote: I like it
  • +288
  • Vote: I do not like it

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

woa, so fast, I feeling so good to know how to solve those. Thanks alot for your effort

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

Could anyone please tell me why this was giving TLE? https://codeforces.com/contest/1325/submission/73271304

Thanks!

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

    It's the submission for C

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

    you're using python and your algorithm is n^2

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

      Actually, the set size will never grow more than 3 elements (the inner loop). It looks N^2 but it's not

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        for i in range(n-1):
            u, v = map(int, input().split())
            if u not in graph:
                graph[u] = {i}
        

        i believe this is n^2 but I don't know python either

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

          Oh, graph is a dictionary here (HashMap), constant lookup.

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

            python dict worst case is O(n),so the whole complexity of code becomes n^2. https://wiki.python.org/moin/TimeComplexity

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
            Rev. 2   Vote: I like it +1 Vote: I do not like it
            temp = ""
            for j in range(n-1):
                if j in graph[maxi]:
                    temp += str(w) + "\n"
                    w += 1
                else:
                    temp += str(t) + "\n"
                    t -= 1
            

            this part is the reason for TLE. As in python strings are immutable so it creates new. It takes O(n) time and make it O(n**2). Instead, use a list to print results.

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

    most likely when n is 1e5 to 1e7 the solution will require a complexity of n or nlogn but if you have n^2 you will get TLE and i will advice that you try to use java/c++ due to their time efficiency and great stl algorithms and data structures which will make solving problems more fun

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

      Sir, it's not N^2. Could you please see my above reply to bleh0.5

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

        if it runs in n ir nlogn then it should pass i am not good at python but it may be helful to check the complexity of python core function it may cause overhead and wish you more luck in figuring the problem out

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

    Hey it's because of python only. Thanks to Pajenegod and c1729 copy the template i am using for future purposes it has fast io. submit the code in pypy2 and also be careful while printing it works like python2 in pypy2.:)

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

      oh is it so? It's so frustating and unfortunate that python is slow. Thanks a lot!

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

    How about input optimizing? input — slow method, use alias:

    import sys
    input = sys.stdin.readline
    

    But the main problem is partial reading. It could be too much faster if you'd read all lines, for example:

    n = int(input())
    lines = sys.stdin.readlines()
    

    Good luck!

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

      Really Cool. Thanks for looking at the code!

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

    I think it's because your complexity is $$$O(n^2)$$$. Take a look at these lines:

    temp = ""
    for j in range(n-1):
        ...
            temp += str(w) + "\n"
    

    String addition costs $$$O(n)$$$ in Python, and you do it $$$n-1$$$ times. Sometimes it's optimised away, but not always, so you shouldn't count on that. Here's what you could do instead:

    temp = []
    for j in range(n-1):
        ...
            temp.append(str(w))
    print("\n".join(temp))
    
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'll keep that in mind from now. Thanks a ton!

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

    my java solution also initially timedout. I used fast output, it passed. May be fast input output is the key!

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

    Your code works in Python but times out in PyPy. Don't know why. Usually PyPy is faster than Python.

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

    It looks like one reason PyPy might be slower than Python for your code is that PyPy is slower when you use very large dictionaries. That was a comment I read here: https://stackoverflow.com/questions/7063508/pypy-significantly-slower-than-cpython

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

In problem D, there is a formula a+b=a⊕b+2∗(a &b), how to prove its correctness? I couldn't find a proper google keyword for it.

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

    It basically splits the result into directly added bits ($$$a \oplus b$$$) and carried bits (a & b), which should be moved one to the left since they are carried over (same as multiplying by 2).

    I know that's not a real proof, but hopefully you can see why this works. In terms of googling, half-adders might be useful: https://en.wikipedia.org/wiki/Adder_(electronics)#Half_adder

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

    One can visualise the equation using Venn diagrams

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

      I still can't get it. Can you please show us the diagram? Thanks

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

        I already understand it, but I didn't use the Venn's diagram approach. Here is how I visualize it:

        Imagine all bit position where bit in a is different with bit in b (this is a^b). If we sum a and b, all these positions contribute (a^b) to the sum.

        Now imagine all bit positions where bit in a is the same with bit in b (this is a&b). If we sum a and b, all these positions contribute 2*(a&b) to the sum.

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

          I understood the equation but I couldn't understand the proof and sorry your statement doesn't contain a proof.

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

        See retrograd's video at that timestamp: https://youtu.be/fpxArbp3FLo?t=8456

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

In editorial for problem D, what does this mean "if u and v have different parities, there's no array"

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

    "u and v have different parities": either (i) u is odd and v is even or (ii) v is odd and u is even

    "there's no array": no such solution exists

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

    For example, if xor-sum has least significant bit = 1 and sum has 0, there is no answer. Similarly with xor ending in 0 and sum ending in 1.

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

      Can you explain why solution will not exist for different parity u and v?

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

        Don't think too hard. Just focus on the very last bit (right most). Parity means whether the last bits are same or not.

        • A=....0, B=....0, Then A^B = .....0, A+B = .....0.
        • A=....0, B=....1, Then A^B = .....1, A+B = .....1.
        • A=....1, B=....0, Then A^B = .....1, A+B = .....1.
        • A=....1, B=....1, Then A^B = .....0, A+B = .....0.

        XOR and ADDITION acts same on last bit. Hence the XOR and ADDITION should end with same bits i.e should have same parity.

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

          Got it! Thanks.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But that's only the case where in you are assuming that array size is 2

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

        from the equation, a+b=a^b+2(a&b) you can see that a+b-a^b=v-u=2(a&b), which shows v-u is divisible by 2, because of 2 as a multiplier. that could only be possible if v and u both have same parity, otherwise their difference would not be multiple of two and above equation will not hold.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        An easy way would be to think like this. If the last bit of u is set(=1) this means that number of times the last bit occurs should also be odd(in all array number) and if last bit is occurring odd number of times then v should also be odd(check by binary addition). Hence the contradiction.

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

    it means that no array if one is even and other is odd

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

    except u == 0 and v == 0 it is not possible that same parity u, v can have a valid array same parity means (u % 2 == v % 2) different parity means (u % 2 != v % 2)

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

    It also means that difference of u and v is odd.

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

Such a fast editorial !!!

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

Thanks for the quick editorial !

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

Bonus task 1325A : A. 1 for odd numbers(?) B. 2 or more for even numbers : {n/2,n/2}, {1,n-1}, ...

Can you help me out how to find these 'more' numbers?

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

How did u judge the solutions of problem C?? I mean there are a variety of solutions..

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

    To check if a solution is wrong, just check if on a path between 2 edges containing val. 0 & val. 1 contains edge with val 2 or not.

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

      I labeled three edges with 1-degree vertices as 0,1,2. So it should be the correct solution, right? But it didn't pass pretest 3.

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

Isn't problem C can be solved by sorting edges according to number of times it occurs in any of the path in ascending order then label each edge from 0 to n-2 in this order?

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

Why in problem C we need to check node with exactly three or more edges?

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

    let's say that a node has degree 3 so we can put values 0,1,2 in the three edges .. If you observe carefully after this step there wouldn't be any path that contains 0,1,2 together hence MEX(u,v) will be at most 2. The same is true for a degree greater than 3 too. Hope this helps.

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

      Thanks! Helped!

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

      I don't think so . There is one case where degree three and arbitrary combination of 0,1,2 will fail . Check this out https://imgur.com/4P89Jga

      In the first diagram max MEX value comes out to be 6 In the second diagram max MEX value is restricted to 3 only

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

        how come the max MEX is 6 in the first case .. I guess its 1 ?

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

          MEX of vertex (2,7) in first diagram . Degree of vertex 3 is 3 so we have assigned 0,1,2 to the three edges now labels from (2,7) are 1,2,3,4,5 so MEX(2,7) comes out to be 6.
          The maximum value of MEX comes out to be 6

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

            MEX(2,7) contains weights 1,2,3,4,5 not 0 . Hence MEX(2,7) = 0

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

              Wait ....so 0 is allowed ? UGHHHHHH Same mistake every time . Half of my headache comes from either not reading the problem correctly or assuming something that isn't there in the first place . Thanks for pointing it out tho

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

      i cant understand the problem C, can you please explain

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

    if number of node in tree is more than 2 then ans is always greater than or equal to 2(because edge with number 0,1 will always have MEX 2). now if we have node with three edges then we can write 0,1,2 on these edges and now any path cannot contain all of these three edges. so MEX cannot be greater than 2.

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

    Not necessary, you can do it with simpler way.

    First notice that max(MEX) will never be less than 2, since no matter how we assign weights, there will always be some pair of nodes (u,v) such that the path from u to v has the edges bearing the weights 0 and 1. In short, max(MEX)>1 for any tree configuration or arrangement of edge weights.

    Now that we know that max(MEX) is at least 2, we can simply find the edges having one of their extremities as a leaf, and assign to them the least unassigned weight starting from 0. That is, if we have k leaves, surely k<n, assign the value 0,1,2,3,4,...,k-1 to their corresponding edges.

    Note that a node is a leaf if and only if its degree is 1 and thus we only have one edge issued to a leaf node.

    This way of distribution of weights ensures that there will never be a path that contains the edges of weights 0,1 and 2 at the same time, since those 3 edges are all connected to leaves. Therefore we ensure that max(MEX)=2 , irrespective of the distribution of the weights left , that are: k,k+1,k+2,...,n

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

      Your last conclusion isn't true --->> Therefore we ensure that max(MEX)=2 , irrespective of the distribution of the weights left , that are: k,k+1,k+2,...,n

      This is true only if any of the node has a degree at least three otherwise no matter how you put up the weights , you'll end up getting maximum MEX(u,v) equal to n-1 . And here's a counter example. 4 1 2 1 3 3 4 So the answer will be just n-1 and here you get 0,2,1 at the same time.

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

        Yes you are definitely right, thanks for correction. I missed this point. But the algorithm still applies however.

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

      Im.new to graph theory..and I couldn't even understand the problem Statement..it would be really helpful if someone can explain it to me :(

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

I was debugging D for about an hour, and then five minutes before the end wrote a solution in python — it worked)) Actually, could someone tell me why C++ solution fails (I suppose it's something to do with overflows, but can't figure out)?

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

    In line 32 you should use long long instead of int

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

Woa..A great contest and a quick editorial... Really appreciate this... Thanks alot for your effort

»
4 months ago, # |
  Vote: I like it +40 Vote: I do not like it
Another way to think about DFS solution for F
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Omg, so stupid of me!! It seems that this construction was so deep in my habits, I wrote it unconsciously — but now, surely, I won't make the same mistake. Thanks so much!

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

    Hello, inspired by F, I wonder if it is correct if I enumerate the root and use dfs tree in E. But I got an WA on test 151.. Here's my code .Actually, I think this method may be incorrect because dfs tree is used to get the longest cycle.

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

      This is test 151: https://codeforces.com/contest/1325/hacks/625397 (so it means your solution would pass during the contest xD)

      It looks like this with middle cycle of length $$$13$$$, and all other of length $$$14$$$ (those vertices are $$$1$$$ and primes less than $$$1000$$$, which gives exactly $$$169$$$ vertices), whilst all larger primes are connected to vertex $$$1$$$

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

        Interestring, I think I now fully understand. If at least two of the edges in the middle cycle are not in the dfs tree, the middle cycle can't be found.

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

    Can you give some proof that if a node has sq-1 backedge,then there surely exists a cycle of length atleast sq.

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

The solution to problem E is truly beautiful!

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

    can you explain the editorial. Why are we diving with perfect square?

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

    true I figured everything but got stuck on getting the Length of the smallest cycle the final trick is amazing!

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

How to solve C ? Please explain simply .

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

    First notice that max(MEX) will never be less than 2, since no matter how we assign weights, there will always be some pair of nodes (u,v) such that the path from u to v has the edges bearing the weights 0 and 1. In short, max(MEX)>1 for any tree configuration or arrangement of edge weights.

    Now that we know that max(MEX) is at least 2, we can simply find the edges having one of their extremities as a leaf, and assign to them the least unassigned weight starting from 0. That is, if we have k leaves, surely k<n, assign the value 0,1,2,3,4,...,k-1 to their corresponding edges.

    Note that a node is a leaf if and only if its degree is 1 and thus we only have one edge issued to a leaf node.

    This way of distribution of weights ensures that there will never be a path that contains the edges of weights 0,1 and 2 at the same time, since those 3 edges are all connected to leaves. Therefore we ensure that max(MEX)=2 , irrespective of the distribution of the weights left , that are: k,k+1,k+2,...,n

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

      thank u so much .. :D

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

      It's satisfying to know, what i thought during contest was correct. But it is more disappointing to know my code during the contest failed only one test case . Case no 19:: 2 1 2

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

        Same, my dumb ass realized this after wasting 40 mins because I thought test 19 wouldn't be something so simple :(

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

        Oh haha I failed at test 19 too. But fortunately I figured it out quickly. Usually, when your code fails at tests like 19 (later tests) it means that probably your general solution is correct but you didn't consider corner cases. Otherwise, if such corner cases are tested too early, you might falsely think that your solution is totally incorrect which would be worse.

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

      Great explanation:):)!!

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

    Sort nodes according to their degree and then assign numbers from 0 to n-2 to the children.

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

In D how can we say that the max length of such an array can be at most 3?

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

    Because ,u (v-u)/2, (v-u)/2 always work.

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

      Is there any formal proof of it?

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

        If you know that $$$a \oplus a = 0$$$ and that $$$a \oplus 0 = a$$$ then it's obvious why that works:

        $$$u \oplus \frac{v-u}{2} \oplus \frac{v-u}{2} = u \oplus (\frac{v-u}{2} \oplus \frac{v-u}{2}) = u \oplus 0 = u$$$

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

          Hey, Can you please answer my following questions?

          1. If v-u is odd, why isn't there any solution?
          2. If (u & (v-u)/2) ==0, how are we sure of two numbers to be u + (v-u)/2 and (v-u)/2?

          I have a hard time understanding bit operators. Thanks

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

            since a^b=a+b-2(a&b) now you are given a^b as u and a+b as v therefore u=v-2(a&b) 2(a&b)=v-u as our ans is [a,b] as elements of the array in case there exists 2 elements therefore v-u has to be even for a solution to exist.

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

              Got it. This is in case of two numbers.

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

      Why cannot it have more than 3 elements in the array?

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

        We are supposed to find minimum possible length, and for any u, v such that a valid array exists we have an explicit way to construct an array of length 3, thus the optimal solution can't be more than 3

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

          Pardon me. Let n be the number of elements in the required array.

          For:

          1. n= 2: we use a+b = a⊕b + 2∗(a&b) to find a and b.

          2. n= 3: u, (v-u)/2, (v-u)/2 is the answer if v-u is even.

          Suppose both the above case fails, then why are we not checking for n= 4, 5, 6... ?

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

            $$$a \oplus b \equiv a + b \mod 2$$$. And this can be inductively generalized to $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n \equiv a_1 + a_2 + \ldots + a_n \mod 2$$$, so if $$$v - u$$$ is odd, then there is no answer.

            And in the same manner knowing that $$$a \oplus b \leq a + b$$$ we can conclude that if $$$v < u$$$ there is no answer as well.

            So if both those cases fail there is no answer.

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

              How come a⊕b≡a+b mod2 consider a=2 and b=5 then how the above holds?

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

              Pardon me again. But I don't understand why are we not checking for n= 4, 5 ...?

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

                If case with $$$n=3$$$ failed then $$$v-u$$$ is either odd or negative and in both cases I proved in a comment above, that there is no way to construct a valid array

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

                consider the case of three numbers (v-u)/2,(v-u)/2 and u. The xor of these three numbers will always be u as (v-u)/2 xor (v-u)/2 is equal to 0. Hence for every case, we can say that the minimum length array will be 3.

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

    You can refer to the contest GOODBYE2019. The problem C's solution used the same method (0 xor x == x, x xor x == 0) as well.

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

When will there be rating changes?

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

Can anyone tell that why the mentioned link solution give WA for problem D when checking whether array of length 2 is possible or not https://www.geeksforgeeks.org/find-two-numbers-sum-xor/

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

I think the First AC of E is in the middle of F

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

Bonus task for E:
Let T = sqrt(maxAi)

A cycle of length K has atleast ceil(K / 2) vertices with value <= T.
Because if it didn't, it would mean that two vertices that are > T come next to each other in the cycle, which isn't possible as their product would exceed maxAi.

So if the length of the smallest cycle more than 2T, it would mean that at least T + 1 vertices in the cycle have value <= T.
Which means a vertex repeats in the cycle, causing a smaller cycle to exist. Reaching to a contradiction.

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

I'm interested to know why the $$$D$$$ problem preferred an empty array if $$$u = v = 0$$$ rather than an array of a single element $$$= 0$$$

Here are my solutions along with explanations if anyone wants to refer

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

I don't understand this part of explanation for C: Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges, since there will be a path with MEX n−1 anyway. If n=4, and I label *---0---*---2---*---1---* none of the paths will have MEX higher than 1, will they?

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

    The path from one leaf node to the other leaf node will definitely have a MEX equal to n-1.

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

Randomized solution to F

First try some permutations (10 seems enough to pass tests) of the vertices and then check for independent set greedily.

If we haven't found any independent set let's do the following until we get an answer: shuffle all the edges and then run dfs. Inside the dfs if we look at a used vertex lets try to make it the cycle.

I don't know how to prove it works fast, but it does. I guess it's just close to the editorial solution.

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

    Other random solution:

    Shuffle everything and do a dfs at the same time as greedily taking vertices to the independent set. Stop if you find a good set or a good cycle.

    Do that until it gets AC :D

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

      I'm investigating further and it seems that if we couldn't find a big independent set we will have to run dfs for cycles only once! I'm just too weak to prove it...

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

        Of course you should run dfs only once, because if I understand correctly what you are doing is a correct algorithm for finding the longest cycle in the graph

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

          Well, of course it's not true because not every dfs tree gives the longest cycle. It's not hard to come up with an example.

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

    I also have the same idea. But I didn't implement it in the contest. Because I didn't have proof about it in the probability. Can anyone prove this?

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

non-greedy solution for problem D 73264903

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

    Can you please explain the approach you have used to solve it?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it
      1. obviously if u > v the answer is -1
      2. you need to solve it bit by bit
      3. let's keep the count of bits that will construct the required numbers in arr
      4. initially you have a sum and you want to distribute it on some numbers to give you the required xor.
      5. if there is a 1 in the current bit in xor you need to leave a bit in this position in arr from the sum you have
      6. after distributing the bits on the xor, there will be a remainder, you don't wan't this remainder to affect the xor, so divide the remainder by 2 and put 2 bits in the positions that has 1 in the binary representation of the remainder.
      7. if the remainder not divisible by 2, the answer is -1
      8. now you need to construct the required shortest array of numbers, so iterate over the arr and try to remove the maximum possible number of bits from it and put them in a number, do this operation untill no bits is left in the arr
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What is the need of dividing the remainder by 2 and putting the 2 bits in the positions having 1 in the binary representation of the remainder?

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

Question D was great... looking forward to participate more of your rounds in future :)

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

How to solve A ? Please explain simply

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

    gcd(x-1,1) = 1 lcm(x-1,1) = x-1 answer is 1 and x-1

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

    we know that gcd of 1 with any positive number is always 1 and in the given question x>=2... so if u will take a=1 and b=x-1... we know b>=1 since x>=2 so now gcd of 1 and x-1 is 1 and lcm of 1 with any other number is equal to other number (e.g.-lcm of 1 and 4 is 4)... so now lcm of 1 and x-1 is x-1 so the gcd + lcm of 1 and x-1 is (1) +(x-1) =x .Let me know if it's still not clear to you.

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

mohammedehab2002 If u doesn't have that many back-edges, you can add it to the independent set (if none of its neighbors was added.) That way, if you don't find a cycle, every node only blocks at most sq−1 other nodes, the ones connected to it by a back-edge, so you'll find an independent set!

How you deduce this type of facts so easily. How to come up with a good proof which requires this type of things.

»
4 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Problem statement of especially C was not well enough and unclear.The algorithm of D has no proof.It is nothing but a result from searching find two numbers whose xor and sum is given .. Not a good contest !! Problems should be more classy.

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

    its hard to come up with proof for constructive problems. u need a good intution and guess. gutt feeling should be strong. otherwise u will keep on thinking on it forever. practice more and more to get familiar.

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

    there was an announcement that explained the example stated in problem C. I solved problem D by proving it for sure! Otherwise, I wouldn't be able to solve it. It doesn't mean that if you couldn't solve a certain problem, then the contest is bad. Instead, the problems that you couldn't solve teaches you new algorithms,techniques and ideas!

»
4 months ago, # |
  Vote: I like it -29 Vote: I do not like it

in problem D, we don't have to print the answer with minimum length of array.so,the answer 1 1 1 1 1 1 1 1 1 1 is true for pretest 7,but I got WA because "the jury had a shorter answer" than me.

please fix this,mohammedehab2002!!

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

    I guess we have to!!!

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

      The statement says:

      Given 2 integers u and v, find the shortest array such that bitwise-xor of its elements is u, and the sum of its elements is v.

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

        Oh yes.I was wrong. sorry jury!sorry codeforces!

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

can anyone explain the problem statement for the 3rd question

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

In problem D, how can we prove "u and v have different parities, there's no array"? Maybe there is some relation that I am missing.

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

    Bitwise xor is like addition if we threw away all the carry bits, but obviously carries don't affect the least significant bit (parity). If we add an odd number of odd numbers, the sum and xor will both be odd. If we add an even number of odd numbers, the sum and xor will both be even.

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

    If i^th bit of u is 0, it means that there are even number of 1's at that bit position, and if there are so, the sum of even number of 1's will leave 0 at that bit. Hence, i^th bit of v must be 0 if i^th bit of u is 0.

    Similarly, you can make an argument for when i^th bit of u is 1, i^th bit of v has to be 1.

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

Here is how I thought about D: First take care of the impossible cases and u=v=0. Let's start off with an array that satisfies the xor condition, then modify it until it satisfies the sum condition.

So let's start with just the array $$$[ u ]$$$. We need to add $$$v-u$$$ somehow without changing the xor. For the $$$i$$$'th bit that is turned on in the binary representation of $$$v-u$$$, we can add two elements with value $$$2^{i-1}$$$, which doesn't change the xor, and let's do this for each on bit in $$$v-u$$$. Now note that the sum and xor is only affected by the number of on bits in each position, so instead of adding new elements, we can keep track of how many on bits in each position we need and try to squeeze them into as few elements as possible. Clearly we never need more than 3.

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

How to prove the answer for C is always correct by the editorial above.

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

    because we can't draw a simple path passing via a node including more than 2 edges that are incident on that particular node.

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

How to prove ( a+b=a⊕b+2∗(a&b) ) in problem D ?

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

    Visual proof using Venn diagrams:

    proof

    Note that A + B is not actually union, its actual addition.
    Hence, both the complete circles will be added.

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

where can i learn stuff like: a+b=a⊕b+2∗(a&b).

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

Easy-to-read problem statements, good difficulty distribution, and interesting problems. To top it all, an editorial that was written 3 weeks ago! Nicely done!

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

can anyone explain how the graph works in E

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

And why is the time complexity of the solution for E is O(sqrt(MAXA)). Shouldn't it be smth like O(sqrt(MAXA)*MAXA), because you firstly bruteforce over the sorce (O(sqrt(MAXA))) and then build the bfs tree (which is O(MAXA))

OK, that was not the time complexity, sorry about that useless coment

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

    Can you tell why the time complexity is not O(sqrt(MAXA)*MAXA).

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

mohammedehab2002 In problem E — Bonus Task, how about answer can't be more than ~170.

Proof — Worst case is when there is a chain numbers — (2*3), (3*5), (5*7), ..., (991*997), (997 * 2) after 997, numbers will exceed the bound on Ai — 10^6.

Correct me if I am wrong..

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

    Well, not exactly, but yes I gave a generous bound. You can prove the answer is at most 2*169. The worst case is a chain 1-big prime-2-big prime-3-big prime-5-big prime....-997-big prime-1. The proof is exactly what sinus_070 said in his comment above + the fact that all the nodes are primes.

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

can anyone explain the question C ?? i am trying for the last 2 hours and still not able to understand the question. i read the tutorial and code but still the question is not clear.

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

    What MEX means is minimum excluded number for any pair of u and v between all the edges coming in between for coming from u to v some numbers are appearing and you have to make sure the MEX is not too large for it. For eg by arrow I mean a connection is present 2->3->4->5 here 2,3,4,5 are vertices and you can consider 2,5 as pair in short all the edges in this must have edges such that the MEX the number which has not appeared should me minimimum

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

My solution for E based on parity of Prime factors power{ if even then they form a perfect square } of each number in the input, I have two choices for every number pick it or leave it then if I picked it, does it get the answer or not ?! that was my solution but I got TLE, anyone could help thanks in advance

here is my solution

https://codeforces.com/contest/1325/submission/73290435

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

Can Anyone explain problem E logic, I still haven't understood the Editorial?

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

Nice contest, gg :3

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

Can someone recommend me XOR related problems?

Thanks!

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

I gave my 3rd contests. I am unable to solve even A problem. Only solved A problem of Educational. Can anyone suggest some links that I should prepare from first??

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

In problem C we can simply give the leafs lowest weights as there does not exist a simple path in a tree containing more than 2 leaves 73306866

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

How to solve bonus task for problem A?

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

In problem 'D' , why the array does not exist if the parities of 'u' and 'v' differ ?

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

    If you do not carry an odd integer, It is impossible to generate different bit after applying XOR and SUM on any array of ones and zeros.

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

In question E , I am not able to understand how to get shortest path cycle in less than O(n^2)

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

    The naive approach is to fix the root of the bfs tree and then run a bfs to compute the shortest cycle which passes through the fixed root. Now since our graph is special and it is not possible to have an edge between 2 vertices u and v if both of them are bigger than $$$\sqrt{maxA}$$$, you can check only with roots smaller than $$$\sqrt{maxA}$$$.

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

    Because there does not exist an edge $$$(u, v)$$$ such that $$$u>\sqrt{\max a_i}$$$ and $$$v>\sqrt{\max a_i}$$$. Suppose that there is an edge $$$(u,v)$$$ in the shortest cycle, then we just need to take the $$$\min(u,v)$$$, which is must be within $$$\sqrt{\max a_i}$$$, as the source node and run bfs.

    Since all nodes are prime numbers, $$$\sqrt{\max a_i}=1000, \pi(1000)=168$$$, we just need to bfs at most 168 times, and the total time cost is about $$$\mathcal{O}(\pi(\sqrt{\max a_i})\cdot n)$$$

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

Fine :D

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

In problem c testcase number-61 is wrong . in these test case graph is not forming tree.

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

    This definitely looks like a tree, atleast to me.

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

      Thank you bro, i was misunderstood the question and i thought that its binary tree's question but i was wrong its only tree's question

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

I wrote another solution to the F problem using dfs trees. I have described it here.

https://codeforces.com/blog/entry/74800

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

So,bros,Can we solve F in this way.We find bccs in the graph and check whether there are a bcc,whose size is not less than sq,if not we sort the nodes as their degree,and add as many nodes into the independent set as possible. And I have some implenment problem. If we know the nodes in a simple circle,how can I print them in the order.Can someone answer me,Thanks bros!

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

I have a different approach to D. Consider $$$ dp[u][v] $$$ to be $$$ -1 $$$ if no solution exists for given $$$ (u, v) $$$ and $$$ a $$$ if $$$ a + b = v, a \oplus b = u $$$.

Now consider the last bit of $$$ u $$$ and $$$ v $$$.

If they differ, the answer is definetely $$$ -1 $$$. Otherwise, there are two cases.

If the last bit of $$$ u $$$ is $$$ 1 $$$, then the last bit of $$$ a $$$ is definetely $$$ 0 $$$ (or it is definetely $$$ 1 $$$, depending on which one you like better, we may pick either of them as long as we are consistent in our definition of dynamic program). But then you must be able to construct $$$ (u \gg 1, (v - 1) \gg 1) $$$, so if $$$ dp[u \gg 1][(v - 1) \gg 1] = -1 $$$, then $$$ dp[u][v] = -1 $$$, otherwise $$$ dp[u][v] = dp[u \gg 1][(v - 1) \gg 1] \ll 1 $$$.

The second case is $$$ u \bmod 2 = 0 $$$. Then last bit of $$$ a $$$ may be $$$ 1 $$$ or $$$ 0 $$$, so all you can say is that you must be able to either construct $$$ (u \gg 1, (v - 2) \gg 1) $$$ or $$$ (u \gg 1, v\gg 1) $$$.

I don't really know why the number of states is low, there could be an exponential blowup in the number of states in the second case, but apparently it doesn't happen. If somebody has a proof for that, it would be interesting.

Submission: 73345383

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

Didn't want to write a blog for this, so posting here. Why are we seeing " Rating changes for the last round are temporarily rolled back. They will be returned soon." so often? Is there a particular reason for doing this after ( almost ) every round?

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

I don't understand the problem C Editorial. Can anyone help me understand it more clearly? As in every case max(Mex(u,v)) over all u and v nodes will be n-2, so why can't we directly output numbers till n-2.

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

for solution of probelm f using dfs i could not understand why this is " If u has sq−1 or more back-edges, look at the one that connects u to its furthest ancestor. It forms a cycle of length at least sq" can anyone help me please .

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

    Since there are no multiple edges, each back edge will go to a different ancestor. Each ancestor will be at a different depth from the root. In the worst case, one ancestor will be u's parent, i.e 1 level above u, another 2 levels above u, the next 3 levels above u ans so on....
    Therefore, it's guarenteed that the furthest ancestor will be atleast sq-1 levels above u, and hence, connecting it to this ancestor will form a cycle of length sq-1+1=sq

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

There is another solution for c. One can start filling all leaves edges from 0,1,2.... and then can fill inner leaves with an arbitrary value.

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

For problem E why is not enough to make a dfs and check every back edge to find the minimum lenght of a cicle?

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

    Yeap, I got it: (1-2) (1-5) (1-4) (2-3) (4-5) (4-3) In this graph for a dfs like 1-2-3-4-5, we don't detect ( 1 — 4 — 5 )

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

I have written the code for Problem E, but it's giving me TLE. Here's my submission. I think the problem is in the way I am finding the shortest cycle. Can anyone tell me more exactly where am I going wrong? I did the same as in the editorial- for all node x find the shortest cycle including node x.

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

Hello! Could anyone tell "can we find longest simple cycle using DFS tree"?

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

can anyone plzz explain me the question no c...i.e C.Ehab and Path-etic MEXs

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

My solution for F


For cycle of length sqrt: compute the height of every vertex using DFS. Look at all the edges. If the vertices differ by a height of (sqrt-1) or more, then they complete a cycle of length at least sqrt.

For independent set of size sqrt: Use a priority queue to find the next vertex with the lowest degree. Add it to the set. Remove all its neighbours from the graph, and reduce the degrees of the neighbours of the removed neighbours by 1.

Submission link: https://codeforces.com/contest/1325/submission/73650985

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

Yet another idea for D: There's a solution using two numbers if and only if $$$[\frac{v+u}{2},\frac{v-u}{2}]$$$ works.

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

Here are video editorials.

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

From the problem C editorial:

Otherwise, the tree is a bamboo, and it doesn't actually matter how you label the edges.

Please do not use such terms like "bamboo" in an editorial (or at least care to mention that you are talking about the shape of the real-life tree). It took me some time to conclude that this was not a computer science term.

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

For problem F, this is stated in the second approach: "If at every step the node with the minimal degree has degree ≤ sq−1, that algorithm solves the first problem." By solving the problem we mean finding a independent set of size sq.

Now, note that EACH of the first (sq — 1) nodes (that we choose for our independent set), in the worst case, will delete sq nodes (sq — 1 nodes connected to it, and one itself). Thus, before we are able to add the last node to our independent set, we have already deleted sq*(sq-1) nodes from our graph.

Note that there exist several n such that sq*(sq-1) > n (take n=17,18,19 for trivial examples, they have sq=5). So, according to this, we should not be able to add the last node for such values of n.

This contradicts the editorial however. So, where did I go wrong?

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

    Hi!

    Sorry, I had a small mistake in the editorial. I proceed to solve the cycle problem if the node with the minimum degree has degree $$$\ge sq-1$$$, so in order to solve the independent set problem, its degree is strictly less than $$$sq-1$$$ in every step, and it removes at most $$$sq-1$$$ nodes, not $$$sq$$$.

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

include<stdio.h>

int main( ) { int t,c,n,d,i,j,swap,count=0; scanf("%d",&t); for(c=0;c<t;c++){ scanf("%d",&n); int array[n]; for(d=0;d<n;d++) scanf("%d",&array[d]); for(i=0;i<n-1;i++){ for(j=0;j<n-i-1;j++){ if(array[j]>array[j+1]){ swap= array[j]; array[j]=array[j+1]; array[j+1]=swap; } } } for(j=0;j<n;j++){ if(array[j]== array[j+1]) { count++; } } printf("%d\n",n-count); count=0; } } It is the best solution in C.

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

In problem E, I don't get the intuition of why why we build a graph with prime labels only. My attempt is to build graph with vertices being 1, p, p*q. And then the edges being 1, p, p * q. For each node, the next node label * edge label normalized. However, this means that edges can be repeated. How do I get from this attempt to the editorial's solution?

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

In editorial of F, it is said that " If u has sq−1 or more back-edges, look at the one that connects u to its furthest ancestor. It forms a cycle of length at least sq." Can someone elaborate why should there be a cycle of length atleast sq..??

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

can anyone describe me the solution of A??

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

    Assuming d is GCD(a,b) we have:

    a=d*p
    b=d*q
    

    we have LCM(a,b) = d*p*q.

    x = LCM(a,b) + GCD(a,b) = d*p*q + d = d(p*q + 1).
    

    Since numbers a and b are picked arbitrary by us, we can try choose d = 1. Therefore, x = p*q + 1.

    LCM(a,b) = p*q = x - 1. 
    

    Let's take p = x .- 1, then q = 1, and that's satisfies all statements above. Which is exactly what editorial saying :-)

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

In D,if u>v no solution exists....but why?

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

If at every step the node with the minimal degree has degree < sq-1 , that algorithm solves the first problem..I dont quite understand how

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

Can someone help me with python ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
**MY SOLUTION FOR C**

    As Given that we have a tree
    and we are considering path for every pair of nodes
    so paths can be of 3 types
    1) leaf to leaf
     In this case
     a) if number of leaves >2 so still some edges containing leaf node as one of the edges 
     exist
     b) if number of leaves==2 so structure is bamboo like and is of no concern

    2)leaf to non-leaf 
    and
    3)non-leaf to non-leaf
    In both the cases we  definitely will have some edges containing leaf node as one of the 
    edges exist

    So from above cases you realize can realize that any path you consider
    some leaf-edges will remain(not contained in that path choosen) at end of the day..

    So Greedy approach to give the leaf edges numbers from 0,1,2..
    and non leaf edges n-2,n-3..
     * 
    How I got this Idea
    I considered the following cases
     * 
    1--2--3--4
    Best solution 0 2 1  since max(MEX(u,v))is 1
    will in all other configurations answer is 2
   [MY submission:](http://https://codeforces.com/contest/1325/submission/81356364)
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the solution for problem E? (I am not understanding the editorial)

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

can someone help me with my solution for F

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

    Ah, the two necroposters who made me wonder why the contest problems and editorial are different.