Hemose's blog

By Hemose, history, 2 years ago, In English

صباحو (Good Morning), Codeforces!

I'm glad to invite you to Codeforces Round 746 (Div. 2), which will be held on Oct/03/2021 17:35 (Moscow time).

This round is rated for the participants with rating lower than 2100.

You will be given 6 problems and 2 hours to solve them. All problems were prepared by me and Bakry.

One of the problems will be interactive. So, it is recommended to read the guide on interactive problems before the round.

I would like to thank:

The statements are short and we have tried to make the pretests strong. I encourage you to read all the problems.

For people who don't like stories, you will find all the stories written in italic you can skip them safely.

This is our first official round on Codeforces. We are sincerely looking forward to your participation. We hope everyone will enjoy it.

Good luck and see you in the standings!

UPD:

Score Distribution: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$2000$$$ — $$$2500$$$ — $$$(1750-1750)$$$

UPD1: Editorial is out!

UPD2: Winners

Div. 1 + Div. 2

  1. LayCurse

  2. SSRS_

  3. qazsxdew

  4. peti1234

  5. dlalswp25

Div. 2

  1. qazsxdew

  2. CrTsIr

  3. tsukigakirei

  4. FangZeLi_AK_IOI

  5. RiCHEPCPR

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I think this round will be great one.

»
2 years ago, # |
  Vote: I like it +65 Vote: I do not like it
lighthearted meme
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I thought nobody likes stories

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

    stories are annoying during contest time but enjoyable during practice

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

      that's an amusing paradox.

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

      Ya during practice it is very enjoyable but during contest specially for rated people most of us have not read it

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Looking forward to this one!

»
2 years ago, # |
  Vote: I like it +126 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Bakry and Hemose OP

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

As a contestant, I hope there are no XOR problems as it's always the case with Egyptian rounds.

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

I claim that this round will be one of the best Div 2 rounds ever.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

you can skip them safely.

Don't tell me what to do, I like stories.

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

    For people who don't like stories, you will find all the stories written in italic you can skip them safely.

    This line was not for you if you like stories.

»
2 years ago, # |
  Vote: I like it +153 Vote: I do not like it

Orz Bakry for winning the EOI

»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

As a tester, it is a great contest with great ideas. I recommend participating. I am sure you will enjoy the 2-hours of the contest. Great Hemose well done!! :)

»
2 years ago, # |
  Vote: I like it +64 Vote: I do not like it

As a tester, I pinky promise you will like the contest.

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

    Pinky promise >>>>

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

    The struggle with D and E was real fun! Looking forward to the editorial. Kudos to the entire team for a great contest. :)

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

i think this contest will be amazing ,Good luck, God willing i hope to be pupil or expert lol

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Waiting for an amazing round and wishing everyone good rating.

»
2 years ago, # |
  Vote: I like it +48 Vote: I do not like it

These Arabic comments are annoying!!! please use only English in an International site.

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

    Imagine thinking you are entitled to regulate how other people talk.

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

      That's not regulating, He's asking to use a common language

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

hopefully this blog wont get any downvotes.

»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I hope the difficulty level will be balanced unlike the last contest XD

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

One of the problems will be interactive. So, it is recommended to read the guide on interactive problems before the round. Hope that it will be one of the last problems that I don't even touch!

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

Can candidate masters participate this contest?

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

Looking forward to this one!

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

hope it's not as hard as the last one xD

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

"The statements are short".. I already like this contest :)

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

    strong pretests are even better

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

Thank you for the opportunity to train on this site. This is the most convenient and practical site for sports programming!

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

This round will be a book for participants, where you can read stories, and also solve problems. Hope it will be interesting! Good luck all!

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

Scoring distributions?

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

Hello everyone!) I have a question. How many problems should be solved on average from the competitions of the second division in order to have a rating of 1400 — 1600. Thanks for the answer)

»
2 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Hope I go purple this round!

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Nice ♥

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

500 — 1000 — 1500 — 2000 — 2500 — (1750−1750) WHAT DOES THIS MEAN last problems will be of lesser difficulty than d and e?? someone pls clear

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

    Last problem has 2 subtasks, if you solve just the easy one, you'll get max 1750 pts, if you solve both, easy and hard subtask, you get max 1750 + 1750 = 3500 pts. Also, avoid caps please :)

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

Egypt Round Today?

»
2 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Long Q?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Way too long..

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

      When you wait for 5 minutes just to see the verdict as Wrong Answer on pretest 2 :_(

»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Can the time limit exceeding be for the long queue time?

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

I am getting a bad feeling about getting FST on B.

update: the solution is right

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

problem B is hard for being div.2 B imo.

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

    gg wp

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

    It has a 1000 points, usually it's only 750 points. I think its justified.

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

      then for many users this contest will only depend on how fast you solve a and a lot of submissions for problem a are like:

      Spoiler
»
2 years ago, # |
  Vote: I like it -61 Vote: I do not like it

Good problems. But was this necessary ??

One day, Ahmed_Hossam went to Hemose and said "Let's solve a gym contest!". Hemose didn't want to do that, as he was playing Valorant, so he came up with a problem and told it to Ahmed to distract him. Sadly, Ahmed can't solve it... Could you help him?

Hemose was shopping with his friends Samez, AhmedZ, AshrafEzz, TheSawan and O_E in Germany. As you know, Hemose and his friends are problem solvers, so they are very clever. Therefore, they will go to all discount markets in Germany.

...

Sorry for pointing this.

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

    Read the announcement carefully, (For people who don't like stories, you will find all the stories written in italic you can skip them safely.)

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

      Ah my bad, sorry for that. Anyway thank you, I really enjoyed the contest.

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

Another contest with only 10% solving C...

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Lovely problems.

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I was manage to solve only one problem that is A, truly speaking I loved that problem. Because I thought that could be solve just traversing the non-increasing array, but that gave me TLE. After that it forces me to think other way to solve it. For me problem A was real meaning of "codefocres", loved it.

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

How to solve B?

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

    +1 from future specialist

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

    There might be a part of the array in the middle where we cannot move any element. If that part is not correctly sortet in input then ans=NO.

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

    The main idea to solve this problem is that you will not able to swap the elements present in the array in the range from (n — x) to x, so, the elements that are present in this range must be sorted and must have values equal to the sorted array..

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

Can problem D be solved using Centroid Decomposition + knapsack?

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

    I think binary search on the edges was required. Since the gcd of two numbers is always smaller than or equal to the smaller of the two number ( $$$gcd(a,b) <= min(a,b) $$$) . This means that the maximum distance will be between two nodes that are intially having a edges.

    Now we can find the maximum distance between any two edges in 1 query. After that we can binary search on the edges and find the edge with the distance equal to maximum distance.

    I was not able to get AC and might be entirely wrong.

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

      Sorry, but what binary search on the edges means?

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

        Sorry about it entirely wrong T_T.

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

    Yes, basically the idea is the following:
    1. Set the goal = query of all nodes, we will eventually end up with this score between exactly two nodes.
    2. Perform the following operations on the tree, till the tree has exactly two nodes (the answer):
    2.1. Find the centroid of the tree and let's root the tree at the centroid.
    2.2. For each child of the centroid add all the nodes of the subtree rooted at the child into a set.
    3.3. From 2.2, we have k sets of nodes where k is the number of children of the centroid.
    3.4. Merge all these k sets into exactly 2 sets, here we need to make these two sets have size as close as possible to each other. This can be done accurately enough by using knapsack as you described, but I used a greedy version for my implementation and it got accepted. Although, I am not entirely sure it is correct, so please someone prove its correctness or hack it :p.
    3.5. After merging we ask a query on the first of these two sets. If the query == goal then we know that we have a valid answer in the set we asked, so we remove all the nodes & edges of the tree from the other set. Otherwise, if query != goal we know that our answer is contained in the second set, so we remove the nodes & edges of the first one.
    3.6. If we end up with just two nodes, this is our answer, otherwise, we repeat the 2nd step.

    Note that the 2nd step will be executed at most log(n) times because in each iteration we remove almost half of the tree's nodes. It can be proven that the size difference between these two sets will be small enough to keep it in log time, (if we merge all the k sets optimally) because of the properties of the centroid.

    Here is my post-contest submission (130742844) of this implementation.
    (Again, I did not use DP knapsack to merge the K sets into 2 as optimally as possible, so it might be hackable)

»
2 years ago, # |
  Vote: I like it +102 Vote: I do not like it

Nice sense of humour in that iconic at most k-1 edges line.

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

    They probably had something like split into at most k trees and then changed it last-minute for that XD

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

    I actually got C wrong answer at 10 because I handled the case when K = 1 instead of 2 because of that line. after the contest I edited it and got the late ACC :(

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

    I thought that was to be able to easily write the constraints on n and k. It was something like 1 <= k <= n <=

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

C, how to find the XORsums for all edges without TLE?

Then it should be not so hard. It cannot be more than 3 components, since if it would, we could put together 3 of them into 1.

So we want to search for XORsums in our list where both ends are same, or one end equals 0 and there exist two other ends with the same XORsum.

Edit: And yes, problems where way to hard. A trivial, B stupid. Actually only C somewhat interesting.

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

    This is what I did. Let XOR of all elements be Xo.

    1) If Xo == 0, then there is always an answer ( As all elems >= 1 => it is possible when two partitions have equal XORs ) 2) If Xo != 0, then we need to divide the tree into 3 components. So, I ran a DFS across the graph which basically returns XOR of the subtree. a) If Xor of a subtree == Xo => this is a candidate for division. Return 0 ( So that we don't double count it, especially for cases where some contiguous group of ancestors have a xor 0. This leads to double counting of this subtree b) If Xor of a subtree != Xo, just return Xo

    Finally, if we have > 1 nodes with Xo XOR and k > 2 => we can always have an answer.

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

      How does this dfs returning the xor of that subtree run without TLE?

      Consider the trivial implementation: We iterate all children except the parent, and return the XORsum. But that goes TLE for a star like tree (one center and a lot of leafs arround it).

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

        I still don't understand why the DFS will be any different from say DFS to return count of nodes.

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

          While counting the nodes we can simply return the number of adj nodes, without iterating them.

          Finding the xorsum we need to iterate them.

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

            XOR of SUBTREE ( ROOT ) = Value ( ROOT ) ^ XOR of SUBTREE ( Children )

            This is the recursion. We will visit every node once and if our dfs call at a subtree returns the corresponding XOR => we can easily derive the parent's XOR

            Thus O ( V + E )

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

            Went over your code ( TLE one ). Your DFS function itself seems correct but, the fact you are iterating for a lot of nodes is not. If you think a bit, if there exists an answer, it can be discovered with a single DFS call

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

              Yes, I think I understood now.

              It is enough to dfs starting at one edge, since foreach iterating edge we have the two values, and can simply store them also in the oposite direction.

              I tried instead to dfs from kind of "all directions" :/

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

    Rerooting approach (couldn't implement it in time because I was stuck at problem B):

    Code

    Note: every edge is double-counted.

    In the first DFS we calculate xor of all vertices in the subtree of u. In the second DFS we do it for every possible root. In the u's component XOR is dp[u] ^ dp[v] and in v's component XOR is dp[v].

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

what the heck is in test case 17 (and how to solve D)?

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

    +1

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

    I guess you are doing a simple binary search on the edges. Imagine this, you want to ask about Edges $$$(1,2)$$$ and $$$(3,4)$$$. You will get $$$7$$$ as answer!

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

    Test 17 is really depressing. In your case, it was for problem D and in mine, it was problem C. ;-;

»
2 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Thanks for interesting F

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

Hurrahhhhh,,! after a long time againg specialist :)

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

lmao someone got -1294 points for -50 hacks

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

I've no idea why authors of C decided that it's possible to delete at most k-1 edges, while input is k :/

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

    If we delete $$$k-1$$$ edges, there will be $$$k$$$ pieces of the original tree. So if $$$k=2$$$ for example, there will be $$$2$$$ trees left after removing $$$k-1=1$$$ edge.

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

      But in the solution we don't care about number of pieces, we care only about number of edges. Because of this k — 1 it's easy to get wa10.

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

        It's easier to reason about number of pieces. Would you prefer "Two edges cut" or "three trees"?

        If you prefer "Two edges", then just do k--, there's no one stopping you from that.

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

    Meaning that we cut the tree into k components, so the # of cut edges is k — 1.

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

    K components is more natural

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

    I think it is so that there are maximum k disconnected components as the result of the edges deletion, pretty reasonable.

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

Approach for C? I noticed that if the total xor is $$$0$$$, then there is always a solution. If it's $$$x$$$, and there is a solution, the solution requires at least $$$2$$$ total edge-cuts, and each of those $$$3$$$ pieces of the tree should have xor $$$x$$$.

But how do you implement a solution to find whether it there are $$$3$$$ subtrees with xor $$$x$$$?

Edit: Thank you chlalstjr and Ghassane :)

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

    One dfs should be enough. For each subtree, calculate XOR for it. If a subtree has XOR equal to $$$x$$$ (XOR of all the elements), we set it equal to $$$0$$$ and increase the counter. If the counter reaches $$$2$$$, then we can split the tree in $$$3$$$ components with equal xor.

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

      (deleted) I think I've figured out. Thanks.

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

      i dont think this approch is correct.but this is Accepted.

      this is case: ai=value at node[xor value]

      i= node number, k=(100)
      
                XOR=xor of the sum tree root at this node
      
      
      
                              (a1=0,XOR=5)
                            /             \
                     (a3=0,XOR=5)         (a2=0,XOR=0)
                     /          \
             (a4=5,XOR=5)      (a5=0,XOR=0)
             /
       (a6=0,XOR=0)

      here net XOR=5 and your count is = 3 times. but it is not possible to split in 3 parts Ghassane Can you explain this??

      UPD: GOT it. i missed the part set it equal to zero.

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

    Your observations are correct. Using x as the value of all XOR, I did a dfs from any point. At root, if A[root] == x, return 0 and increment numComponents, else return A[root]

    At non-roots, you take A[node] XOR with dfs of all children (so excluding parent). Again if value == x, return 0 and increment numComponents, else return XOR value.

    Basically what this does is everytime you get a subtree where its XOR equals x, you immediately break it away as a single component.

    Then check if numComponents <= k or (numComponents — k) % 2 == 0 --> This means if you can achieve k components by combining 3 components into 1.

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

How to solve C?

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

    If the xor of all $$$a_{i}$$$ is $$$0$$$, you need to make an even number of components i.e just one cut is enough.

    If the xor of all $$$a_{i}$$$ is greater than $$$0$$$, let's call it $$$x$$$, you need $$$3$$$ components(two cuts) with subtree xor's equal to $$$x$$$. You can easily calculate that with a dfs and cutting edges off subtrees when you meet one with a xor of $$$x$$$.

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

    let x = xor of all nodes z = equal xor value for each component if x is zero deleting any 1 edge will do the job other wise the number of components must be odd which implies even number of edge cuts and the xor value of each connected components must be x i.e z must be = x. Thus the number of components must be 3 , 5 , 7 ... (bound depending on value of k) but We don't need more than 3 components , suppose we 5 components , we can merge 3 of them into 1 maintaining the xor value since z xor z xor z is = z

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

Anyone How to solve B i am sure for x=1 ans will yes and for x=n no :(

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

I spent half hour just to change i+2 to i in my B solution it took me a dreaming journey in the universe to see it

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

    When I suspect that something like this is happening, I delete everything, read the problem statement and start writing the code again.

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

      it wasn't a typo i actually thought it's i+2

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

        I solved B the same way you did, but I think this is a better way :

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

          I knew it's a continuous range but my mind just didn't work to calculate it i guess not my best day

»
2 years ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

Is this called contest? :| I think you should change your minds

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

Not sure of the binary search approach for D but here is mine. The first query is the whole graph to search for the final value. The second query is to turn the size of edges set to the power of 2. The 10 next queries is to divide the set into 2 halves. Then just check for one half and move to the valid set.

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I thought only Ehab is in love with XOR..

It seems common for all Egyptians

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

Seriously, what was pretest 10 in problem C!?

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

    You probably forgot that you have to use almost $$$k-1$$$ cuts.

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

      Can't we always find the answer with exactly two cuts when the xor is non-zero?

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

        If $$$k = 2$$$ then you have only $$$1$$$ cut so the answer is NO.

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

          I decremented $$$k$$$ already, I don't think that's the issue.

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

    I could not pass the pretest 10 as well ;(

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

I think many ppl got stuck on the impl, C was actually pretty easy and interesting tbh.

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

For C, I would like to know if the following observation is correct or not.

If it is possible to generate components with the same XOR sum, it is possible to do so using either one cut or two cuts.

I played around with a few examples and reached this conclusion. But implementing this gave me WA.

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

    If Xor = 0, One cut is enough

    If Xor != 0, If there is a solution it always can be done with 2 cuts

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

      Yea that makes sense, thanks.

      Now I just need to check where I went wrong in the implementation :/

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

    Proof: Let X represent XOR of all nodes

    If X = 0, it can be done in 1 cut, because, say y represents xor of one component and z represent the other component. Then:

    y ^ z = 0

    therefore, z = 0 ^ y = y, so the two componnents will have equal xor value

    If X!=0, it can be done in 2 cuts. Let x, y, z represent xor of each component after two cuts

    x^y^z = X

    since all components are supposed to be equal, x = y = z, therefore:

    x^x^x = X

    x^x^x = (x^x)^x = 0^x = x

    x = X

    So we should make 3 components with xor value = X

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

I tried to solve it. :)) but at the last minute, I realized that I misread problem A. I think I can solve problem B if I have more time :3

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Fun contest ! My delight in solving the problems outweighed the frustration from repeated stupid bugs. Good job round setting team

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

Check out code of problem A,B,C of RestricePlanox. Looks like this guy gets the solution from somewhere and then add helper++ all over the code so that system can't detect it.

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Great round but problem C and D aged me $$$10+$$$ years

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

Nice Contest , Thanks For The Round . Although my bad form Continues (Solved A and C but failed in B) , I enjoyed the round .

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

Only able to solve A but all problems are interesting and educational. Great round Hemose and other problem setters too

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Now that all my problems passed system tests, I'd like to express my admiration and say Good job guys <3

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

    Thanks!

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

      Hey, can you help me out? Problem C of today. https://pastebin.com/jFS45YQM Why this code gives MLE? I don't see any point of MLE!! Does clearing vector before taking input is the culprit behind the scene?

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

        deleted

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

          I got it and posted about it. I am now flying on the doom of darkness and sorrow grasping me harder man!!! Haven't got MLE before this for that approach.

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

The system testing is in "Flash" mode

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

So is F2 flows?

I find it in the last 5 minutes.But I've deleted all my code written before to clean my computer.

Anyway it's a nice contest with hard but interestinf problem.

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

Really enjoyed the round, especially the C problem !!!

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Amazing ABCD, but E was quite easy for its position. Amazing contest.

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

My code for problem C was wrong and i have the wrong case for it

The test

and it passed the systests !!!!!

so weak systests its just a simple case !!!!

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

    Well, I guess your test case is wrong, as it does not meet the constraints specified for the weight of the node, which was greater than 1 and thus cannot be 0.

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

Hard, but very exciting set!!!

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

Can someone tell me whats wrong in this Approach for Problem E?

I am looping for each bit i and trying to find the largest subarray all it's elements have 1s at bit 1

If the AND of this subarray > XOR, then the answer will be the size of this subarray, otherwise the answer will be Size of the subarray — 1, maximizing the answer with each i

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

    when you are looping over some bit i, and let's say you have a subarray with bit i, it is not always sufficient to check, this total subarray, or subarray-1 .

    Though just a little extension of your approach could have done it. Let's find a new array A from your subarray, such that for each element in subarray, you make an entry in this new array, with bits>=i.

    Now in this new Array, find the max length subarray with xor = 0. That's your answer.

    130719800

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

Were the tests of problem C weak? I used random to generate the root of the tree and solved it without checking 1 thing. Currently, I don't know what I'm forgetting. but it somehow got AC. If you know can you leave it here? my submission is 130722566 thank you.

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

Thank you Bakry and Hemose for this contest. Although I didn't end up solving C in contest time (which means I'll get -ve unfortunately), I thought that B, C, and D were very nice problems! I found the right observations for them, although couldn't implement C in time. I'll definitely be upsolving them :D

One question about C, was the constraint on $$$k$$$ added to troll about the previous contest that also had to do with $$$k-1$$$ edges? Because all it added was a simple if-statement, but it made many people fail pretests as it wasn't in any sample.

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

    I guess the reason why authors gave the constraint k-1 is because when you delete k-1 edges then the tree ends up with k components, which looks easier to deal with. Again, just guessing

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

      I'm not asking why it was $$$k-1$$$ edges cut versus $$$k$$$ components. I'm asking why there was a constraint with $$$k$$$ in the first place.

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

    We are happy that you enjoyed the contest!

    The constraints are the same from the beginning we didn't modify anything.

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

Is there anyone, who also thought problem C is doable and then couldn't able to solve it :(

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Round was excellent!

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

When will the problems can be submitted?

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

    once the system testing is complete, then you will be able to submit it. It's almost completed just a matter of 2,3 minutes.

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

Can anyone explain the approach for problem B??

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

    if k is bigger than half of the size of the array, then there are some elements in the middle of the array that we cannot swap with any other element.

    We need to check if these not-swappable elements are in correct position.

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

      hey, i do understand that but can someone prove that all swappable elements can be sorted??

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

        The prove is that each two elements can be swapped by using a third element, and swap three times. So each element that can be swapped with any other element, can be swapped in any position that is reacheable by any swap. Like we can swap with the usual adjacent elements.

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

130711588 This submission is taking a lot of time. why why!!!!

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

difficulty gap between B and C was too high

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

    I don't think so, it only required basic xor knowledge and dfs traversal.

    You should definitely check out the editorial, it is pretty well explained there.

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

      yeah I read the tut and it was was actually quite nice and intuitive logic :) One of my friends sent me this question which is equivalent to the case where the tree degenerates into a linked list.

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

very interesting problemset, I missed C by few seconds :/ https://codeforces.com/contest/1592/submission/130724367

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

pretest 10 on C haunts me , anyways nice contest

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

    same here, I found the testcase but I completed my solution 3 seconds after the contest :/ really just 3 seconds :/

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

I came up with a very-overkill solution to E quickly but spent a good amount of time implementing/debugging it only to get mle on test 1.wish the ml was more.Its surprising that intended solution was so easy and short.

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

    Yeah, I like E because The solution becomes easy and short after one observation.

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

hard one but good one

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

What is happening to this 130711588 submission by rainboy to problem D? It is getting "Denial of judgement". I have never seen one before...

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

    Update: It became "Accepted". I wonder what happened...

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

      We just rejudged the solution, We don't know the reason for this verdict.

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

      we've rejudged his solution and he got AC

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I have known Bakry personally for around 2 years and there is one thing I want to say,

Good job Bakry senpai, You always amaze me with your progress, keep up the great work.

Also, no one can forget the great work of the great Hemose in this contest.

Thank you guys.

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

    Thanks! We are happy that you enjoyed the contest!

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

Thanks for interesting problems, I felt like real div2 C diff problem was missing.

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it
Telling everyone you're hitting expert
After rating change
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

F1,F2 are interesting.

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

صباحو

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

Finally became a Div. 1 Newbie.

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

got -106 but still wht a great round and quality problems