When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

AkiLotus's blog

By AkiLotus, history, 5 years ago, In English

Once again, TREMBLE BEFORE THE MIGHTY OMEGALULRIPGRAPE.

(He last walked the Earth in round 538 btw.)

Hello Codeforces!

We are here to invite you to Codeforces Round #554 (Div. 2), which will take place at 24.04.2019 17:35 (Московское время).

The round will be rated for all Division 2 participants (with rating less than 2100), yet any Division 1 participants are welcome to join us out of competition.

The round will be cat themed. Raise your paws and prepare your catnips!

(Or even cat memes, while you're at it).

You will be given 6+1 problems ( 6 problems, one of them has 2 subtasks ) to solve in 2 hours. The round's problems were prepared by Xuan-Quang xuanquang1999 D. Nguyen, Duy-Bach AkiLotus Le, Stefan stefdasca Dascalescu, Quang-Minh MofK D. Nguyen and our dear Codeforces coordinator Dmitry cdkrot Sayutin.

Gladly (or sadly), no interactive problem tonight!

Also, the tribute should be given to everyone within the team — we all make it possible:

  • Andrew GreenGrape Rayskiy for various problem suggestions and the infamous OMEGALULRIP influence. ;)
  • Xuan-Tung neko_nyaaaaaaaaaaaaaaaaa Nguyen for testing the rounds and various suggestions in the core theme idea. Nya~.

Last but not least, I want to give a huge appreciation to MikeMirzayanov for the awesome Codeforces and Polygon platform, which makes this contest possible.

P/s: I will be at the Discord CP Community to discuss the problems after the coding phase. However, please follow the rules and don't discuss the problems during the contest by any means.

Wish everyone good luck and high rating!

P/s(2): Commies united!

P/s(3): A dear thank-you to Grigory vintage_Vlad_Makeev Reznikov for the last-minute complete testing as well! ;)

UPD1a: Another comrade, Quang-Minh MofK D. Nguyen joined the fun! Kudos for the problem suggestion! ;)

UPD1b: The problemset contains 6+1 problems ( 6 problems, one of them has 2 subtasks ).

UPD2: Score distribution: 500-1000-1500-2000-2000-(2250+750).

UPD3: Editorial will be available tomorrow. Sorry for the waiting, we have quite a lot of things to polish. ;)

UPD4: The contest is finished. I hope that you're satisfied. And here come our winners ;)

Official participants:

  1. hamzzq
  2. davidHernandes
  3. oiyoayao
  4. abandonedw1
  5. OnionGod
  6. IPL
  7. memset_inf
  8. dsgsjk
  9. FluffyT (the only official participants solved F1+F2, too bad she didn't solve E :<)
  10. _wxw_

Div.1 + Div.2 participants:

  1. dreamoon_love_AA (solved all problems!)
  2. pwild
  3. Sugar_fan
  4. hamzzq
  5. natsugiri
  6. kmjp
  7. davidHernandes
  8. Jeffrey
  9. betrue12
  10. KrK

UPD5: Editorial blog post is available.

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

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

$$$iS iT rAtEd?$$$

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

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

A lot of rounds recently! That is awesome!

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

What's "the infamous OMEGALULRIP influence" ??

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

Not all grape is GreenGrape XD

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

Meow :3

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

Wait a second I didn't say anything about quarantining GreenGrape from pretests right? lenny eyes

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

upvote: funny and cool announcement downvote: messy announcement with many unnecessary details

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

I can see several rounds opened by you while I am waiting for my single proposal. Jealous! Hope I will open my round also.

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

    Once the first one is accepted, proceeding with later proposals should be a cakewalk (provided the problems in the next proposals are well-prepared) and require less waiting time. ;)

    Anyway, would be glad to join yours soon. ;)

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it -78 Vote: I do not like it

There are some guys who use to devote all the comments without any reason, please don't do this. Happy Coding

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

    Do not mind downvotes on your comment

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

Again you posted a week before the contest =) AkiLotus

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

    Next time I might post it a month before the contest I suppose. ;) :thinking:

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

downvote if you get OMELGALULRIP reference upvote if you don't know what it is

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

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

I hope GreenGrape gave you only problems ideas not test cases ideas :V

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

How many points each question will be worth?

»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

I'm a gay!

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

Hack time is during the contest?

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

How do sub-tasks work at codeforces?

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

What's with all these female anime character profile pictures?

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

gg Everyone!

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

How does the subtask thing work? Does that mean that the problem will have partial scoring? I guess this will be the first time that a rated CF contest has partial scoring for problems?

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

    It happened in some previous contests though, the latest iirc was about 2-3 months ago.

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

Someone will solve all the problems at 6:13. Says, the contest poster. -Illuminati

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

Yay! Another chance to change the rank! Maybe to expert xD

Well, seems like I'm working on it.

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

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

Site is working so slooow

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

,

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

    F1 and F2 differs in constraints of $$$n$$$.

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

Isn't the LCM problem harder for a Div2 C problem?

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

    It was a math problem, not that hard, or not that easy. The number of submissions(1285) reflects the same, that it was not that hard. :)

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

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

Great round!

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

What a shame...how to solve C? i have no idea about it at all..

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

      I spent almost all contest time on that problem and now see my error thanks to that link. I was keep using prime factors instead of divisors :P

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

        I always get stuck at Maths problems . :(

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

    Find the difference (b-a), and for every factor of (b-a), try to find the number(greater than a) which is the nearest to a and a multiple of the factor. Now that number — a will give you x, and you can solve it further. Constraints did help me think this way.

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

    According to Euclidean algorithm, when a != b, "GCD(a + k, b + k) == GCD(b — a, a % (b — a) + k)" (when a < b). Then all we need to do is find all divisors of "b — a" (Traverse from 1 to sqrt(b — a) is enough), for each divisor d, let "d == a % (b — a) + k", so we can calculate k and corresponding LCM, then find the minimum. Exceptionally, consider the "a == b" case.

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

.

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

what was the logic in problem c??? anyone who got it accepted.

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

    $$$lcm(a, b) -> min <=> gcd(a, b) -> max$$$

    $$$gcd(a, b) = gcd(a - b, b)$$$ if $$$a > b$$$.
    So $$$gcd(a + k, b + k) = gcd(a - b, b + k)$$$. That means that you can iterate over divisors of $$$a-b$$$. For each divisor $$$d$$$ you can find such $$$k$$$ as $$$g * ceil(b / g) - b$$$. And just print $$$k$$$ that gives minimum value of $$$lcm(a + k, b + k)$$$.

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

      (I probably misunderstood the question, but) if we are to maximize gcd(a — b, b + k), then why do we need to iterate over divisors of a — b? Isn't it we just find k such that the gcd attains the max possible value, i.e. a — b?

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

        There might exist a factor less than the maximum possible value for which the LCM is smaller.

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

        Countertest: $$$a = 3, b = 1$$$.
        $$$a - b = 2$$$. So $$$k$$$ must be 1 ($$$gcd(3 + 1, 1 + 1) = 2$$$). But real answer is zero.

        if $$$k = 0$$$ $$$lcm(3 + 0, 1 + 0) = 3$$$.
        if $$$k = 1$$$ $$$lcm(3 + 1, 1 + 1) = 4$$$.

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

          I think I understand what's wrong with my logic...

          The thing in my mind is LCM(a + k, b + k) = (a + k) x (b + k) / GCD(a + k, b + k). While my focus is on maximizing the denominator with respect to k, I overlooked the fact that k also impacts the numerator...

          What a stupid mistake and flawed logic (sigh... spending like an hour debugging my logic...)

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

      In the line : For each divisor d you can find such k as g∗ceil(b/g)−b ; what was 'g' here...?

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

What was the 5th test of D???

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

    5 answer 84

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

    $$$ans(4) = 27$$$
    $$$ans(5) = 84$$$
    $$$ans(6) = 270$$$

    Maybe 5th test is neither of them but you can at least check.

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

Why was x from problem B 1e6? I have a greedy solution that works in O(steps) (in our case steps is 40). Is the official solution dp?

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

LOL, I overrated D, it shouldn't take so much of my energy like that, so not able to even read statement of E and F. Great round anyway.

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

I would like to ask if we could reduce problem E to a euler path problem like this one: SGU101.

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

    I got AC on pretests with euler path. I think it's quite easy to prove that any solution gives euler path in a graph, and any euler path is a solution.

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

      can you please explain your approach?

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

        Let values $$$b_i$$$ and $$$c_i$$$ be vertices of the graph, and edges would be $$$(b_i, c_i)$$$. Then you just need to find euler path in this graph and it would give answer, or there is no answer if such path does not exist. And before all you need to check that $$$b_i \leq c_i$$$ for all i.

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

          Sorry but I didn't understand why this works? Can you give me the intuition behind it?

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

            Whole problem is to reorder pairs $$$(b_i, c_i)$$$ in such way that it would give you some array a. Pairs need to form a path because pairs $$$(min(a_i, a_{i+1}), max(a_i, a_{i+1}))$$$ and $$$(min(a_{i+1}, a_{i+2}), max(a_{i+1}, a_{i+2}))$$$ obviously share one element, which is $$$a_{i+1}$$$.

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

            Oh, I forgot to tell that graph is undirected, it's really important here.

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

              If i understood correctly then a particular vertex b[i] may appear twice in the resultant array. So, if we just add the edges between bi and ci then how can we differentiate between them? (like in sample case 3)

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

                Just add multi-edges, algorithm for euler path works well with them

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

                  it worked! thanks!

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

    I think yes, but the graph can have $$$O(n^2)$$$ edges

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

      Could you elaborate on how you model the graph?

      My approach is to use numbers appeared in b' and c' as vertices and add edges only between each pair of b and c. So if it is correct, the number of edges would be O(n) I guess?

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

        I think he means that for each i, you will have two possibilities for two consecutive elements at some position in a, either b'[i],c'[i] or c'[i],b'[i] (given that c'[i] >= b'[i]). Let these 2 pairs be pi1 and pi2, you will add an edge from pix to pjx (i != j) if pix.second == pjx.first. This may result in n^2 edges.

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

The solution to Problem C could be found on multiple Q/A forums. Aren't the setters supposed to make sure this doesn't happen?

The exact problem has been discussed here and here.

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

Thank you for the great round! I guess E is Eulerian path problem, but not enough time for coding:(

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

sorry for not being clear about codeforces rules, but is it reasonable to skip all the previous submits that had passed pretests and only accept the last submit?

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

Am I the only one who experienced problems with the website today?

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

    Me too. Can't send D within last five minutes. But this is almost regular.)

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

    I have recently started having trouble with loading website, not only during this contest

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

    Me too :(

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

    of course not ... specifically after every submission, the page needed to be refreshed for the verdict which then too was not loading

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

it looks like I should've used my googling skills to solve C instead of thinking

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

how to solve D?

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

    Let's consider a rectangular grid with $$$n \times n$$$ cells. Denote the lower left vertex as $$$(0,0)$$$ and the opposite as $$$(n,n)$$$. For every correct bracket sequence, there is a path walking from $$$(0,0)$$$ to $$$(n,n)$$$, without crossing the diagonal( you can touch but cannot go to another side), which is related to Catalan number.

    Denote the number on the vertex to be number of ways walking in this rule. The question ask for the largest set of edges such that there are no two edges with a common vertex. i.e. we can think as the sum of all number in the vertex such that no two vertex does not touch each other. The best way to take the set of vertex is taking $$$(x,y)$$$ with $$$x+y \mod 2=1$$$

     (illustration of 4x4 grid, typo fixed)

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

D can be found on oeis (somewhat indirectly):

Just take the partial sums of https://oeis.org/A000957, that's your answer.

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

    Oh,thanks!

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

    Oh crap. Of course I verified that the $$$f(n)$$$ in this problem is not oeis-able, but I haven't guessed that the $$$f(n) - f(n - 1)$$$ may oeis.

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

What is the easiest way to to find the Euler Path of a graph? ( In code ). I got to this on problem E but I couldn't implement it in time.

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

    Check this https://cp-algorithms.com/graph/euler_path.html For undirected graph to keep track of deleted edges, edges should be $$$(b_i, c_i, i)$$$ and $$$(c_i, b_i, i)$$$, so when you delete an edge you do something like $$$used[i] = 1$$$, then it would be easy to check for both $$$(b_i, c_i)$$$ and $$$(c_i, b_i)$$$ if it's deleted or not.

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

    I think an easy way to solve this is using multiset to store the graph. Using multiset you are able to delete the edges without much effort. Here's my code: 53257834

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

Today, i found the codeforces site to be extremely laggy and massive loading time was there even to just open the submission portal.This is what ruined the contest for me today :( I even dare say that the loading time must have taken 25-30 mins for me today during the contest :( MikeMirzayanov and others please tell me if i am wrong :(

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

About problem D.

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

Any hint at problem F would be appreciated ^^

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

    My solution for F1 was a $$$O(2^{m} nk^{2})$$$ dp.

    Suppose the planets you've visited are $$$a_{1}, a_{2}, ..., a_{k}$$$ in order. If you add edge for every $$$i$$$ such that $$$a_{i} < a_{i + 1}$$$, then the visited path basically looks like a bunch of forward paths. Now it's not hard to construct those forward paths by dp. Notice that a planet $$$i$$$ can only be connected with $$$i-m, i-m+1, ..., i-1$$$ in a forward path. So you've to store a mask of size $$$2^{m}$$$ in your dp state to know which of the last $$$m$$$ planets are endpoints of some forward path. You also have to store number of planets you've chosen so far. But only constructing those forward paths is not enough, because there're multiple ways you can choose to merge them, so another thing you need to store in your state is number of forwards paths that can still be merged.

    DP transitions are now not very difficult. In fact, the transition is a linear recurrence and the coefficients do not depend on current planet, so F2 can probably be solved via Berlekamp–Massey algorithm.

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

~160 tests for task with 7s TL.... Potentially ~18 minute for checking participant. Is it right?

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

    In theory, possibly. However, many of those tests are quite small (in case some would fail at some random small tests).

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

Can anyone tell me why my solution for A failed for test case 11? https://codeforces.com/contest/1152/submission/53227715

I tried the testcase manually and it showed 3 whereas the output given here is 1. What am I missing here?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    ll a[n],b[n];
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh thanks a lot

      Been scratching my head since over an hour

      Silly of me to make that mistake

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

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

Good

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

because they use that logic for problem C, I do not understand, help me plis.

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

    Let $$$a \le b$$$ and $$$d = b - a$$$ and $$$k$$$ is answer. Denote $$$x = a + k$$$, then $$$x + d = b$$$. So $$$lcm = x * (x + d) / gcd(x, x + d)$$$ . It's obvious that $$$d$$$ is multiple $$$gcd(x, x + d)$$$ and $$$x$$$ is the least multiple $$$gcd(x, x + d)$$$ (to reach the minimum). So we need to check all divisors of $$$d$$$ and find for each of them minimum $$$x$$$ which is greater then $$$a$$$ and multiple this divisor, calculate $$$lcm$$$ and choose $$$x$$$ at which the minimum $$$lcm$$$ is reached.

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

Stupid mistake costed me B lmao :/

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

How to Solve B ? I can't think of any other way except brute force!

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

    Break down the input number into its binary form. It will take at most 20 bits. Now do as the problem says. Our target is to make the binary representation of input number to contain all 1s, so will try to make every 0 convert to 1 in our binary representation. For every 0 bit in the binary representation, store it's index in the answer(vector in CPP) and xor all the following bits(including this one). Then in the next operation add one to its binary representation. You will also have to keep an optional check to see at what which step the binary representation will contain all ones. Since for each bit we will use at most 2 operations, we will use at most 40 operations. I don't think it's the most optimal(or even optimal) strategy but it appeared pretty intuitive to me(though i got a couple of wrong answers) as we can represent number less than 1000000 in 20 bits and we are allowed 40 questions(2 for each).

    Please tell me if something wasn't clear or if something was wrong !

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

    Some greedy stuff.

    First of all when it comes to $$$XOR$$$ or any bitwise calculation, first thing I consider is to do binary stuff. Change number to binary form then do some mathematical magic, you know...

    So when I look into the problem $$$A$$$, first observation is if you $$$XOR$$$ a number with a random $$$2^n-1$$$, actually you reverse $$$n$$$ consecutive bits of this number from the last bit. Then I tried to reverse the problem, like you already get the last result (some $$$2^n-1$$$), then you minus 1, and take a random $$$XOR$$$ with $$$2^k-1$$$ ($$$k$$$ don't need to be smaller than $$$n$$$). Then I realize this problem is all about processing consecutive bits $$$1$$$ or $$$0$$$.

    Change the input form (number $$$x$$$) into binary bits. Then you repeat processing $$$x$$$ from the last bit to the first bit like this until bits of $$$x$$$ are all $$$1$$$:

    Case 1: Your number $$$x$$$ is like this: ......1110000000.000 (0 consecutive bits $$$1$$$ from the last bit) or .......11100..0011111.111 ($$$k$$$ consecutive bits $$$1$$$ from the last bit and $$$k>1$$$). In general it's $$$k$$$ consecutive bits $$$1$$$ from the last bit with $$$k\neq 1$$$. Then you just do $$$x=x\oplus 2^k-1$$$ and $$$x=x+1$$$.

    Case 2: There is just 1 consecutive bit $$$1$$$ from the last bit. Let $$$k$$$ be the number of consecutive bits $$$0$$$ from the bit stands in the left of the last bit (pretty sure it's a bit $$$0$$$, cause we just have 1 consecutive bit $$$1$$$). Then you just do $$$x=x\oplus 2^{k+1}-1$$$ and $$$x=x+1$$$.

    Actually I just tried some drafts before trying my greedy guess. First I minus 1 to $$$2^n-1$$$, which you get a bit array like 111111111...110 as the result. Then you $$$XOR$$$ with a random $$$2^k-1$$$ which you get a bit array like 1111..1100000..001 as the result. Then you minus 1 again and get 1111..1100000..000 then $$$XOR$$$ again and get 1111..11000..00111..111. Then I realize every step you need to deal with consecutive bit $$$1$$$ or consecutive bit $$$0$$$ plus one bit $$$1$$$.

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

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

My submission for problem D is actualy wrong since in my solve function what I am returning is basically the maximum length after taking modulo which will result wrong comparisions. For the 1st call it may return 5 and for second call it may return 15 but since I am taking modulo before returning the 1st value could be 10^9+7+5 but I will not consider it as maximum value. Can someone tell me if there is a reson or test cases are weak?

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

    No effing way! I did the exact same thing. But I didn't submit my solution because it was obviously wrong (in fact I submitted it, but with some extra prints and I didn't bother to remove them). What my plan was: translate the code to python (for big integer arithmetic) and pre-compute (and hardcode) all solutions up to 1000. But I was 1 or 2 minutes too slow.

    But now that I read your comment, I submitted my original (supposedly wrong) solution and it got accepted! I also tested it on all 1000 possible cases and it somehow gets the right answer on every one. I guess sometimes wrong solutions just give right answers ¯\_(ツ)_/¯. I just wish I'd known that during the contest.

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

      I know it's strange right?! Could there be logical explanation or it's just a fluke that it passes all test cases?

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

        I guess the intuition is that in most cases you're taking the max of two values that differ by very little (since the left and right tries are for the most part very similar). The less the values differ by, the smaller the chance to get it wrong.

        For example, say you were taking the max of $$$a$$$ and $$$b$$$ and you know they differ by exactly 1 (suppose $$$b$$$ is greater). Then, the only case in which $$$max(a, b) \; mod \; M \not= max(a \; mod \; M, b \; mod \; M)$$$ is exactly when $$$b \equiv -1 (mod \; M)$$$, which occurs with a probability of $$$\frac{1}{M}$$$. For our problem, that's 1 in a billion times.

        Obviously, in our problem values might differ by more than 1, but still. A similar thought process can be applied as long as the difference is small. And even if you get it wrong once, there's a chance that it won't actually affect your final result.

        In other words... it's obviously a "fluke". But it's a rather "probable" fluke when you think about it.

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

    Probably the function is specific enough for those incorrect ideas to work too and it is probably impossible to make a test against it since the input is just a small number.

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).

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

How can I develop my problem solving skills? What do I do to develop my skills in algorithms and data structure?

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

    In short, you need to learn more.

    Take a shot at "Competitive Programming 3" of Steve Halim. I highly recommended it as the book has almost latest algorithms and data structures, with exercises to practice what you learn. Although you should support the author by buying the original book, you can find its pdf in the web.

    Try to learn from the experience ones. They have knowledge about the competitive programming scene, and should give you best advice about how, what to learn, what mistakes to avoid..

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

I really find how bad I'm at math,in order that I only solve 2 problems (T2 cost me 1 hour and 58 minutes)

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

nice round thanx

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

A good and interesting problem set after a long time. Hope to see more like this.

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

I think that the checker for the task D might be incorrect. I have sent the solution with dp[i][j][0/1] — max answer for the tree where the root contains i opening brackets has balance j and the root is unused/used in the answer. It is easy to calculate and the answer is max(dp[0][0][0], dp[0][0][1]). However, we calculate the values using modul so the maximum operation is invalid. But my submission(53297703) receives OK.

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

    It looks like in all cases either the second value you're taking the maximum of is 1 larger than the first value(meaning a very tiny chance to fail) or the values are the same.

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

good