Блог пользователя Hemose

Автор Hemose, история, 3 года назад, По-английски

صباحو (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

  • Проголосовать: нравится
  • +806
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

I think this round will be great one.

»
3 года назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится
lighthearted meme
»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Looking forward to this one!

»
3 года назад, # |
  Проголосовать: нравится +126 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Bakry and Hemose OP

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

you can skip them safely.

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +153 Проголосовать: не нравится

Orz Bakry for winning the EOI

»
3 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Waiting for an amazing round and wishing everyone good rating.

»
3 года назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

hopefully this blog wont get any downvotes.

»
3 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Can candidate masters participate this contest?

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Looking forward to this one!

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Scoring distributions?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Hope I go purple this round!

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Nice ♥

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Egypt Round Today?

»
3 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Long Q?

»
3 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

update: the solution is right

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -61 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +74 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Another contest with only 10% solving C...

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Lovely problems.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve B?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    +1 from future specialist

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Can problem D be solved using Centroid Decomposition + knapsack?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +102 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

        Code
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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 года назад, # ^ |
              Проголосовать: нравится +4 Проголосовать: не нравится

            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 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Thanks for interesting F

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

lmao someone got -1294 points for -50 hacks

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    K components is more natural

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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 :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Hint 1
    Hint 2
    Hint 3
    Hint 4
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        Spoiler
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -20 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I thought only Ehab is in love with XOR..

It seems common for all Egyptians

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Seriously, what was pretest 10 in problem C!?

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    If Xor = 0, One cut is enough

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yea that makes sense, thanks.

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

The system testing is in "Flash" mode

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hard, but very exciting set!!!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    We are happy that you enjoyed the contest!

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

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Round was excellent!

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

When will the problems can be submitted?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the approach for problem B??

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

difficulty gap between B and C was too high

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

pretest 10 on C haunts me , anyways nice contest

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hard one but good one

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Telling everyone you're hitting expert
After rating change
»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

F1,F2 are interesting.

»
3 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

صباحو

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Finally became a Div. 1 Newbie.

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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