Bakry_'s blog

By Bakry_, history, 2 months ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +267
  • Vote: I do not like it

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

Wow, that was quick.

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

The contest was awesome, Even system testing was fast :D

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

In problem D, you can do binary search directly on the bfs order (search for the shortest prefix having value same as the value of whole array) which will save 1 query I think.

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

    Also, Dfs order of edges without Euler tour traversal will work in 11 queries, But we didn't want to make the problem harder so we let ETT solutions pass.

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

      I think D can be solved in around $$$1 + 1.25 * log(N)$$$ querys for a general graph, by doing ternary search over the sets of nodes, even if edges from the graph are hidden. Sadly that was 1 extra query and i couln't solved it that way. Anyways, awesome problemset!

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

      _runtimeTerror_ Bakry_ I do understand why ETT works, but could you please explain why your approaches work?

      UPD: Already realized what's happening when using bfs/dfs. Just accepted it, 130744806 is my solution using bfs. Thanks!

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

      yes i did this solution i think that the euler tour solution is much harder to realize though

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

      found it (Euler tour traversal)

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

      I used a centroid decomposition solution, which passed in 11 queries for all system tests. However, there is a construction that makes it use $$$1 + log_{\sqrt{3}}n \approx 13$$$ queries. The construction is basically the pattern shown below, recursively expanded.

      130697675

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

        Could you elaborate on it being log in base sqrt(3)? I also did centroid decomposition

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

          Basically, this construction makes it so that the size of the tree only decreases by a factor of 3 every 2 queries.

          In the tree above, assume that 1 is a set of 334 nodes, 2 is a set of 333 nodes, and 3 is a set of 332 nodes. The solution edge is somewhere in set #3.

          In the first query, the algorithm would query all of the nodes in set #1 and determine that the solution edge is either in set #2 or set #3.

          In the second query, the algorithm would query set #2 and determine that the solution edge is somewhere in set #3.

          We can then recursively construct the same tree structure in set #3.

          As you can see, we have used up 2 queries, but only decreased the size of the tree by a factor of 3. This means the algorithm will use $$$1 + log_{\sqrt{3}}n$$$ queries, which is just barely over the limit.

          I was able to hack your submission using a very similar test case.

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

            Thanks a lot!

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

            how are you always sure to reduce the tree by a factor of 3 at least?

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

            I was also doing sort of centroid decomposition. If you have the time, you can try to hack my submission too. It passed all the hacks so far.

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

              I just hacked your submission. I'm pretty sure that any solution involving centroid decomposition can be hacked. Thanks for letting me know and making the test set stronger.

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

                Thanks, I agree.

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

        thanks man

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

Thanks for the quick editorial

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

It was a miracle. compared to current speed of posting of editorials.

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

B is Great!!!

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

Check out my blog please -> My first blog!

Put in lots of effort! :)

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

Loved problem E.

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

    Can you please explain how to do E in detail?

    I can't understand so as to how to find the lower boundary ?

    How will you construct a mask for this and check for odd and even cases?

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

      Let ith bit is most important bit, that means, for all bits greater than ith bits, xor = AND = 0. So what you want is, when we are assuming ith bit is most important bit, can we somehow have only bits greater than equal to i, in each number of array and remove their lower bits. This can be achieved by taking bitwise AND of all numbers with a number which has bits>=i as set and bits <i as unset. All you need now is, in this modified array max length subarray with xor = 0.

      130719800

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

What was the intuition to B? like I got to know that what will work but what is the line of thinking (approach) to solve this problem ?

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

    My approach: We cannot move an element if i-x < 0 and i+x > n-1 (i is the index of the element), so its index must same as in the sorted array. We can swap the rest of the elements as we want.

    My Solution

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

      What a lovely idea. I thought about something like this but still coudn't complete this idea. Thanks!

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

      can you tell me what should be the output for** ~~~~~ n= 5 x=3 arr[]= 5 4 3 2 1** ~~~~~

      and how?

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

        YES

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

        It took me about an hour to realize that this problem just involves 2 simple ideas. 1. If an element is movable with another element, then that element can go to any other element which is swappable. This means that no matter what the given elements, you can always place the movable elements into their correct position. 2. If the element is not movable, we have to check if the element is already in the correct position and if it is not then we say NO. If all are in the correct position, say YES. The solution is just to make another array which is the sorted input and check all the non-movable elements, ensuring that they are in the same position in the original as they are in the sorted. Non-movable elements are those that are not able to be swapped anywhere, meaning that if you add x to its index or subtract it, it will go out of bounds of the array. For example, in 3 1 2 x = 2, 1 cannot be moved and is not in the correct position so it is NO. In the example you asked, 5 4 3 2 1, all elements are movable so we can say YES.

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

      I did the same thing

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

      Really cool solution btw

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

You could just sort the edges and do binary search on D

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

    fucking great idea,sad to realize this after contest...

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

    What is the reason for sorting?

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

      none really. I just tried a few test cases and it seemed to work

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

      You could do it on the bfs order.

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

    sorting mustn`t work in this task... guess tests are week maybe

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

nice contest. fast systest and editorial :D

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

Thanks for the fast editorial. For problem C, may I ask that how do we find the two required edges to break the tree into 3 parts with xor sum of each component equal to x in O(n) or O(n lg n) time? I have been trying to solve this problem but I am stuck at the implementation.

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

    I saw the update in the editorial. Thanks for explaining it!

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

I Think, in problem A, ans should be "H / (x + y)" multiple by 2

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

    we've corrected it in the editorial

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

Thank you for a great round and fast editorial!

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

Thanks for the contest, good pretests and quick testing!:)

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

Thanks for fast editorial!

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

Are there any provements for C that the deepest subtree erase is always right?

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

    If we do not choose the deepest subtree we might mistake choosing a subtree which has three (2n+1) subtrees in itself who individual XORes is equal to the XOR of all the nodes in the given tree. And unfortunately we might not find any other subtree with the required XOR.

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

Problem D could've been solved relatively naively due to the limit being $$$n < 10^3$$$, ie. without any consideration in which order to process edges. Simply maintain the set $$$E$$$ of suspected edges and traverse graph in any way you like (in my case it was DFS) until you enumerate $$$|E| / 2$$$ suspected edges (for the binary search part; edge set will be denoted as $$$E'$$$). Collect all the visited nodes into a single query, and if this query gives the same result as the initial query for the whole graph, set $$$E = E'$$$. Otherwise, $$$E = E \setminus E'$$$.

Of course, each time we print a large portion of the tree just because we enumerate zounds of "unsuspected" edges. What I mean to say is that there was no need for consideration of Euler tours nor to care about efficient implementation.

Btw, this makes IO load equal to $$$O (n log n)$$$ rather than amortized $$$O(n)$$$ as in editorial.

Also, I liked this problem a lot :)

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

    Could you please explain why is it O(N log N)?

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

      Most cases you will enumerate lots of edges that are not in set $$$E$$$, because we queried about them already. In other words, almost every query will be about a set of O(n) vertices. There are O(log n) queries, thus O(n log n) vertices printed in all the queries.

      For example, imagine a path of length 512. First you enumerate ~256 vertices. If the sought-after edge is not there, in the next query, if you start dfs from the same source, you need to query 256 + 128 = 384 vertices rather than just 128 (because first 256 vertices enumerate only edges not in $$$E$$$, and you need to print a whole connected component). Etc.

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

        Though I checked my submission 130706195 and it seems that during the round I mitigated this problem, because I stored the visited component as a set of suspected edges from this component (the $$$qry$$$ variable). And instead of querying vertices from the whole component, I print only those adjacent to at least one $$$qry$$$ edge. It seems that this trick makes all queries to contain at most $$$n + 2n - 2$$$ vertices in total = $$$O(n)$$$.

        Anyway, $$$O(n log n)$$$ should pass as well (ie. if you stored vertices from the component rather than edges).

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

In problem A ans=(h/x+y)*2

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

    we've corrected it in the editorial

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

Could anyone please explain me that why does this submission 130717510 to D fail because I guess that this approach was fully correct. Moreover can anyone explain me why does this submission pass 130725042. I cannot find any valid reason for this and am doubting this to be a case of bad test cases

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

Can anybody disprove the following?

We can split into 3 components if we can find a subtree (not the tree itself) that has $$$xor$$$ equal to the $$$xor$$$ of the whole tree.

I am getting wrong on the test 10, with this idea. Solution.

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

    Assuming that other nodes count is > 1, you guarantee that you can split them into 2 components with equal xor value, but this value is not necessarily = the whole tree xor.

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

    1
    3 69
    2 2 3
    1 2
    1 3

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

Now this is a great round. A-C were creative and easy to code, D required some implementation, E was just beautiful and no "fancy" algorithms appeared until F2, the hardest problem.

A perfect example of how div2 rounds should be prepared.

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

rel-a-table

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

balanced div2

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

Systest for C seems to be weak. I wrote something nonsensical (count all edges that can split the graph into zero and the target xor value). But it can be uphacked with this simple test case:

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

For problem D maybe my solution can be hacked because my basic idea was finding maximum edge at first by 1 query. After that split the tree to 2 trees so that new smaller trees have 1 common node and their union is current tree. Also while choosing this 2 trees we are minimizing their size difference. Now after splitting we can easily ask one query about them and determine which one includes max edge and continue to process until our tree has only 2 nodes. This works quite well but I can't create worst case scenario If you know how to do it please share your ideas. my code

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

    My friend hacked my solution post-contest with randomly generated trees.

    My solution selects half of the remaining nodes by starting from a random node and dfs, and repeat if necessary.

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

    Hacked with a tree, where each node has $$$9$$$ children. $$$n=820$$$, it has $$$3$$$ layers, and in the worst case it is $$$4$$$ question to handle each of them. $$$3*4+1>12$$$. I think a similar construction works, where each node has $$$5$$$ children.

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

How can E be solved in $$$O(NlogN)$$$? According to editorial, it looks like the time complexity should be $$$O(N^2 logN)$$$

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

    I only know a solution in Nlog(max A), I think the editorial meant that it's solved by iterating k giving total complexity N(logN ?)logmaxA. One observation you can do is that you can split the array into intervals [x, y], where for all positions k is set, and then find tho positions which are furthest apart with the same xor (in the interval [x-1, y]), but with the same parity of indices.

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

In problem E, shouldn't be $$$r-l+1$$$ is even, instead of odd?

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

Problems were really good

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

As always, here are the video solutions to the first three problems : solutions

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

It would be great if you could add a "model" solution for every problem, but that is not necessary.

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

great contest loved it

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

It's not solution but I want to share idea about 1592D - Hemose in ICPC ?. You should know that tree is bipartite graph. Let's say one partition is array a, and other partition is array b. Request answer for 1,2,...,n. Let's say it's r. Now, repeat following:

  • if partition a bigger than b, just swap them.
  • now split array b (array of vertices) into two halves c and d, or closest size. Because in bipartite graph each edge goes from one partition to other, we get that edges connecting a and c are different to edges connecting a and d, and together they make whole set of edges between a and b.
  • ask about vertices a + c.
  • if result is less than r, then say new partitions are a and d, otherwise new partitions are a and c.

Do this until we get 1 vertex in both partitions. I didn't proof how many requests it does in worst case, but I guess it's around 17 (case 500 size of both partitions). So it's a little bit more than we can afford. Sad. But very easy to implement. 130691922

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

    For some reason, if I remove isolated vertices each time before the check for swap, then it get wrong answer, but it should be request limit exceed if idea above is correct. Something is wrong. 130827040

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

      I found bug. Proof above is wrong.

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

        Can u help me on problem D? I have submitted two solutions for problem D 1592D - Hemose in ICPC ?. One of them is giving wrong answer. I can not figure out why this is giving wrong answer. Here is my submission:131034503.

        Basically I am doing binary search on dfs traversal of nodes.

        Here is the submission which is giving correct answer.131035225

        Basically I just removed this condition

        while(high-low<1)
        

        in binary search to

        while(low<high)
        

        and started low from 1 instead of 0. here euler is zero indexed and binary search is done on those indexes.

        I have submitted this query below but thought it would be better if i posted it here

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

The contest was fun, but i think the editorial is kinda bad. For example, on E, what is "which can be solved easily in O(NlogN)" supposed to mean? If you're not gonna explain the solution at least put code so people can learn what to do.

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

I can't figure out why this one is not working (I know its messed up but my idea was correct and just changing the line V[i].second to x>i resulted in AC. (I wasn't able to do that in contest). Help me to avoid such mistakes ahead.

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define mod 1000000007
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
#define PB push_back
#define MP make_pair

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin>>t; 
    while(t--)
    {
       int n,x; cin>>n>>x;

        vector <pii> V;
       vector <int> M;

       FOR(i,0,n)
       {
         int b; cin>>b; V.PB(MP(b,i+1)); M.PB(b);
       }
        bool ok=0;

       sort(all(V));
       {
           FOR(i,0,n) if(M[i]!=V[i].first){ok = 1; break; }
       }
       if(!ok) {cout<<"YES\n"; continue;}

       if(x>=n) {cout<<"NO\n"; continue;}

       

       bool val=0;
       FOR(i,0,n)
       {
           if(M[i]!=V[i].first) {
               if(V[i].second>n-x and V[i].second<x+1) {val=1; break;}
           }
       }
       if(val) cout<<"NO\n";
       else cout<<"YES\n";

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

me: thinks I can pass 1000 this round

codeforces: nope, here's your 999

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

For problem C, not all submissions are evaluated beyond test 39, some submissions fail on test 42, for example this one 130707908

Test 42 :-
1
5 3
1 1 1 1 3
1 2
2 3
3 4
4 5
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B - checking — if the elements of the subarray [n−x, x) i.e. [n-x, x-1] in the original array are in their same position after sorting the array, as bellow, worked fine. But, I didn't get the tutorial's last line.

The editorial talks about the subarray [n-x+1, x] instead. Can anyone please clarify?

    if(n-x >= x) return true;

    for(int i = n-x; i < x; i++){
        if(a[i] != b[i])
            return false;
    }
    return true;
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice contest

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

Can someone break my idea for D? Im finding the centroid of the tree and doing a knapsack to find the value closest to n/2 you can get by summing subtrees of the children of the centroid and do a query with those subtrees + the centroid. If the value you get by doing it is less than the answer, you remove all those children from the tree (i.e mark them) and repeat that algorithm until i have 2 nodes.

Code: 130722106

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

why we multiple by 2 in problem a?

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

    Because we're using two weapons. Think of the case where h = 10 and the two weapons are 5 and 4

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

      bro i don't understand all equations for problem a Can you explain them?

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

        Assuming you understood the first part of the editorial:

        The ammount of times we can be 100% confident we can use both weapons will be h/(x+y) (the ammount of times we can fit both of them in h).

        That would cost (h/(x+y))*2 operations and leave h-(h/(x+y))*(x+y) hp remaining (each time we take x+y hp off, and we will do it h/(x+y) times). We can notice that this is the remainder on the division of h by (x+y), or h mod(x+y) or in c++ h%(x+y).

        Since the hp remaning after that will be smaller than x+y, you will either use x or x and y if it is bigger than x.

        If you still cant get it, do some cases by hand and/or read the editorial and this comment again

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

Hemose Bakry_ there is unproved part for C. "If you can partition the tree into m components".. how do I prove this?

Can you please help in proving if these (below) are the components with every one of them with xor=x, we can have another set of 3 legal components?

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

    you cant partition into those components in the first place because you cant get that by removing edges

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

    For every partition into $$$m \ge 3$$$ components with all of them having xor equals to $$$x$$$ there is also a partition with $$$m - 2$$$ componenets where every component has xor equals to $$$x$$$.

    The main idea is if you have a partition with $$$m \ge 3$$$ components then there exists a component where you removed at least $$$2$$$ edges from it to other $$$2$$$ different components, otherwise the initial graph is not a tree. Let's say these three components are $$$A$$$, $$$B$$$ and $$$C$$$, as $$$xor(A) = xor(B) = xor(C) = x$$$ then $$$xor(A) \oplus xor(B) \oplus xor(C) = x$$$ ($$$\oplus$$$ is xor operation). So if you don't remove those $$$2$$$ edges, you create a partition with $$$m - 2$$$ componenets.

    Since a partition with just $$$1$$$ component is not valid for this problem, you should focus on solutions with $$$2$$$ and $$$3$$$ components.

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

In problem C, Can anyone explain how do we search for the 2 edges in the tree?

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

    Video explaining the idea

    Basically once we fix the first edge, I explain how all edges fall under 2 categories:

    1)An ancestor to its parent and

    2)A vertex from a disjoint subtree of an ancestor to its child Then I explain how we can check for these 2 cases in the DFS.

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

      Thanks a lot. I am loving the codeforces community

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

    Suppose the three components have xor equals to $$$x$$$. Traverse the tree (you could do bfs/dfs/whatever) if you find a subtree with xor $$$x$$$ then remove the edge which joins this subtree with the tree itself. Then traverse the remaining tree and find another subtree with xor equals to $$$x$$$ and again remove the edge which connects it to the remaining tree and done!

    You can proof that if there is a solution then you find one by doing this and if there is no solution, well, it's straightforward to see that you won't find one by doing this.

    PS: here is my solution using dfs.

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

    Or you can also just count number of edges (say cnt) s.t the subtree corresponding to these edges have xor = 0 or xr (=xor of whole tree)

    ans = (cnt >=2 ? "YES" : "NO")

    My submission: 130710063

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

F1 and F2 are one of the best F problems I have seen before: It's really difficult to come up with the correct ideas, but the solutions are quite short.

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

In the editorial of F2, perhaps "if" is spelled wrong in the last paragraph:(

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

    "if and only if" is sometimes shortened to "iff". Link.

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

      Oh, I have known that know. Sorry for my poor English:(

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

Can someone give me a solution to D problem in simpler words, I just can't understand it from the editorial.

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

    check this URL to understand what is euler tour https://www.geeksforgeeks.org/euler-tour-tree, and we generate an euler tour array from the input tree, then use binary search to find the edge with maximum dist

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

      Why does binary search in the Euler Tour yields the right answer?

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

        Let's define Dist(u,v) as the greatest common divisor of the weights of all edges on the path from node u to node v.

        means the maximum dist in this tree is simply a maximum weight edge from u to v, because a >= gcd(a,b) for all positive integers

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

          I understand that. What I don't get is: how do you know that when you choose the midpoint in the binary search, you're not "breaking an edge"? In other words, how do you know that all the edges you have to consider will be either in the left or the right part of subarray you're considering?

          PS: I can see why that won't happen in the first 2 splits, but I can't see why it'll never happen.

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

            there is no way to break an edge since we only do binary search on nodes, in one search we decide to search the node's left or node's right (here left/right means left/right in euler tour array)

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

              1 2 3 2 4 2 1 5 6 7 6 5 8 5 1

              Assume the answer is edge 5-6. Let's say that the first binsearch split gives you:

              6 7 6 5 8 5 1

              Now, the second split will query either

              "6 7 6" or "5 8 5 1"

              and neither has the answer (5-6).

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

                in the second split we will split the arr into (6,7,6,5) and (5,8,5,1), then ask whether the left part has the maximum.

                here's my code

                        while (l + 1 < r) {
                            int m = (l + r) / 2;
                            get arr from euler arr[l,m](l and m inclusive)
                            int t = ask(arr);
                            if (t == target) {
                                r = m;
                            } else {
                                l = m;
                            }
                        }
                
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it +4 Vote: I do not like it

                  Why does the second split will split into (6,7,6,5) and (5,8,5,1) rather than (6,7,6) and (5,8,5,1)?

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

      Thanks for the explanation got it.

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

A question Regarding problem B

In the problem B , suppose the main array is ar[] and the sorted version of it is br[].

Now , if (i-1) >= x or (n-i) >= x , ith element can be moved to anywhere . If it is not true , then ar[i] has to be equal to br[i].

This same thing does not work when I reorder the indices according to sorted array and then check for each sorted index . Why ??

I meant , let the array of reordered indices is cr[].

Then , if (cr[i]-1) >= x or (n-cr[i]) >= x , cr[i]th element can be moved to anywhere . If it is not true, the ar[cr[i]] has to be equal to br[i].

But this one gave me WA . Can anyone tell me why ??

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

    maybe it is because same numbers.(not sure). // I also have a question .could you help me? my code my code always shows wrong answer expected YES, found NO [1109th token] or wrong answer expected NO, found YES [1109th token]. I cant find reason.

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

Nice Contest and finally I have become a PUPIL.

I was able to solve both A and B within 45 mins for the first time and got stuck at C without knowing trees .

Can anyone explain E please?

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

    nice bro i was stuck on B for almost the whole contest lol had to solve C and D and I found them much easier than B :(

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

Hey, I think my logic for problem B is correct but it is giving wrong answer on testcase 2. My approach is to find out all possible position where I cannot swap and if my sorted position lies in that region then that element cannot be placed their. I have not seen the editorial.

Here, is my submission: https://codeforces.com/contest/1592/submission/130760624. Please, let me if my approach was wrong or tell me the testcase which does not pass this approach. It would be really helpful.

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

In D can't we just take half the edges every time?

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

    We can't do this in simple way. Because edges are defined by vertices we ask. So if we want to check edges (1,2) and (3,4) just two edges, then answer to our question will also may have edge (2,3) if (2,3) is connected in initial graph.

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

      r57shell, can you explain why the binary search on the Euler Tour will never "leave edges behind"? Like, edges whose one endpoint is to the left of the midpoint and the other endpoint is to the right. I understand that that won't happen on the first or second split, but it's not clear why that won't happen as the binary search progresses.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        Explanation turned out to be long
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But when you go through (u, v) the first time, you add "u v" to the Euler Tour. The second time you go through (u, v), you add "v u". Assuming the answer is (u, v), isn't it possible that one of the binary search splits will put "u v" in separate segments ("u | v"), pick the segment that contains "v u" (since that is the answer) and later on another binary search split will put "v u" in separate segments ("v | u") and now the answer won't be in either segment?

          Maybe you tried to answer that, but I still can't see why that wouldn't happen...

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

            Ah, you should not do that. You should cut segment by half of its edges, it's not the same as to cut array of vertices into two halves. You either take edge u->v or not take. If in first choice is M edges, then in other is N-M edges where N is total edges (not vertices).

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

              That's what I figured. I tried that in my latest submission, but my code ended up asking more than 12 queries. I'll try and fix the code, but glad to know that I got the idea right. Thank you!

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

    Lets say we did simpe dfs and got edges as {1,2} {2,3} {1,4} {4,5} {1,6} {6,7}

    Now lets query for first three edges

    query({1,2}{2,3}{1,4}) === query(1,2,3,4) To ask a query about a set of k nodes v1,v2,…,vk (2≤k≤n2≤k≤n, 1≤vi≤n1≤vi≤n, all vi are distinct)

    we get the max gcd and max gcd edge was actually there in our query edge set. But what if we query last three edges

    Query ({4,5} {1,6} {6,7}) === query (4,5,1,7)

    Note that result of this query we will get, would still be max gcd, coz 1 and 4 is present in the query and so the edge {1,4} . However, our edge set for this query didn’t have this edge.

    So, we need to use edge set formed using Euler tour.

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

For F2, I don't think we need to search for all the values of k in: 0<=k<=K, because using the second operation once saves us one coin (with type one operation we will use 3 coins and with type 2 we will use 2 coins). The only corner case is by using the second operation we might change a[n][m] from 0 to 1, but even in that case, it can be rectified with just one additional coin which was our profit from the last type 2 operation we made.

Thus using the maximum number of type 2 operations always works :)

Thanks for an amazing contest and a really amazing set of problems. Liked the E problem especially.

I hope you would do this change in F2's tutorial so that it becomes slightly easier for the viewers to understand and code :)

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

Can anyone help me in the solution to Problem B. I have used the same logic as the editorial, yet the tests give me a runtime error. This is the link for my submission- 130775373. Where exactly is the error? Could someone also give the corrected version?

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

finally a specialist =)

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

in problem E how do you check the condition that pref[r] ^ pref[l-1]==0 fast?

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

The Observations in the Div2 C question is same as this question — https://codeforces.com/problemset/problem/1516/B

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

My explanation for Problem E. Commented source code, see 130804026.

Let's look at $$$2, 3, 5, 3, 7, 5, 1, 4$$$. I will write the numbers in binary in columns:

What the task now translates to is: Find the longest row of continuous $$$1$$$s with the following property: The length of the sequence is even and each horizontal segment above your sequence contains an even number of $$$1$$$s. Examples are:

Only the first and the last example are valid. The last one is the longest valid example. How do we find this longest sequence? We will need to iterate over each bit (row) and each value (column). Let's assume we iterate over row $$$k$$$

. What we now want is a prefix-xor-sum for all values above our row $$$k$$$ (those are called important in the editorial).

We also color the values in the xor-sum alternating in 2 colors. We will need this to achieve the even length of the sequence. Now we iterate row $$$k$$$ with $$$r$$$ from left to right and for each $$$r$$$ we keep the value $$$l$$$ which denotes the last position with a $$$0$$$ (We handle position 0 as also having value $$$0$$$, so $$$l$$$ starts with 0):

We now want to to find the smallest $$$l_{ans}$$$ such that $$$l \leq l_{ans} \leq r$$$ and that the xor-sum of all values in $$$(l_{ans},r]$$$ is equal to $$$0$$$. This is equivalent to finding $$$l_{ans}$$$ such that the xor-sums of $$$(0, l_{ans}]$$$ and $$$(0, r]$$$ are equal. To achieve the parity in the length of the segment we also need, that $$$r$$$ and $$$l_{ans}$$$ have the same color:

How do we find this $$$l_{ans}$$$? We could create a map that saves for each possible xor-sum value and both colors all the positions this xor-sum appears at and then do a binary search. This would get as a $$$\log(N)$$$ for the binary search and a $$$\log(a_i)$$$ for the map and this will TLE 130742189. We can replace the map with just a vector with $$$2^{20}$$$ values. This will get accepted, but just barely 130742292! Another improvement is, we do not need the binary search. While iterating $$$r$$$ we can keep for each possible xor-sum the earliest appearance in our $$$1$$$ s-segment. This way we get rid of the second $$$\log(N)$$$-factor and this solution gets accepted easily 130804026. The final complexity is $$$O(N \log a_i)$$$, for iterating both $$$k$$$ and $$$r$$$.

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

Why in C we do we need to go to the deepest subtree? Why can't we take any subtree whose xor is x?

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

    XOR value of subtree 3 is 4.
    But if you delete the edge (2,3) first, it is impossible to partition the tree into three components with equal XOR values.

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

Bakry stomped on us in EOI and now he's stomping our ratings here >:(

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

The system testing was fast :) + The Contest was great.

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

C is really nice, the m-2 idea is sneaky

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

I'm trying to solve problem D in the following way:

After getting max value by querying N nodes, query for N/2 nodes.

If the ans is less than max, then remove all the edges which are made up these nodes at both the ends.

If the ans is max, then keep all the edges which are made up these nodes at both the ends, remove other edges.

With the help of remaining edges, again figure out N/4 nodes, and query it. Keep going this way, and in the end, only one edge will remain.

Any issue with this approach?

The solution is failing : https://codeforces.com/contest/1592/submission/130812435 . Is there a logical bug or an implementation bug?

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

    In this way, you cannot guarantee every time you make a query, you really half the size of the set of possible edges that could becomes the answer. I believe that some of the pretests block this approach but I'm not sure .

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

I really can't understand why the approach given in editorial of problem D works?? Can someone explain it to me. Thanks in advance :)

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

In the F1 problem , the editorial makes a new grid using parity of sum of (i,j) , (i+1,j) , (i,j+1) and (i+1,j+1) and solves for this one...is this a common technique?

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

    To get a feeling, you can look at it the other way first. If you want to flip $$$(x,y)$$$ using rectangles containing $$$(1,1)$$$ without flipping other cells, how do you achieve this? You achieve this, by doing operations on $$$(x-1,y-1)$$$, $$$(x-1,y)$$$, $$$(x,y-1)$$$ and $$$(x,y)$$$. If you got several bits you want to flip, then you can add those operations. You notice, doing this operation twice on a cell will keep everything the same. So we can handle the operations as "activate" and "deactivate" the operation on some $$$(a,b)$$$. The editorial now turns this around, by transforming each 4-operations flip into a single cell. This is easily possible, because we found a sequence of operations, that flip exactly one cell.

    I guess you can find similarities to [Lights Out](https://en.wikipedia.org/wiki/Lights_Out_(game)) (I'm really sorry, I somehow can't link this. Guess because there are brackets in the link maybe...?) although the transformation is not so easy, because there is no simple sequence to swap exactly one cell in this case.

    You could also try and learn more about linear algebra to get a better feeling for this.

    So yes, I'd say it is a useful technique to group some operations with special properties and then transform the problem into that group-view.

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

What's that, please? Any link? (some macro/library stuff)

cLay version 20210926-1
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I read the editorial and I understand the solution for problem F1, but, can anyone please explain me the line of thinking to build grid a? I don't get the idea behind this grid structure.

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

How harder would be an adaption of "Alice and Recoloring" where you are given an arbitrarily shaped board, arbitrarily shaped pieces (maybe allow rotations and inversions) and tell if it's possible to reach the final configuration?

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

I have submitted two solutions for problem D 1592D - Hemose in ICPC ?. One of them is giving wrong answer. Can anyone tell why this solution is giving wrong answer?? Here is my submission:131034503.

Basically I am doing binary search on dfs traversal of nodes.

Here is the submission which is giving correct answer.131035225

Basically I just removed this condition

while(high-low>1)

in the binary search condition to

while(low<high)

and started low from 1 instead of 0. here euler is zero indexed and binary search is done on those indexes

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

Someone please help me find the mistake in my code for problem 2c....it is giving TLE on 3rd test case (https://codeforces.com/contest/1592/submission/131055533)

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

His all submissions in this contest are shrinked deliberately. I know it is rule violation. 130676197

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

Can anybody please share the implementation for problem c and possibly explain how exactly are we going to do what has been mentioned as the last step in the editorial?

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

can anyone explain me or give some test cases where my solution for problem D is failing? link to my solution: https://codeforces.com/contest/1592/submission/131272538

Edit: Ok so I got the error by reading some comments above, actually you can't just randomly binary search on the edges because if we select some edges say in the left part and they do not form a connected component then too the interactor calculate the ans for the unconnected vertices which was not forming any edge in our selected set of edges(E.g. in our selected part, edges were(4,10) and (9,11) but the interactor will calculate the ans for (4,9) as well which is not there in the set) which could lead to selecting the wrong part in binary search.

Accepted Solution: https://codeforces.com/contest/1592/submission/131276018

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

IG answer to 1592B is not complete for eg take 1 6 5 2 9 3 11 i.e. n=7 and let x=3 you wont be able to sort it ): but it is actually n>2*x