Hemose's blog

By Hemose, history, 3 weeks 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. XianHZ

  3. tsukigakirei

  4. FangZeLi_AK_IOI

  5. RiCHEPCPR

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

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

I think this round will be great one.

»
3 weeks ago, # |
  Vote: I like it +65 Vote: I do not like it
lighthearted meme
»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Looking forward to this one!

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

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

Bakry_ and Hemose OP

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

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

Orz Bakry_ for winning the EOI

»
3 weeks 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!! :)

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

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

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

    Pinky promise >>>>

  • »
    »
    3 weeks 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. :)

»
3 weeks 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

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

I thank Naseem17 for this wonderful thing

I_will_be_like_naseem17_someday

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

Waiting for an amazing round and wishing everyone good rating.

»
3 weeks 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.

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

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

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

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

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

        He stated himself it's an International site...

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

    They look like noodles.

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

hopefully this blog wont get any downvotes.

»
3 weeks 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

»
3 weeks 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!

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

Can candidate masters participate this contest?

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

Looking forward to this one!

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

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

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

hope it will be lot better than previous contest(745div2). wishing to get back to specialist.

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

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

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

    strong pretests are even better

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

      But then there's less chance of hacking someone's code.

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

        As I know you shouldn't post here anymore :)

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

»
3 weeks 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!

»
3 weeks 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!

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

I think this contest will be interesting and increase the Rating and confidenceof coders. _ _ _...will see after contest.

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

Scoring distributions?

»
3 weeks 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)

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

Hope I go purple this round!

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

Nice ♥

»
3 weeks 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

  • »
    »
    3 weeks 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 :)

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

Thanks for all the love.

Looknig forward for the contest

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

Egypt Round Today?

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

queue doesn't look good today :/

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

Long Q?

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

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

»
3 weeks 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

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

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

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

    gg wp

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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
»
3 weeks 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.

  • »
    »
    3 weeks 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.)

    • »
      »
      »
      3 weeks 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.

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

Another contest with only 10% solving C...

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

Lovely problems.

»
3 weeks 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.

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

How to solve B?

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

    +1 from future specialist

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

      You can only swap between the first $$$n - x$$$ values and the last $$$n - x$$$ values.

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

    If the current element is in its correct place, do nothing
    Else, check if there is room to swap it to its left or its right. If no, print NO
    If it didn't print NO for any of the elements, print YES

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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..

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

Can problem D be solved using Centroid Decomposition + knapsack?

  • »
    »
    3 weeks 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.

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

      Sorry, but what binary search on the edges means?

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

        Sorry about it entirely wrong T_T.

  • »
    »
    3 weeks 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)

»
3 weeks 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.

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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 :(

  • »
    »
    3 weeks 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 <=

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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).

      • »
        »
        »
        »
        3 weeks 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
        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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 )

          • »
            »
            »
            »
            »
            »
            3 weeks 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

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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" :/

  • »
    »
    3 weeks 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].

»
3 weeks 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)?

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

    +1

  • »
    »
    3 weeks 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!

  • »
    »
    3 weeks 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. ;-;

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

Thanks for interesting F

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

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

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

lmao someone got -1294 points for -50 hacks

»
3 weeks 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 :/

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

  • »
    »
    3 weeks 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.

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

    K components is more natural

  • »
    »
    3 weeks 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.

»
3 weeks 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 kusnim and Ghassane :)

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

    Euler tour ?

  • »
    »
    3 weeks 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.

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

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

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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.

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

How to solve C?

  • »
    »
    3 weeks 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$$$.

  • »
    »
    3 weeks 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

»
3 weeks 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 :(

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

    1

    3 3

    1 2 3

    x == n, answer -> yes.

»
3 weeks 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

  • »
    »
    3 weeks 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.

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

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

      • »
        »
        »
        »
        3 weeks 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
        • »
          »
          »
          »
          »
          3 weeks 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

»
3 weeks 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

»
3 weeks 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.

»
3 weeks 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

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

Seriously, what was pretest 10 in problem C!?

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

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

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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.

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

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

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

    I could not pass the pretest 10 as well ;(

»
3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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 :/

  • »
    »
    3 weeks 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

»
3 weeks 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

»
3 weeks 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

»
3 weeks 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.

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

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

»
3 weeks 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 .

»
3 weeks 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

»
3 weeks 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

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

    Thanks!

    • »
      »
      »
      3 weeks 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?

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

        deleted

        • »
          »
          »
          »
          »
          3 weeks 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.

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

The system testing is in "Flash" mode

»
3 weeks 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.

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

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

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

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

»
3 weeks 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 !!!!

  • »
    »
    3 weeks 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.

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

Hard, but very exciting set!!!

»
3 weeks 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

  • »
    »
    3 weeks 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
»
3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks 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 :(

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

Round was excellent!

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

When will the problems can be submitted?

  • »
    »
    3 weeks 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.

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

Can anyone explain the approach for problem B??

»
3 weeks 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!!!!

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

difficulty gap between B and C was too high

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

I had the idea for B, but I don't get why my indices are wrong. I drew it out on paper and I thought mine were right. Can somebody help thanks. LowerIndex and higherIndex are the last ones that can be switched with other indices.

int lowerIndex = numNums-x-1;

int higherIndex = x;

boolean foundNO = false;

for (int k = lowerIndex+1; k < higherIndex; k++) {

if (numbers[k] != sorted[k]) {

     System.out.println("NO");

     foundNO = true;

     break;

     }

}

if (!foundNO) System.out.println("YES");

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

could someone tell me why this approach doesn't fit the time limit in problem B submission ?

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

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

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

pretest 10 on C haunts me , anyways nice contest

  • »
    »
    3 weeks 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 :/

»
3 weeks 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.

  • »
    »
    3 weeks 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.

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

hard one but good one

»
3 weeks 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...

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

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

    • »
      »
      »
      3 weeks 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.

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

      we've rejudged his solution and he got AC

»
3 weeks 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.

»
3 weeks 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.

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

first time under 1200 (: hoping great rating :)

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

صباحو

»
3 weeks 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!

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

F1,F2 are interesting.

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

صباحو

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

The quality of problems is really great, gems! Thanks for the contest.

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

Finally became a Div. 1 Newbie.

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

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

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

How come for this problem https://codeforces.cc/problemset/problem/1592/B this solution gets accepted https://ideone.com/N6PmZb but this solution https://ideone.com/NiqtE2 does not?

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

    You should change this :

    if (a[i].first != i) {
        f = 0;
        break;
    }
    

    with this :

    if (a[i].second != b[i]) {
        f = 0;
        break;
    }
    

    Here is your code get accepted after change 130840375.

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

    Your approach is wrong, in the test_case below your code is giving "NO" but as you can see it should be "YES".

    1
    5 3
    2 1 2 1 2
    

    why is that ? before sorting :

    vector : 2 1 2 1 2
    index  : 0 1 2 3 4
    

    after sorting :

    vector : 1 1 2 2 2
    index  : 1 3 0 1 2
    

    the 2s in the middle of the vector before and after sorting are different, and because of that it gives "NO".

    without using "index" and use another vector for example :

    vector<int> a = {2, 1, 2, 1, 2};
    vector<int> v = a;
    sort(v.begin(), v.end());
    

    now v is like : 1 1 2 2 2 and when you compare a[2] with v[2] there should be no problem.

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

<3333

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

Thanks for this round,I finally become a pupil haha.