Atomic-Jellyfish's blog

By Atomic-Jellyfish, 14 months ago, In English

1875A - Jellyfish and Undertale

Tutorial
Code

1874A - Jellyfish and Game

Tutorial
Code

1875C - Jellyfish and Green Apple

Tutorial
Code

1875D - Jellyfish and Mex

Tutorial
Code

1874B - Jellyfish and Math

Tutorial
Code

1874C - Jellyfish and EVA

Tutorial
Code

1874D - Jellyfish and Miku

Tutorial
Code

1874E - Jellyfish and Hack

Tutorial
Code

1874F - Jellyfish and OEIS

Tutorial
Code

1874G - Jellyfish and Inscryption

Tutorial
Code
  • Vote: I like it
  • +220
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
Rev. 2   Vote: I like it +389 Vote: I do not like it

I apologize for the unreasonable difficulty. I'm sorry :(

UPD: https://codeforces.me/blog/entry/120967

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

    chill

    thanks for the round

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

    amazing round loved it

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

    chill, in my opinion the round was great, ABCD and F were great problems (although D might be a bit too easy for a D?). It seemed that div1 was too hard but I guess that such things happen and can't be predicted.

    I'm looking forward to compete into one of your rounds again :)

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

      The scoring for D justifies its difficulty. There was a huge difficulty gap between D and E though and that's the only issue. Nevertheless, amazing problems.

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

        Next time I'll pay attention to the difficulty gap of adjacent problems :)

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

      Thanks, welcome to the next Jellyfish Round :)

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

    it was a great contest the problems were very interesting I had so much fun so thank you <3

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

    It was my first contest, littrally I solved nothing. But it was a nice experience

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

    maybe you are the king of dp :) (doge)

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

      In fact, I personally think it's the number of dp problems is too much, but it seems like a lot of people thinks it's a math-y round X_X

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

    No need to apologize at all.
    I really enjoyed the round and think that no one should be blamed after their hard work.
    I admire your work.

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

    Don't feel guilty...

    Some people will never appreciate your hard work <3

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

At some point I have just started guessing C and it worked 226022161 (only if I didn't forget to take n modulo m first)

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

    pls explain me why in Problem C my solution passed for only 60 iterations but otherwise it showed tle

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

    Can you explain why u have taken max 300 operations

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

Why my O(n^2) solution fails 226039678? Thanks in advance

»
14 months ago, # |
Rev. 3   Vote: I like it +42 Vote: I do not like it

I think you can solve Div1.D in $$$O(nm)$$$: https://codeforces.me/contest/1874/submission/225975684

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

tilted asf, how to become better on coming up with ideas for DP, ABC superfast and ... no way, i wasted 2.5 h on D and didnt solve it, but came up with O(n^3) solution first, then O(n^2*logn), tl..

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

I have one doubt . in Div2C how do we know, that for the given set of powers it is always possible to divide the apples , in a away that all m people will get that set of powers?

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

    Each person needs $$$\frac{n}{m}$$$ apples. We can divide each of the $$$n$$$ apples into $$$m$$$ pieces, then each piece is $$$\frac{1}{m}$$$, Each person takes $$$n$$$ pieces.

    This is only possible since $$$m$$$ is a power of two, otherwise we would not be able to divide an apple into $$$m$$$ pieces.

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

      Thanks

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

      thats almost right...consider n = 3 and m = 24 here m is not a power of two but its still possible....thats why actually m/gcd(m,n) should be a power of two ;)

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

        Yes what I did was take gcd, divide it from m and n at the beginning, then multiply back at the end

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

          In Div2C, Why the answer in the tutorial is m×|S|−n. Anyone help me pls, I was thinking from yesterday.

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

            Everyone should have $$$|s|$$$ pieces( $$$\frac n m = \sum_{i \in S} \frac 1 {2^i}$$$ ), there are $$$m$$$ people and $$$n$$$ pieces (each one is a whole apple), and the number of apple pieces is added to exactly $$$1$$$ for each cut.

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

I can't understand this statement:

Since it's cut in half every time, if $$$\frac m{\gcd(n,m)}$$$ is not an integral power of $$$2$$$, there's no solution.

I just made 2000 iterations simulating the process:

int op=0;
while (n && op < 2000) {
    op++;
    cnt += n;
    n *= 2;
    n %= m;
}
if(n) 
    cout<<-1<<endl;
else
    cout << cnt << endl;
  • »
    »
    14 months ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    suppose after some large no (let it be a) of iterations, let x be (n*2^a) then -> x%m (according to your code only)

    now, x%m to be zero m should be the divisor of x.

    now m can be in the form of something * 2^(something else).

    now this something cannot come from 2^a so it should come from n (see x=n*2^a) therefore m/(__gcd(n, m)) should not have any other prime factors other than two because 2 (in other words __gcd(n,m) should take all factors from m which are not 2) can be taken care by 2^a, but remaining factors have to be taken care by n itself.

    explanation might be bad english not my native language.

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

      Thank you I got it.

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

      Help me understand this in a better way, please.

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

        If you can give everyone the same piece then (n * 2^k = 0) mod m, or n * 2^k = q * m. You can factor out gcd(n, m) to get

        a * 2^k = q * b, where a = n / gcd(n, m) and b = m / gcd(n, m).

        Now if b is a power of 2, then q = a and 2^k = b satisfies the equation. But if b is not a power of 2, then b has some additional factor(s) that is not found in a (because a is coprime to b) and 2^k (since b is not a power of 2).

        Also https://youtu.be/UvnVghpIjwk?si=rmsoD_dtVNUFOtLx&t=668

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

          For 1875C — Jellyfish and Green Apple can you please explain: why __builtin_popcount(a) is equal to |S|?

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

            Because m is 2 's interger power, (a/m) is equal to |S|,and so do(a);

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

    THANK YOU !!

»
14 months ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

In problem $$$D$$$, ternary search for finding the optimal $$$x$$$ works for some reason.

In problem $$$E$$$, $$$FFT$$$ does pass without any D&C, just by computing the convolution of $$$dp[i-1]$$$ and $$$dp[n-i]$$$ for every $$$i$$$ (used the fastest 1000 lines long implementation from yosupo judge).

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

"Note that the sum of n over all test cases is not bounded." what does this mean in Div2 A problem?

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

    Usually the sum of $$$n$$$ over all test cases is such that an $$$O(n)$$$ solution would remain $$$O(n)$$$ (not $$$O(nt)$$$) even though you're answering $$$t$$$ test cases. However if $$$n$$$ is unbound, this doesn't stay true.

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

why does my div2 D python code TLE (link)

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

Div2D problem can be solved in $$$O(n)$$$ time and memory.

Let's say that mex values we add to the total score are interesting values. So main the observation is that there are $$$O(\sqrt{n})$$$ that can be interesting values. Proof: Define $$$cnt(x)$$$ as the count of $$$x$$$ in the array. Suppose that $$$x < y$$$, and $$$cnt(x) = cnt(y)$$$. We will not select both of them as interesting because it's enough to choose one. So if we choose $$$y$$$ its contribution to the answer is $$$y * cnt(y)$$$ and if we choose $$$x$$$ the contribution is $$$x * cnt(x)$$$, and as $$$cnt(x) = cnt(y)$$$ it's optimal to choose $$$x$$$. For every $$$cnt(i) = x$$$, it's enough to choose minimal $$$i$$$ as interesting value and as $$$1 + 2 + 3 + ... 2 \sqrt{n} \ge n$$$ there are at most $$$2 \sqrt{n}$$$ interesting values.

We can do DP as in editorial but only with values that can be interesting. Total complexity is $$$O(\sqrt{n}^2) = O(n)$$$.

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

    i did not understand it clearly could you explain with this example??

    0 0 0 0 0 1 1 1 1 2 2 2 3 3 4

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

      For this example, $$$n = 15$$$. Also $$$cnt(4) = 1$$$, $$$cnt(3) = 2$$$, $$$cnt(2) = 3$$$, $$$cnt(1) = 4$$$ and $$$cnt(0) = 5$$$. So 0, 1, 2, 3, and 4 (5 numbers) can be interesting values. And $$$5 \leq 2 \sqrt{15} \approx 8 $$$. We do DP only for these numbers.

      Let's see another example. $$$n = 20$$$ 0 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7. For this example only numbers 0, 2, 4, 6 (4 numbers) can be interesting. $$$4 \leq 2 \sqrt{20} \approx 9 $$$.

      And for any array count of possible interesting numbers won't exceed $$$2 \sqrt{n}$$$.

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

        oh i got it! great solution bro loved it!!

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

    It is a really nice idea and it is sad that it's not possible to make this problem use it because convex hull trick will pass anyway.

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

    why is the contribution y* cnt(y) shouldn't it be mex * cnt(y)

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

    Actually complexity is $$$O(log(n)n)$$$ or $$$O(\sqrt n n)$$$. Because you need too count numbers.

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

      you don't need an extra log to count numbers, because we can ignore all values which are not less than n

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

        Yep, but first you need to sort

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

          again, you can use count sort, so it is still O(n) )

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

There is also o(1) approach for problem b https://codeforces.me/contest/1875/submission/226021601

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

    Reading array of n numbers already requires O(n). For a reason it can't be O(1).

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

    it's not O(1) you are summing the values.

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Div2 D works with convex hull trick!

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

how the equation m×|S|−n come out in the problem Div2C? Can anyone explain this? There is no any additional comments about this in Editorial.

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

    |S| is the number of pieces of apple each person is going to get , so m*|S| will be the total number of pieces they are going to get. Since each cut increase the number of pieces by 1 and initially there are n pieces when there are 0 cuts hence for x pieces we have to make x-n cuts and hence number of cuts will be m*|S| — n.

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

    I was also stuck in how builtin_popcount_ ( or the number of set bits in a) is equal to the value of m. I got it like this:

    If each person gets a/b (simplest form of n/m) weight of apple: It is represented as 1/2^k + 1/2^l + .... and sum of all these individual parts for a person is equal to a/b. a will be the numerator . Also, we notice that on adding these we will get just some powers of 2 in numerator . and lets say 2^p + 2^q +.... =a So number of pieces for each person can be obtained as number of different powers of 2 that add up to form the numerator . ie (a), and this is just equal to the number of set bits in 'a'. Also, in one cut we get 1 extra pieces , so for m*|S| pieces , we need to make m*|s| -n cuts, as we already had n pieces when 0 cuts were made (as explained by the person above)

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

For Div1C, can someone please explain why $$$p_i$$$ is different for each $$$v_i$$$, I don't get it, it should be same according to me.

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

    It depends on what is $$$p_i$$$?
    $$$p_i$$$ is probability that both of them chose $$$i$$$, possibility after destroying some roads.
    Let's say graph has 4 outgoing edges from 1, aka $$$1->2$$$,$$$1->3$$$,$$$1->4$$$,$$$1->5$$$,
    Let $$$f_2=0.4$$$, $$$f_3=0.2$$$, $$$f_4=0.1$$$, $$$f_5=0.5$$$.

    During the first turn, Asuka will choose all nodes with equal probability, so for maximum probability to reach n, Jellyfish should choose $$$5$$$, there $$$p_5=0.25$$$.

    The second turn happens only if Asuka does not choose $$$5$$$ in the first turn.
    If $$$2$$$ still exists for the second turn, Jellyfish should choose it. $$$p_2=0.5*0.5$$$, (Asuka chose 3/4 in the first turn and 2 in the second turn).
    If $$$2$$$ does not exist, then Jellyfish should choose $$$3$$$, $$$p_3=0.25*0.5$$$. (Asuka chose 2 in the first turn, and then 3 in the second turn)

    Jellyfish will not get a third turn; he will never choose $$$4$$$, $$$p_4=0$$$,

    $$$f_1= p_2*f_2+ p_3*f_3+p_4*f_4+p_5*f_5$$$
    $$$f_1= 0.25*0.4+ 0.625*0.2+0*0.1+0.25*0.5$$$

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

      Can you explain why f[i] = $$$\sum$$$ f[j]*p[j] ?

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

        It's via linearity of expectation/probability.

        If one is at $$$i$$$, the next possible outcome is one move to one of the nodes ($$$j$$$) with an edge and eventually moves to $$$n$$$, or one remains stuck there.

        So, the probability of reaching $$$n$$$ from $$$i$$$ will be the probability of moving from $$$i$$$ to one of the adjacent nodes multiplied by their probability to reach $$$n$$$, and $$$0$$$ (probability to reach $$$n$$$ after being struck on node $$$u$$$) multiplied by probability to remain stuck there.

        Sure enough, you can also add other non-adjacent nodes in this equation but the probability of reaching them from $$$i$$$ is $$$0$$$.

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

      By calculating, p=[0.25,0.25,0.125,0] , it also satisfies the condition.

      how can we be sure it satisfies the condition without checking all cases??

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

        One cannot find all probabilities without checking all cases, just that you can memorise the subproblems via appropriate dp.

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

      Thanks, I misunderstood the problem twice, but your explanation made it very clear why the $$$p_i$$$'s would be different. But, the only issue is to calculate these $$$p_i$$$'s in general, how did you extended this approach for any general $$$d$$$ outgoing edges?

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

        Asuka chooses randomly with equal probability; by exchanging arguments, one can conclude that Jellyfish should always choose the one with the highest $$$f_j$$$, still around.

        Sort all the possible nodes in the adjacency list in descending order; then, we want to find $$$p_j$$$ of each of them, with the condition that Jellyfish will always choose the first available one.

        We can define the following $$$dp[L][R]$$$ as the probability of selecting $$$L+1$$$ th person in a sequence of $$$L+1+R$$$ people.

        DP transitions
        • »
          »
          »
          »
          »
          14 months ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          Probably the editorial was written on the same idea, but I was not able to understand it until you dropped a much simpler explanation. Thanks!

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

          thanks dude, your explanation is really clear and understandable. and maybe a typo error that in the case " chose one of the left ", the probability should be (L-1)/(L+1+R) instead of (L-2)/(L+1+R)

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

          Sorry for necroposting but is there an easy way to prove that the probability of choosing the element we want is non-increasing? Or maybe I'm not understanding the proof by exchanging arguments (that obviously works in the first step since every edge has $$$1/d$$$ probability but I can't extend it for subsequent turns...).

          I don't understand why the strategy of always going for the highest $$$f_j$$$ still around works. Won't there be cases where it's better to wait for some edges to be deleted and then choose the highest $$$f_j$$$ among all of them? In that case, we should first go for some other edge with lesser $$$f_i$$$ and then, after some turns, go for the highest $$$f_j$$$, since it would have higher probability.

          The only way I can think of is proving that $$$dp[L][N-L-1] \geq dp[L+1][N-L-2]$$$ but the formulas blow up recursively.

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

      How do you calculate p2? If Asuka chooses 3/4 in the first move, then this probability = 2/5 = 0.4, and from there, for Asuka to pick 2, it should be 1/3. So p2 should be (2/5)*(1/3) right?

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

        There are only $$$4$$$ outgoing edges from $$$1$$$, so possible choices are $$$4 (2,3,4,5)$$$ instead of $$$5$$$. So, in the first move, Asuka has to select $$$3$$$ or $$$4$$$, which has $$$2/4$$$ probability.
        In the second move, the remaining edges will be $$$1->2$$$ and ($$$1->3$$$ or $$$1->4$$$); selecting $$$1->2$$$ will have probability $$$1/2$$$.

        Overall $$$2/4*1/2$$$

»
14 months ago, # |
  Vote: I like it +6 Vote: I do not like it

You can easily optimise the Div2 D solution to O(N) by noticing that you will ever only consider deleting O(sqrt(N)) distinct elements. As the author mentioned, the deletions will be of strictly descending value but they will also be of strictly ascending count of appearance. Of course the sum of the counts of the elements we erase is bounded by N and since the counts will be distinct as mentioned earlier, the number of elements we consider erasing is O(sqrt(N)) (this is because in the worst case the counts are 1, 2, 3, .. and the sum of this series is quadratic). Then we can just do the same DP with complexity O(sqrt(N)^2) = O(N).

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

    Great observation! We could have had a harder version of the problem with $$$n \le 2 \cdot 10 ^ 5$$$

»
14 months ago, # |
  Vote: I like it -8 Vote: I do not like it
»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

For question C, turns out 1000 operations fits under the time limit and satisfies an "infinite" number of operations 226038405 :)

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

    You can even go down to a number as small as 100, since 2^100 is way greater than 10^9! Great solution, I didn't even think about brute forcing.

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

Number of Submissions(E)*Submissions(F)*Submissions(G)<Submissions(D)

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

finally got it thanks passwordisa

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

Please someone explain the mathematics behind the Div2C problem as mentioned in editorial in detail.

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

Since it's cut in half every time, if m/gcd(n,m) is not an integral power of 2, there's no solution. (Div 2C) Can anyone explain this statement?

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

    The denominator on each slice needs to be a power of two. For example, you couldn't make $$$\frac{1}{3}$$$ of an apple with slices of $$$\frac{1}{2}, \frac{1}{4}, \frac{1}{8}\cdots$$$, thus if $$$n=1$$$ and $$$m=3$$$ you can immediately say it's not possible.

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

For Div1 C, you can also think of the solution as writing n/m in binary such that the mantissa is not recurring. Why? Because you will divide the apples in powers of 2 and sum them to get n/m, which is possible in finite steps only if the sequence terminates.

And how do we know that if the mantissa is recurring? Well, if you get remainder 0 at some step then it terminates. And if you get the same reminder again, then it doesn't. To avoid storing digits, you can just check if the number is longer than 32 bits, if not, then it is recurring since its modulo is bounded and it can't extend to a digit longer than that.

Submission for reference

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

Can someone clarify the middle paragraph in Div1.B?

I don't understand why we need +1 in 4^8. Also are the nodes in the BFS functions?

thx in advance

»
14 months ago, # |
  Vote: I like it +37 Vote: I do not like it

I think tests for Div1C are not great because my solution runs in time sum of squares of degrees which is $$$O(n \cdot m)$$$ in the worst case, and I think it should be just about ok to pass the time limit. However, in reality my solution works in 75ms which is even faster than most of the other solutions that work in time $$$O(n^2 + m \log n)$$$.

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

Can someone explain me why my solution is wrong for div2 question 1. 226083957

Thought process is that whenever the timer comes to 1 we add the array element, now we have 1+array element seconds left until bomb explodes ( obviously if 1+array element is greater than permissible value then I will just take the permissible value, formally min(arr[i]+1, a) )

now we just sum this up for each element and the answer will be

initial timer value + sum

b + sum should be answer isn't it?

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

    You have int overflow, use long long instead

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

      Thanks, that does solve the problem. But one thing which I now started to have question is that why was I subtracting n from my answer.

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

        You do sum+=min(arr[i]+1,a); which actually adds one more second than the tool is supposed to, the correct statement would be sum+=min(arr[i],a-1);

        You then subtract by $$$n$$$ at the end to correct the error.

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

This was the best contest I have ever faced in a while. I enjoyed the problems so much. Thank you Atomic-Jellyfish.

I solved Div. 1 D/Div. 2 G in $$$O(nm)$$$ using an observation I didn't try to prove.

First of all, I arrived at the formula that the answer is

$$$\displaystyle n + 2\sum_{i = 1}^{n - 1} \sum_{j = 0}^{i - 1} \frac{a_j}{a_i}$$$

and optimize the nested sum using DP.

I noted that the sum is simply

$$$\displaystyle \sum_{i = 1}^{n - 1} \frac{p_{i - 1}}{a_i}$$$

if $$$p_i = a_0 + a_1 + \dots + a_i$$$. I used a slightly different dp transition with states (current index, sum of weights so far) to obtain the following formula

$$$\displaystyle dp[i][S] = \min_{1 \le w_i \le m - S} dp[i + 1][S + w_i] + \frac{S}{w_i}$$$

which can therefore be altered to

$$$\displaystyle dp[i][S] = \min_{S \le k \le m} dp[i + 1][k] + \frac{S}{k - S}$$$

Now, the observation is as follows:

Observation

This is the observation stated formally. Now, what is this really trying to say is that we can treat each

$$$\displaystyle dp[i + 1][k] + \frac{S}{k - S}$$$

as a function in the form of

$$$\displaystyle g(c, k) = c + \frac{x}{k - x}$$$

with $$$c = dp[i + 1][k]$$$, and we plug in $$$x \mapsto S$$$. Now, we need a data structure to store the maintain the minimum of these functions at a given $$$S$$$.

Assume $$$dp[n][x] = 0$$$ for all $$$x$$$. We can calculate $$$dp[i][S]$$$ for each $$$i$$$ from $$$n - 1$$$ to $$$0$$$, and since the minimization is done over $$$S \le k \le m$$$, we may loop over $$$S$$$ from $$$m$$$ down to $$$0$$$ and we may insert the function $$$g(dp[i + 1][S], S)$$$ in the data structure for minimization.

So, we see that the data structure receives the functions in the form of $$$g(c, k)$$$ where $$$k$$$ keeps strictly decreasing. Now, to maintain what is the minimum function at $$$x = S$$$, we use the observation that we noted. We maintain a deque (or monotonic stack) containing pairs $$$(c, k)$$$ where $$$c_1 < c_2 < \dots$$$ and $$$k_1 < k_2 < \dots$$$.

When we receive a new $$$(c, k)$$$, it must be that $$$k < k_1$$$, and (1) and (2) in the observation tell us that if $$$c \ge c_1$$$, then we don't care since $$$g(c, k)$$$ will be minimal at every non-negative $$$x$$$. If $$$c < c_1$$$, we insert $$$(c, k)$$$ in the front of the deque, since (3) in the observation tells us that there is an intersection where $$$g(c, k)$$$ will become less than $$$g(c_1, k_1)$$$ and thus optimal.

Finally, we note from (4) that the intersections of the functions in our data structure are increasing, and between each two intersections one function overtakes the other function as being the optimal. So, we can note that while the current $$$S$$$ is greater than the intersection of the last two functions in the deque, we can just remove the last function. Then, we query at $$$x = S$$$ in the last function in the deque. This works in Amortized $$$O(nm)$$$.

Note: I calculated the intersections using equations from Wolfram Alpha.

Here is my submission.

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

In Div2 D, why do we need to subtract the initial MEX from dp[0]?

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

    Think of it this way: [ a * ( cnt[b] - 1 ) + b ] + [ b * ( cnt [ c ] - 1 ) + c ] = a * cnt [ b ] + b * cnt[ c ] + c - a

    But since c must end up being 0, it becomes minus a, which is the original m

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

Can anybody explain me why my code in problem C was showing tle

Your code here...
int n = in.nextInt();
            int m = in.nextInt();
            HashSet<Long> a = new HashSet<>();
            if(n % m == 0){
                pw.println(0);
            }else if((m & 1) == 1){
                pw.println(-1);
            }
            else{
                long l = n % m;
                long ans = 0;
                while(l != m){
                    if(a.contains(l)){
                        ans = -1;
                        break;
                    }
                    a.add(l);
                    ans += l;
                    l *= 2;
                    if(l > m){
                        l %= m;
                    }
                }
                pw.println(ans);
            }

but when i iterate in while loop for less than 60 iteration it passes

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

    The sequence takes O(n) steps before it terminates. In your code, you check the whole sequence which goes up to 1e9, and the number of test cases is 2e4, so overall you do around 2e13 operations which gives you TLE.

»
14 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Can anyone prove that precision error wont blow up in D1C?

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

Great contest...

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

thx for the round, really cool div1B, I love it.

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

    Can you please explain ? What are the nodes of Bfs? and how is the time complexity calculated? Thanks in advance

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

Amazing Div1B !

  • »
    »
    14 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I used bfs each time and it finally passed because I found there were only a few situations ($$$\leq 1000$$$). After reading the solution, I think it's a good problem.

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
What's the feeling when you solved Div2.G with...
  • »
    »
    14 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    What is quadrangle inequality?

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

      Why does a pupil need to know that? Stop learning useless algorithms. Mr. bilibilitdasc can learn it because he's already IGM.

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

      If a function $$$w$$$ satisfy $$$\forall l_1 \leq l_2 \leq r_1 \leq r_2, w(l_1, r_1) + w(l_2,r_2) \leq w(l_1,r_2)+w(l_2,r_1)$$$, it is said $$$w$$$ satisfy the quadrangle inequality.

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

Where is the solution of 1875B?

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

Can someone explain me ,I have some doubt in 1875C — Jellyfish and Green Apple

I got till this part So we can uniquely find a set of positive integers S satisfying nm=∑i∈S12i

But how we get the answer by ,what is the logic We can use std::__builtin_popcount() to get |S|, the answer is m×|S|−n.

And moreover since we devided n and m by gcd(n,m), so first ideally we should compute no of operation for one group(the group we get by deviding m by gcd(m,n)) and then multiply that with gcd(n,m) to get the total operation.

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

    Each cut increases the number of apples by 1. Since each person needs to get |S| apples in his account, final number of apples will be m*|S|. Since there were initially n apples, so we get the cuts by subtracting this from final apples, hence the answer m*|S| — n.

    Also, for the intuition why to multiply a group ans by gcd(n,m) (as you say) goes by the following example. Suppose n = 30, m = 48. Then a = n/gcd(n,m) = 5 and b = m/gcd(n,m).= 8. Ans for one group is = 8*2-5 = 11. Now the number of groups have become 6 i.e. gcd(n,m). Hence the answer will be 11*6 = 66, which is same as that given by taking all n and m (48*2 — 30) = 66.

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

Fun fact: we add 1B to prevent the large gap between 1A and 1C.

And Atomic-Jellyfish got the idea of 1G, when playing game. (xd

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

In div1 B, why there is $$$5^8$$$ cases instead of $$$4^8$$$ cases?

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

    Oh i understand

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

      can you explain...i am still not getting it

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

        Because your are going to record the shortest path's source and destinations, and since there maybe some types of $$$(a_i,b_i,m_i)$$$ that will not exist in the $$$(a,b,m)$$$, so except for all $$$(c,d)$$$ that is $$$(0/1, 0/1)$$$, there is another destination called "not exist", so the state is in total $$$(4+1)^8$$$.

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

          what do you exactly mean by "some types of (ai,bi,mi) that will not exist in the (a,b,m)" ? can you give any example...thanks a lot

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

            For example, $$$a=(1111)_2,b=(1111)_2,m=(0001)_2$$$, in this case, pair $$$(1, 1, 0), (1, 1, 1)$$$ exist and others like $$$(0,0,1)$$$ not exist, so you only need to consider the shortest path from $$$(1, 1, 0), (1, 1, 1)$$$ to there specific $$$(c_i,d_i)$$$, so except the $$$4$$$ state $$$(0/1,0/1)$$$, in the pre-calculation there is another state which is "not exist"

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

              can you also attach your submission...tutorial solution is too complicated to understand

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

                I haven't implemented this problem yet, maybe later.

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

                I think the author used some math (base 5 number representation and bitmask) to encode the states.

                Let's see what does $$$5^8$$$ mean again? (thanks many helpful friend here helped me to understand it)

                • First, let's clarify this: Given same $$$(a,b,m)$$$ state of two different bit $$$i$$$ and $$$j$$$, no matter what we do, the resulting bits at position $$$i,j$$$ in $$$(x,y)$$$ must be the same.

                • From then we can just care about different $$$(a,b,m)$$$. For multiple bits that have same $$$(a_i,b_i,m_i)$$$, we can use one to represent the whole group. Now, effectively all numbers can be seen as some special 8-bit numbers.

                • The base, if is in range $$$0..3$$$, then corresponds to 4 cases of some arbitrary $$$(x_i, y_i)$$$ we can make from some $$$(a_i, b_i, m_i)$$$. If base equals $$$4$$$, it means that there isn't any $$$i$$$ such that $$$(a_i, b_i, m_i)$$$ forms the configuration $$$(a_{fixed}, b_{fixed}, m_{fixed})$$$ we're considering

                • The exponent, from $$$0$$$ to $$$7$$$, corresponds to the position, or more precisely the group I mentioned above.

                Take a look at this example: 00004002 is a base-5 number corresponding to a state:

                • Last digit is $$$2$$$. It means that the 0-th group, which is $$$(a,b,m) = (0,0,0)$$$, has $$$(x,y) = (1,0) \text{ (number 2)}$$$

                • 3-th digit is $$$4$$$, it means that the group $$$(a,b,m) = (0,1,1)$$$ contains no bit in it!

                • For the remaining 6 groups, they just have the same $$$(x,y) = (0,0)$$$

                So why do we have to represent data this way? In this representation, we see:

                • Destination and Starting point are being tied together (with destinations $$$(x,y)$$$ as digits, and starting point $$$(a,b,m)$$$ as position (or call it order, exponent, ...))

                • Although we kind of "separated" individual bits to come up with the solution, yet in the solution they must be stored together !? Because each operation AND, OR, XOR affects each bit of the numbers. They're all transforming after each operation, so their values must be recorded and observed altogether.

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

                  Thanks for the explanation. It's really helpful.

»
14 months ago, # |
  Vote: I like it +13 Vote: I do not like it

For E,how can I use BFS(breadth-first search) for preprocessing? I wonder why to use BFS and how to use BFS.

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

    Suppose we start with $$$x = 1$$$, $$$y = 1$$$, $$$m = 0$$$. What are the possible $$$(x, y)$$$ reachable using the 4 operations given and the minimum number of operations to achieve that state? We use BFS for that purpose.

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

    Each state of the numbers is a node, each operation changing from one state to another is an edge.

    Therefore, a sequence of operations that transforms the init. configuration to the desired configuration, is a path between 2 nodes.

    And minimum number of operations is just equivalent to the shortest path. In this case, it's unweighted graph so BFS is sufficient

»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

In problem 1B, why there are $$$5^8$$$ states instead of just $$$4^8$$$?

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

    $$$2 * 2$$$ for each possible $$$(c_i, d_i)$$$, and another $$$1$$$ corresponding to when there is no state for that $$$(x_i, y_i, m_i)$$$.

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

Could somebody elaborate the following editorial for Div1D?

The only thing we need to do is the dot product of the functions, so the time complexity of the transition is also $$$O(n^4)$$$

Does it mean that is there a way to directly evaluate $$$[x^i] F_n(x)$$$ for each $$$i$$$ in $$$O(n^2)$$$ time? And what does it have to do with dot product?

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

    I think what is meant is that you store all $$$F_k(x), k \leq n$$$ in point value form $$$ (i, F_k(i))$$$, for $$$O(n^2)$$$ points.

    Convenient is to use the points $$$i = 0,1,2,3,4, \dots$$$. All operations needed (summing, convolving two polynomials, shifting the polynomial with $$$x^n$$$) can be done in time linear in the size of the representation, so in $$$O(n^2)$$$. Afterwards, the only thing left is from the point value form of $$$F_n(x)$$$, going back to the coefficient form. This can be done with the lagrange interpolation formula in $$$O(n^4)$$$ with some tricks (You need to first with brute force calculate the coefficients of the polynomial $$$x \cdot (x-1) \cdot (x-2) \cdot \dots $$$, and do polynomial division to obtain each of the summands of the lagrange interpolation polynomial.

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

      Ah, now I understand! So let me rephrase it:

      • For each $$$x = 0, \ldots, n(n+1)/2+1$$$, we want to evaluate $$$F_n(x) \in \mathbb F_p$$$. (I wrote $$$\mathbb F_p$$$ to emphasize that we want to find a scalar, not a polynomial)
      • To do so, let us fix $$$x$$$:
        • Then it is sufficient to find the sequence $$$\displaystyle \lbrace F_i(x) \rbrace_{i=0}^n$$$ of $$$\mathbb F_p$$$, successively from the initial element to the final.
        • The recurrence relation $$$\displaystyle F_i(x) = x^i \sum_{j=1}^i \binom{i-1}{j-1} F_{j-1}(x) F_{i-j}(x)$$$ enables us to find $$$F_i(x) \in \mathbb F_p$$$ for each $$$i$$$ in an $$$O(i)$$$ time.
        • Thus, $$$F_n(x)$$$ can be found in an $$$O(n^2)$$$ time.
      • Therefore, $$$\lbrace F_n(x) \rbrace_{x=0}^{n(n+1)/2 + 1}$$$ can be found in a total of $$$O(n^4)$$$ time.

      All that left is to do Lagrange interpolation, which I understand well. Thanks a lot for the explanation!

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

Why my solution fails 226099505? Thanks in advance!

The input and output of my answer are the same as the example!!!

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

can someone explain div2A. Why it isn't min(a-1, x-1) according to the condition

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

    We get the optimal solution if we use the tool when the timer is at 1. If we increase the timer past $$$a$$$, it will be set to $$$a$$$. We have two outcomes:

    $$$(x + 1 \leq a):$$$ timer change, $$$1 \to x + 1 \to a$$$ increase of $$$a- 1$$$

    $$$(x + 1 < a):$$$ timer change, $$$1 \to x + 1$$$ increase of $$$x$$$

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

any better explaination for div2 c?

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

    I'll try to explain it as best as I can.

    When dividing the n apples among the m people, if n is greater than or equal to m, we can give each person n // m apples. After doing this, we can disregard how many apples each person has because they all have the same amount. We can now focus on the n % m remaining apples.

    Let's say a = n % m. If we have no remaining apples (a == 0), then we have finished. Otherwise, we have to make a cuts to now give us 2 * a apples. If (2 * a) % m == 0, then we have finished. Otherwise, we have to make 2 * a more cuts to give us 4 * a apples. We do this until (a * 2^k) % m == 0, where k is the minimum number that satisfies the equation.

    Now we have to figure out when there is no answer. In order for there to be an answer, (a * 2^k) % m == 0. This means that a * 2^k == q * m for some integer q. In order for this equation to be satisfied, all of m's non-2 factors must also be in a. If m had a non-2 factor that weren't in a, then it wouldn't be a divisor (it can have some factors of 2 that aren't in a because of the 2^k factor). This means that gcd(a, m) must have all of the non-2 factors that m has. This means that m / gcd(a, m) must be a power of 2. We can perform this check at the beginning of program and then proceed.

    Here is what I did: https://codeforces.me/contest/1875/submission/226131697

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

      nice explaination:) thanks a lot

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

      If m had a non-2 factor that weren't in a, then it wouldn't be a divisor (it can have some factors of 2 that aren't in a because of the 2^k factor). This means that gcd(a, m) must have all of the non-2 factors that m has.

      a * 2^k == q * m

      why q was not consider, can it have non-2 factors?

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

        Let's ignore the 2^k for now. If a = q * m, it means that both q and m are factors of a. Therefore a must have any factors that q and m has. If a didn't have a factor that m has, for example, we could have something like 3^2 = q * (3 * 5), and there is no positive integer solution here for q.

        So, by this logic, we can see that all of m's factors must be present in a, so therefore gcd(a, m) = m, and m / gcd(a, m) = m / m = 1 (or in the original problem it must be 2^c for some c). So at the end of the day, q doesn't really matter at all.

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

      Thank you so much, you saved my life, oh, I'm really happy now that I found an explanation, I was so confused, I think you must be the maker of all editorials, I probably wouldn't understand without you why did we use m/gcd(m,n) at all, thanks very much :)

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

i learned a lot from problem C, thank you Atomic-Jellyfish

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

:3

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

If max(a)>max(b), MAX=max(a). If min(a)=max(a), then min(a)>max(b), Jellyfish will do nothing. Otherwise, Jellyfish won't swap the apple with value MAX. In the tutorial for 1874A — Jellyfish and Game, can anyone explain to me what Otherwise means? Is do nothing and won't swap is different?

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Think there's a mistake in 1874C — Jellyfish and EVA tutorial. The transition should be:

$$$ \forall 1 < i \leq k , g_{k, i} = g_{k-2, i-2} \times \frac{\mathbf{i - 2}}{k} + g_{k-2,i-1} \times \frac{k-i}{k} $$$

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

    Typo, thanks for the correction!

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

      For 1875C — Jellyfish and Green Apple can you please explain: why __builtin_popcount(a) is equal to |S|?

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

        For example, if a = 13, b = 32, each person will get 3 pieces of apple, a is 1101 in binary, 1101 = 1000 + 100 + 1(in binary), which is an apple piece with 8/32 kg, an apple piece with 4/32 kg, an apple piece with 1/32 kg.

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

          ok i got this but why you have taken a = n / __gcd(n, m)??

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

            We need to reduce it to its simplest fraction. for example, n = 5, m = 20, n/m = 5/20 = 1/4, the popcount of n is 2 but the popcount of a is 1.

»
14 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone please explain the editorial of D1B?

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

can someone please explain why gcd(m,n) in problem C Div.2

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

Need a better explanation for div 2 E. It doesn't provide details about what preprocessing you're doing and how it helps in solving the tests.

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

Atomic-Jellyfish may you explain a bit in detail what you mean "by greedy and induction" we would arrive at those conclusions? what induction step is there ? greedy would be I think just wanted to make the sum more at each round by the one who is making the move .

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

    "By greedy and induction" means, we can get the result of k rounds of the game from the result of k-1 rounds of the game, for example, if k=2, Jellyfish will know what Gellyfish will do in the next round, which is the result of k=1, this is "induction". The result of k=1 is very easy, which is written in the tutorial — swap the max and min. Thus when k = 2, you can predict what your opponent will do next, for each of your operational scenarios, you will choose the best one, this is "greedy"

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

How do we prove that the optimal answer is m×|S|−n for Div2 C? .

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

    Somehow i managed to prove it myself.

    Let us assume that $$$\frac{m}{\text{gcd}(n, m)}$$$ is a power of $$$2$$$ . So we can say that $$$\frac{n}{m}$$$ can be finitely represented as some binary representation like $$$\sum_{i \in S} \frac{1}{2^i}$$$.Each individual people is going to get $$$\frac{n}{m}$$$ weight of apples and he will get this weight in denominations of $$$\frac{1}{2^i}$$$ . For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we need to have exactly $$$m$$$ pieces . For an apple of weight $$$1$$$ we can get $$$2^x$$$ pieces each weighting $$$\frac{1}{2^x}$$$ and this will cost $$$2^x - 1$$$ cuts. For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we need to have exactly $$$m$$$ pieces each weighting $$$\frac{1}{2^i}$$$ and it can be done using $$$\frac{m}{2^i}$$$ number of apples having initial weight of $$$1$$$ and for each apples it will cost $$$2^i - 1$$$ cuts . For each $$$i$$$ in $$$\sum_{i \in S} \frac{1}{2^i}$$$ we would need exactly $$$\frac{m}{2^i}(2^i - 1)$$$ cuts . Total number of cuts will be $$$\sum_{i \in S} \left(\frac{m}{2^i}(2^i - 1)\right)$$$ . We know that $$$\frac{n}{m} = \sum_{i \in S} \frac{1}{2^i}$$$, then $$$n = m \sum_{i \in S} \frac{1}{2^i}$$$.So, the expression $$$\sum_{i \in S} \left(\frac{m}{2^i}(2^i - 1)\right) = \sum_{i \in S} \left(m - \frac{m}{2^i}\right) = \sum_{i \in S} m - \sum_{i \in S} \frac{m}{2^i} = m|S| - n$$$.

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

      "Since the number of apple pieces is added to exactly 1 for each cut, So we just need to minimize the final number of apple pieces." So $$$m \times |S|$$$ is the final number of apple pieces, $$$n$$$ is the number of apple pieces in the beginning.

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

Solution for Div2 D with comments:

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

#define MOD // 1000000007
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ull> vull;
typedef pair<ll, ll> pll;

#define umap unordered_map
#define vec vector
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(), x.end()


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll t; cin >> t;
    while (t--) {
      ll n; cin >> n;
      umap<ll, ll> counts;

      for (ll i=0; i<n; ++i) {
        ll v; cin >> v;
        counts[v]++;
      } 

      ll mex = 0;
      while (counts.find(mex) != counts.end())
        ++mex;
      
      // dp[i] stores the minimum value of m to reach
      // a mex of i. So we're trying to find dp[0].
      vll dp(mex+1, INT_MAX);

      // In the beginning value of m is 0
      dp[mex] = 0;

      // We find dp[i] from the higher values to the lower
      // values, till 0.
      for (ll cur_mex=mex-1; cur_mex >= 0; cur_mex--) {

        // For any given current mex, we can reach there from a
        // higher mex value. For eg. if initially the mex of the
        // array is 7. To reach a mex of 4, we can first
        // delete 5 and the delete 4, or directly delete 4.
        // (ofc you can delete 6 also, just an example.)
        for (ll prev_mex=cur_mex+1; prev_mex <= mex; ++prev_mex) {

          dp[cur_mex] = min(
            dp[cur_mex],

            // Suppose we're trying to reach 4 from a mex of 5,
            // and there are 3 4s. After deleting the value 4 for 2 times
            // the mex is still 5, so we add 5*2 = 10. But on
            // deleting the last 4 the mex is now 4 and we add 4.
            // In general the transition is
            // (c - 1)*prev + cur 
            dp[prev_mex] + (counts[cur_mex] - 1)*prev_mex + cur_mex
          );

        }
      }

      // The answer is minimum value of m to reach a mex of 0
      cout << dp[0] << endl;
    }
    
    return 0;
}
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Round! div.1 CD are both counting problems, typical style of CNOI ig

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

In problem 1874C — Jellyfish and EVA, in second test case, I have no idea why the output is "0.625000000000".Please explain to me.

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

i understand the implement of div2G but i still don't know how do we get that formula. Can anyone help me explain that formula

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

amzing solution about div2c!

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

I didn't understand how the graph is constructed in JellyFish and Math problem, author of this editorial didn't explicitly explain how it is done, and I am not able to figure it out from the code, any help will be appreciated. Thank you

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

    I've understood the problem, I'am going to write up the solution in complete detail because I believe the solution provided leaves out a lot of detail that are not obvious at all

    First we need to encode reachability information from initial state of $$$x=a, y=b$$$ We do that by focusing on each bit of $$$x, y$$$ and $$$m$$$ as follows (since bits are independent and same bit combination goes together)

    We're going to represent reachability information from initial state as follows

    For each possible combination of initial state $$$(a, b, m)$$$ there are only 4 possible states it can reach to $$$(0/1,0/1)$$$, and there are 8 possible initial states, so we can represent each of them using a 8-digit base 4 number, and we're only going to need $$$4^8$$$ possible configurations.

    Example : for configuration 00001003

    1. initial state (0,0,0) can reach 3 = (1,1)
    2. initial state (0,1,1) can reach 1 = (0,1)
    3. all the other state can reach (0,0)

    What is the initial configuration ? It is simple, for each digit corresponding to $$$(a, b, m)$$$, its value is simply $$$(ab)_2$$$

    Now, we want to find all such reachable configurations (cause clearly not all $$$4^8$$$ configurations are reachable), we do that by using the operations to define transitions

    Each configuration can reach to exactly 4 different configurations in a single step (using the different operations given as follows)

    Using operation op, we define the transition as

    For each digit corresponding to state $$$(a, b, m)$$$, say it is $$$(xy)_2$$$ we create new reachable state $$$(x'y')_2$$$ given by operation op (eg: in case of $$$op==1$$$ we have $$$x' = x\&y$$$, $$$y'=y$$$)

    Remark : We're changing all the digits because from a configuration of $$$(x,y)$$$, in one operation it changes all of its bits, so the all 8 groups must be changed to reflect that.

    All the configurations reachable from initial config in this graph are exactly all those configs that are reachable from init config (preserving the number of steps), kind of obvious but this construction is quite meticulous

    Now that we have this graph we can do a BFS over it starting from initial configuration, and we can get all the states reachable from it along with minimum number of steps to reach that particular state.

    Now, given $$$a,b,c,d,m$$$, we need to find a configuration where for each $$$(a_i, b_i, m_i)$$$ digit we have $$$(c_i, d_i)$$$ value at that digit, to find that we simply compute that configuration as say config and compute dist[config].

    In case we get in consistency, while computing config i.e. if different bits of input corresponding to same $$$(a, b, m)$$$ values but has different $$$(c, d)$$$ value, then that configuration is not reachable. Doing this requires 5 states instead of 4. (so we'll instead encode using 5 base numbers, using 4 to specify state isn't set or we can say 4 is don't care)

    What if dist[config] == INF ? In this case we do not have any immediate inconsistencies, but the state is simply not reachable in the directed graph

    Hope that was helpful

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

if m/gcd(n,m) is not an integral power of 2, there's no solution. can someone explain me this line of editorial of div2 question3

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

    The denominator on each slice needs to be a power of two. For example, you couldn't make $$$\frac{1}{3}$$$ of an apple with slices of $$$\frac{1}{2}, \frac{1}{4}, \frac{1}{8}\cdots$$$, thus if $$$n=1$$$ and $$$m=3$$$ you can immediately say it's not possible.

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

It's very interesting that 1C doesn't involve determining an actual optimal strategy, but instead we somehow just skip that and directly calculate the probability distribution of outcomes in an optimal strategy.

Not sure I followed how we ensure that the derived distribution corresponds to a valid strategy though. And how do you even come up with the recursion for $$$g_k$$$?

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

Why the div1 has the b div2 and doesn't have c&d div2 ?

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

.

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

Can someone explain why my method for calculating the expected number of step to reach $$$n$$$ in Div.1 D is wrong? I think on this for a few times but still can't find what stuff goes wrong :/

My approach is as followed:

First consider using linearity of expectation, we will get

$$$E[\text{# of steps needed to reach n from 0}] = \sum_\limits{i = 0}^{n - 1} E[\text{# of times edge (i, i + 1) being traversed}]$$$

then obviously every edge will be traversed from left to right, and every time it got traversed from right to left, it will also be traversed from left to right eventually, so we have

$$$E[\text{# of times edge (i, i + 1) being traversed}] \\ = 1 + 2 \times \sum_\limits{j = 0}^{\infty} Pr[\text{edge (i, i + 1) being traversed from right to left j times}] \times j \\ = 1 + 2 \times \sum_\limits{j = 1}^{\infty} Pr[\text{edge (i, i + 1) being traversed from right to left at least j times}] \\= 1 + 2 \times \sum_\limits{j = 1}^{\infty}(\frac{w_{i - 1}}{w_{i - 1} + w_i})^j = 1 + 2 \times \frac{w_{i - 1}}{w_i}$$$

which lead to the final answer

$$$n + 2\sum_\limits{i = 0}^{n - 1}\frac{w_{i - 1}}{w_i}$$$
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

include

include

include

using namespace std;

void solve() { long long int a, b, n; cin >> a >> b >> n;

vector<long long int> v;

int x; for (int i = 0; i < n; ++i) { cin>>x; v.push_back(x); }

int flag = 0;
int k = 0;
long long int sec = 0;
while (flag != 1) {
    if (b == 1 && k != v.size()) {
        b += v[k];
        k++;
        b--;
    } else {
        b--;
    }

    if (b == 0) {
        break;
    }

    if (b > a) {
        b = a;
    }

    sec++;
}

cout << sec << endl;

}

int main() { int t; cin >> t;

while (t--) {
    solve();
}

return 0;

} this code gives me timed exceed on second test can anything be done inorder to fix it ?

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

Sick problems!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it
"Since you are one of the smartest people in the world" this flattered me THANK YOU !! (><)
DIV1 P1