diskoteka's blog

By diskoteka, 11 months ago, translation, In English

1848A - Vika and Her Friends

Idea: diskoteka

Tutorial
Solution

1848B - Vika and the Bridge

Idea: diskoteka

Tutorial
Solution

1848C - Vika and Price Tags

Idea: pavlekn

Tutorial
Solution

1848D - Vika and Bonuses

Idea: diskoteka

Tutorial
Solution

1848E - Vika and Stone Skipping

Idea: diskoteka

Tutorial
Solution

1848F - Vika and Wiki

Idea: pavlekn

Tutorial
Solution
  • Vote: I like it
  • +149
  • Vote: I do not like it

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

A,C,D and E are just math problems. Cf should do better.

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

Problem statements were too long.

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

look at As editorial :0

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

I agree with the general mood that A-C of the contest were too hard. D-F were okay, although in E $$$M$$$ should have been set larger than $$$O(Q \log x)$$$ to prevent the edge case where one of the prime powers reaches $$$M$$$.

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

    Why should setters prevent corner cases instead of contestants preventing them in their code?

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

      This is a Div 2 codeforces contest. Because this is Div 2 where the contestants aren't necessarily that strong, and because this is codeforces where the pace of the competition is very fast, it should be more about solving the problem than implementation and avoiding corner cases.

      Also, it looks like the authors made the same mistake, hence the explanation that Test Case 15 (the first case with that corner case) was incorrect and the solutions had to be rejudged.

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

        This is a Div 1.5 contest, so include purples in your thesis. "not strong div2 participants" wouldn't reach E anyway.

        Btw my opinion on this problem is: why the fuck is it variable mod? Why not just use constant mod 1e9 + 7? It seems some coordinators or setters are addicted to using variable mod for no reason other than worsening the runtime of people's solutions.

        I didn't know about test case 15, that slipping by testing is a big oof.

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

          There are problems where variable mod is needed, in particular the problems where there are limited amount of parameters and it's possible to locally compute all the possible answers with a slower code then submit the result.

          I agree that for this problem there is no such reason and a constant 1e9+7 is better.

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

          Div2 contestant also should have rights to solve E with certain wisdom ,instead of getting cornered by this kind of modulo trick. In fact that’s almost irrelevant to the main idea of this problem, which i think is conducting the numbers of factors (forgive my terrible English)

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

          I think that because the setters want to avoid the solution using inverse modulo to recalculate the product (p/s: sorry for my bad English)

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

      well, stupid edge cases are no fun (the original problem when i tested had a constant mod > 1e9)

      also, the setters themsevles got the case wrong....

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

I liked A and B, even though the latter was mostly implementation. C and D were too mathy and guessable though.

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

problem statement of A was pretty confusing for me.

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

There exists an $$$O(n)$$$ solution for problem C, which is better than the editorial's $$$O(n\log a_i)$$$:

Submission

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

    Can you explain your solution, i read but i can't understand

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

      I can't prove it, but it's correct:)

      The first few steps are the same as editorial. On finding out how to calculate $$$(a,b)$$$'s answer, write a brute force first. Then u can notice the patterns the same in my code:P

      If someone can prove it I'll be very grateful.

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

        Actually it the same as second solution of editorial: "Thus, we can determine the remainder cnt modulo 3 by looking at the pair (a/d, b/d) modulo 2".

        Let a = 2**g * ra, b = 2**h * rb

        ra, rb — odd numbers.

        If g > h, then:

        a / gcd(a, b) = 2**(g — h) * (ra / gcd(ra, rb)) — even number

        b / gcd(a, b) = (rb / gcd(ra, rb)) — odd number

        In case g < h, first will be odd, second even.

        In case g == h, both are odd.

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

    This is O(n log(n)) Only to calculate the number of trailing zeroes it takes log(n) times only.

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

      Hi, __builtin_ctz() is an inbuilt function of G++ that only have $$$O(1)$$$ complexity as far as I know. Correct me if not:)

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

        https://codeforces.com/blog/entry/59268

        Though it does the bitwise calculation, it is too fast to get noticed, but the complexity is still O(log(n)). You can verify this by manually writing the code for it, and you will see that it takes the same time.

        Click on compare the previous solution in the below submission.

        https://codeforces.com/contest/1848/submission/214137912

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

          I can't really agree. It seems on my local machine that __builtin_ctz(x) is at least 30 times faster than the handwritten one. as the handwritten one has the complexity of $$$O(\log n)$$$, I would say that __builtin_ctz(x) has to be something like $$$O(1)$$$.

          Here's my code and results:

          Test 1:

          __builtin_ctz() running 1e7 times, 0.02 s on average
          handwritten __builtin_ctz in your previous submission running 1e7 times, 0.6s on average

          Test2:

          change the lim in the first code to $$$10^8$$$, and it runs 0.2 s on average; change the lim in the second one to $$$10^8$$$, and it runs 6.1 s on average.

          What do u think about that?

          upd: i did another test, i changed the get(x) to:

          int get(int x)
          {
              return 2*x;
          }
          

          and $$$lim$$$ is still $$$10^8$$$. the average time is 0.24s! That means the inbuilt function of g++ seems to be even faster than adding two numbers together! What's ur opinion?

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

            theoretically, it is still n log n but practically it is O(n)

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

              idk how __builtin_ctz() is implemented,but i still think its real complexity should be real close to $$$O(n)$$$.

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

                Godbolt says there's special "bsf" assembler instruction for it.

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

          Stop posting misleading content you are discussing popcount but ctz only needs x&-x

          and popcount isn't O(log n) too it's O(log w) like O(log log n).

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

    how did you arrive at the intuition of using 2 highest power in solving it.

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

      I'm stupid, I don't have intuition, I write brute force, I observe patterns, I draw conclusions, I implement, I pass

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

        hai hai sensei!

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

        What was the logic in your brute force code that showed some pattern?

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

This contest problem statements are too long like a reading comprehension.

I think C is more difficult than D

May be I'm too foolish , but what is the tutorial of C's meaning???

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

Personally I don't think problem A is too hard for its position. The idea is fairly common in game theory puzzles like https://www.youtube.com/watch?v=dh4nEuhZBgg and just requires a bit of good intuition.

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

diskoteka [user:pavlovn]

My thoughts on this round:

The problems themselves were fine.

I do think A was not suitable to be a div2A, but that’s because I think div2A’s should be “submitbait”. The problem itself was fine, and may have done better as div2B.

Perhaps D was too math-y than ideal, but that’s fine.

Perhaps E could’ve had $$$M \geq 10^8$$$ or have been fixed, but it wasn’t much extra (and it is not too hard to generalize to all $$$M$$$). It is bad that the sequence is on OEIS though, so ideally this problem shouldn’t have been used.

Also, don’t listen to the haters, and please keep setting contests. Over time you’ll get better, and this contest probably provided good feedback!

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

    ty very much

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

    True! A problem based on chess with mathematical proof indeed shows that Diskoteka is a smart person. Also with experience, they will get great at problem setting too!

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

      could you link some resource or some other questions like A which use similar logic.

»
11 months ago, # |
  Vote: I like it -20 Vote: I do not like it

C was a beautiful problem!

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

Your tutorial for problem D should write (b+20x)(a-4x), not (b+20x)(a-x) in the 4th paragraph, as reflected in your code.

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

Easier for F is just doing binary lifting as soon as you know the power of 2 thing. It's basically the same solution but O(NlogN) and you don't have to think about reducing it to an array of size N/2.

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

For problem A, vika's friends can see her(vika) right? So they see her and try to modify their movement right? Can vika see her friends as well?

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

    If we color the rooms like a chessboard, and at least one of her friends starts on the same color as her, that friend has the strategy, and can react to her movement(because she moves first) in such a way that no matter what she does, she eventually will be caught, this is explained in the editorial. So, whether Vika tries to avoid her friends or not, it doesn't matter.

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

please explain me this(Problem A):

1 2 1

1 1

1 2

I think when vita goes to right , friend will catch him . Perhaps, i misunderstood something.

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

    both vika and her friend should perform a move .So they're just going to swap rooms forever and never meet each other.

    a friend catches vika only if they find themselves in the same room after performing the move

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

      During contest, I understood from statement so:

      First vika goes, then her friend.

      Thanks

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

    yeah they will be in the same room no doubt but her friend has to make move thats why being on the same room doesnt matter as long as that friend has perform her move

»
11 months ago, # |
  Vote: I like it -103 Vote: I do not like it

This is the WORSR contest i've ever seen. Can you just stop writing such long description of problems?? If you want to show your ability of writing, you don't need codeforces. And problems DEF are so easy to think, the difficulty is too low to be the div2 DEF, it can be used in div3. The quality of the problems are also too low I think. And the awful test cases of problem E, can you just check your test cases before the contest? To my surprise, this contest has not been unrated, but I don't want to see such contest like this anymore. YOU DO NOT NEED TO CREATE THE CONTEST IF YOU DO NOT HAVE THE ABILITY OR YOU DO NOT WANT TO DO IT WELL!!!

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

when problem A has the longest tutorial, you know you did something wrong.

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

wthforces

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

I don't get why so much hate for this round. A is better than normal, I liked problem C quite a bit, and rest of problems were fine. (yet another round with no datastructure tho ;-;)

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

    You could've used a segment tree in order to avoid the corner case in E lol

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

      I wonder why they even used prime mod. Either used fixed or force this....

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

    Problem — A was quite lengthy from a beginner perspective and difficult to prove.
    Otherwise the rest of the contest (I mean A-D, I haven't read E and F) was fine.
    (I struggled a little bit to decipher the language in A (and B for that matter) The story of friends catching "Vika" but having a greater affinity to make a move seems inconsistent and looks like a bad attempt to make the problem look real worldish when it isn't).

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

      I agree A could've been worded better, but I don't think it's bad enough to greatly worsen round.

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

Sorry ,but I feel A lengthy and language is very tricky

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

In solution1 of problem C , it will be ai-4*bi in place of ai-4ai

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

can someone explain me the problem statement of B in easy way.. i have read it multiple times but i am not able to understand

thanks..

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

    vika can paint any particular plank of her choice. you have to figure out which one so that she has to step over minimum number of plank

    condition is that she will be jumping on only same color planks.

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

Problem A was way too unbalanced for its position and difficulty range. Its not a great idea for begineers

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

in task B, isnt it necessary to mention in the problem statement that k distinct colourst will definitely be present.

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

for problem A, i figured that if there are odd number of cells between Vika and friend, they will meet.

And, to calculate the number of cells between them, i thought of using this formula:

d = |vx-fx|+|vy-fy|.

for ex, if this value d is 1, means they are in adjacent cells(or there are no cells between them), so they wont ever meet

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

    No, for d=0 it means they are in the same cell (You have taken absolute value) . For d=1, it means adjacent cells

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

My solution for A :
So we need to check for every position (i,j) in n*m grid, if there is a position where both main person and anyone among the k people have the same distance to (i,j). So we iterate over every position and check whether the distance of main person is same as distance of any of k friends to that position. TC : O(n*m*k).
AC code : 214108505

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

After reading editorial for problem A, do you still feel like this is DIV-2 A problem ?

diskoteka

Only in Vika-land, problem would need this much logical thinking and proof for problem A solution.

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

Because of problems like A, people start to hate math in cf-contests. The problem would be great if it were at the math contest, but not at cf.

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

    Exactly, and also if you make A like this people leave the contest, so the round receive less partecipation as well.

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

If someone is making a video tutorial on A and B please share it

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

Personally, I loved this round! I only solved ABCD, but this round had better problems than most recent Div2s in my opinion. I don't understand why the announcement blog post was downvoted. Keep making rounds!

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

ive done other coding contests but this was my first cf contest and i solved 0 questions, so skill issue for me ig

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

    as you can tell from the malding in the comments this contest was harder than usual, esp A

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it
auto itr = Map.rbegin();
++itr;

to get access of previous element of itr, do ++itr instead of --itr! due to this, I was not able to submit problem B :(

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

can any one explain problem D editorial please? I noticed the cycles before reading the editorial, but the formula??

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

In problem C, I have a different way of finding the $$$cnt_i\% 3$$$ mentioned in the editorial.

Similar to solution 2, we will build the sequence from the end. It will be of the following form:

$$$... x, x/2, x/2, 0 ...$$$

Now try to build a tree of all possible values before $$$x$$$. You will notice values in a particular level are either of the type $$$odd * x / 2$$$ or $$$k * x$$$ where $$$k$$$ is a positive integer. You will also notice that $$$k * x$$$ has a period of $$$3$$$, same as the period of $$$0$$$.

So the problem reduces to finding which of the $$$a_i, b_i, c_i$$$ is of the type $$$k * x$$$.

Here's my submission.

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

    i am still not able to understand your approach, can you explain in more simple way. thanks.

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

      Think of the first time $$$a_i$$$ becomes zero. It will be of the following form:

      $$$...k, k, 0...$$$

      What would come before $$$k$$$? Let it be $$$y$$$, solving $$$|y - k| = k$$$ we would get $$$y = 2*k$$$. So the sequence now becomes

      $$$... 2*k, k, k, 0 ...$$$

      Similarly, try to find what would come before $$$2*k$$$. From here, multiple values might be possible for each position. For example, before $$$2*k$$$, both $$$3*k$$$ and $$$k$$$ are possible values.

      Try to draw a tree of these values. $$$2*k$$$ will be the root and $$$3*k$$$ and $$$k$$$ are its children. It will be something like this: https://binary-tree-builder.netlify.app/?indextree=2*k,3*k,k,5*k,k,3*k,null,8*k,2*k,4*k,null,4*k,2*k.

      In this tree, at each level, the values are either of the type $$$even*k$$$ or $$$odd*k$$$. You will also notice $$$even*k$$$ has a period of $$$3$$$, just like the period of $$$0$$$.

      Now consider a situation where $$$a_1 = even*k$$$ and $$$a_2 = odd*k$$$. Then we know that both $$$a_1$$$ and $$$a_2$$$ won't become $$$0$$$ at the same time.

      So we need all $$$a_i$$$ to be $$$even*k$$$ or all $$$b_i$$$ to be $$$even*k$$$ or all $$$c_i$$$ to be $$$even*k$$$. Only then we will get all zeroes at the same time.

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

        The best explanation I found so far. But why (all ai or all bi or all ci) need to even*k. why not just check if all ci are even*k only? why we have to check ai and bi too?

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

          We might have something like this:

          $$$a = [odd*k_1, even*k_2, odd*k_3, ...]$$$
          $$$b = [even*k_1, odd*k_2, even*k_3, ...]$$$
          $$$c = [odd*k_1, odd*k_2, odd*k_3, ...]$$$

          As you can see, this will not result in all zeroes occurring at the same time.

          Now consider the following:

          $$$a = [odd*k_1, odd*k_2, odd*k_3, ...]$$$
          $$$b = [even*k_1, even*k_2, even*k_3, ...]$$$
          $$$c = [odd*k_1, odd*k_2, odd*k_3, ...]$$$

          This will result in all zeroes occurring at the same time. So its important that you check all $a_i$, $$$b_i$$$, $$$c_i$$$.

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Real Div.2 contest<:

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

What a round!

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

diskoteka, in the editorial of C, while writing Solution 1: I believe where you wrote

(ai, bi, ai — bi, ai — 2 * bi, ai — 3 * bi, ai - 4 * ai)

(and should have written: ai - 4 * bi)

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

Have anyone solved Problem-A using BFS without getting TLE ? looking at the constraints, I thought it was a graph related problem but getting TLE on pretest 3.

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

    Same I too tried to implement a bfs/dfs/backtracking soln, but the actual soln is game/mathematical based!

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

Thank you diskoteka for great math problems, better than previous div(1,2) speedforces

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

E and F are well known math problems.

E: 2016 AMC 12B P16

F: Trivial special case of 2023 USA TSTST P9

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

It has been pointed out to me that the setup for F is actually identical to USA TSTST 2023/9 with $$$p^e=2$$$, although I’m not sure how much knowing the solution to the TSTST problem helps with the codeforces and vice versa. At the very least, one of the solutions to the TSTST problem proves that you will never print $$$-1$$$ (see the first claim in post #5 by a familiar-looking user).

Edit: sniped by the person who pointed this out lol

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

    The first part of the TSTST problem tells you what the operation becomes after applying it $$$2^i$$$ times.

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

      Oh true—the explicit computation of the $$$k$$$-th finite difference implies that for $$$k=2^i$$$, we have $$$\Delta^{2^i} f(n) \equiv f(n+2^i)+f(n) \pmod{2}$$$, since by Kummer's theorem/Legendre $$$\binom{2^i}{a}$$$ is even unless $$$a \in {0,2^i}$$$, which more or less reduces this problem to a straightforward binary search

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

Great round! Like these problems very much :3

We've found some alt ways to solve F, but they have higher time complexity.

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

A is too hard...

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

I think problem A is harder than problem B.

»
11 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Different Approach For Problem C. Code

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

    Can you explain how it works, like why does the highest power of 2 matters?

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

In the first question(Vika and her friends)

How does the area decrease when vika moves in the opposite direction and the friend moves towards her, shouldn't it remain the same??

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

    On a long enough time-frame, vika will reach the border & cannot move in the opposite direction & will be forced to move in a direction that reduces the distance between her & her friends, the catch to the problem is that this cat-mouse game happens infinitely!

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

Problem provider 114514

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

Then, if the cycle is "scroll" x times, the discount will be (b+20x)(a-x)

WHY NOT (b+20x)(a-4x)?

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

In C, I tried to find the number of operations to make ai zero manually in the hope of getting some pattern or some formula but all in vain. May be they should try not to give such mathematical things till C.

C is one of those problems which gives neither the pleasure when I solve them nor guilt when I could not.

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

The background of the problem is just too long, and it's really frustrating! I completely understand your pain. Why do they have to pile up so much unnecessary information? It could have been expressed concisely and clearly, but instead, they make us read a whole paragraph just to understand the problem. It's such a waste of our precious time and energy! And sometimes, the background information has absolutely nothing to do with solving the problem. It's like a test of our patience and endurance. The problem should be about solving the actual problem, not reading a background story! I really wish the problems could be more direct and concise, so that we can focus more on solving the challenging tasks at hand!

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

Problem A statement was so confusing to me, also IMHO this can't be a DIV2 A. All candidate masters and above in the comments trying to justify why it's not bad, of course you don't mind it because if you do it is a problem. Go justify Div1 A and leave Div2

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

problem A is the most difficult ever. I can solve B,C, but A is a impossible task for me.

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

Thus we call a hall with coordinates (c,d) a neighbouring for it if |a−c|+|b−d|=1. Why this statement is even in the question it confused me a lot , I thought that in few test cases Vika canthave an adjacent neighbouring room so she cannot move anywhere

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

Can someone break down C for me, I observed a few things during the contest.

Let a>b for all below expressions, if not we can just move to the next stage where b and |a-b| will fit the scenario(moving one parity ahead).

Every pair will eventually reach a loop of GCD(a,b), GCD(a,b), 0. So essentially we needed to check if every pair have the same parity (%3 values of the number of steps they reach 0). I also noted that we can go from a,b to a%b,b keeping the same parity, except for when (a/b ==1). And that is where it stopped for me.

I saw some people use a%2b to move a parity ahead, but where does that 2 come from?

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

    I'll use pair notion meaning $$$(a, b)$$$ pair becomes $$$(b, |a - b|)$$$.

    Consider some large $$$y$$$ and small $$$x$$$: $$$(x, y) \Rightarrow (y, y - x) \Rightarrow (y - x, x) \Rightarrow (x, y - 2x)$$$.

    We made 3 operations meaning it wont change amount operations modulo 3, therefore you need to find largest $$$k$$$ i.e. amount of operations that: $$$0 <= y - k(2x) < 2x$$$ which is literally a definition of remainder.

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

      Thanks! I understood the pattern. During the contest I just mistook (I was trying to guess it rather than calculate it down ;_;) the pattern to be repeating with (a,b) -> (a%b,b) which is wrong I guess, which is why it will fail for floor(a/b) = 1.

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

      can u prove doing this way + perform the said operation will not be more than logarithmic

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

        I don't understand why do you need to prove this fact since it's literally gcd-like + you literally can implement it and test on big random numbers but here you are:

        Since operation in pairs are not simmetrical you can't assume WLOG $$$x \leq y$$$ so I'll let you do $$$x > y$$$ by yourself ;)

        So I'll be doing $$$x \leq y$$$ case:

        Now consider two cases:

        1. $$$4x \geq y$$$, then pair $$$(x, y)$$$ becomes $$$(y, y - x)$$$ where $$$y - x \leq \frac{3y}{4}$$$, $$$(y, y - x) \Rightarrow (y - x, x) \Rightarrow (x, y - 2x)$$$. Congrats! we have reduced second term by at least 3 quarters, since $$$y - x \leq \frac{3y}{4} \Rightarrow |y - 2x| \leq \frac{3y}{4}$$$

        2. $$$4x \leq y$$$, then $$$(x, y)$$$ becomes $$$(x, y \ \% (2x))$$$. Congrats! we reduced second term by at least half

        This yields next conclusion: rough estimate for upper bound of steps is $$$3*log_{4/3}(y)$$$ which is good enough. The rest of the proof is up to you

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

Typo in d editorial:

$$$(b+20x)*(a-4x)$$$

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

I found a very interesting pattern for problem C. For every i, we count number of trailing zeroes in binary representation of A[i] and B[i], now if A[i] has more, then this pair can be made 'dull' in 3k steps, if B[i] has more, then 3k+1 steps, and if they both have equal trailing zeroes, then 3k+2 steps. And we just have to ignore A[i]=B[i]=0 case.

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

I think my solution is slightly similar in intuition to problem A, but is much simpler.

For any friend to be able to reach Vika, the Manhattan distance between them must be even. So, what I mean is, if the distance between Vika and all friends are odd, then they'll never reach her, but if any one distance is even, that implies that the friend will be able to reach Vika at least at some point of time in future.

I'm not exactly sure yet how to explain or prove this, but I feel it can be better understood if one can just draw out some testcases and check.

In case the claim I made is incorrect, do provide your suggestions, I'll be grateful :)

Here is my submission

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

Can someone provide me with clear insights on Problem C? Or provide resources to learn the topic. It is clear to me that the only thing that matters is the modulo 3 of the first occurrence of zero for each position of the array. But I find the tutorial very confusing on how to proceed further (maybe I am missing some number theory / modular arithmetic prerequisites)?

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

    Consider several cases of a[i] and b[i]. Such as:

    1. Both are odd. [O,O]

      • Then the first difference ($$$O-O = E$$$) will be an even number. [O,E]
      • second difference ($$$O-E = O$$$) will be an odd number. [E,O]
      • third difference will be an odd number. [O,O]
      • Now, we know that the sum of the numbers keeps reducing and one of them reaches $$$0$$$ eventually.
      • So at what parity can a[i] = 0 occur from above observations?
      • Ans: At all "second differences" , because zero is even
    2. Similarly analyse cases of [O,E] and [E,O]

    3. The case of [E,E] is interesting. You can observe that they will mimic the behave of the numbers we obtain by doing successive division by 2.

      • Eg: [4,6] will mimic the behaviour of [2,3].
      • So case 3 can be collapsed into cases 2 and 1.

    You know the story after this.

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

Hi every one in problem B i didn't use k in solving problem

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

Can someone pls tell me what is wrong in this solution for C? 214173357

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

    Nvm silly mistake figured it out, but now weirdly enough this submission is giving a RTE for some reason, can someone tell me why? 214174585

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

At this point, I don't even want to read the problem. It looks like a marathon.

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

Did everyone lose rating? Half of the people must have gained acc to algo

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

I didn't understand the solution explained for problem C. Can someone explain it clearly.

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

LC Better

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

Who can explain the tasks C, D? I didn't understand the author's decision at all

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

    problem C:

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

      how to prove complexity of urs code is log

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

        It's similiar to the complexity of GCD and that's log.

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

          But that we can prove .Here (a,b) where a>=2*b or b>=2*a remains in the same state for more times.Its not exactly same .from this state to say them same is not reasonable

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

            Assume that a>=2*b.(if 2*b>a>=b , My code do the same thing as GCD)

            GCD : (a,b) → (b,a%b) , 1 step makes the biggest num decrease from a to b.

            Mycode :(a,b) → (a%(2*b),b).

            I. 0< a%(2*b) < b. 1 step too , same as GCD.

            II. b<= a%(2*b) <2*b . Then we go the second step: (a%(2*b),b) → (b,a%(2*b)-b). 2 steps makes the biggest num decrease from a to b.

            so Mycode's complexity is no more than twice of GCD's . That's log.

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

              (a,b)

              three cases :

              1) a>=2*b

              2) 2*b>a>=b

              3) a<b

              fourth thing each state will be one of three

              first case u proved in 1 or 2 steps will be same as (b,a%b)

              second case u also proved in 1 step can get to (b,a%b)

              third case can be reduced to (b,b-a) one of case 1 or 2(can take 3 steps)

              a %b==a-b only if 2*b>a>=b

              VERY WELL DONE

              here is my implementation of the same approch (not even a single change ) https://codeforces.com/contest/1848/submission/214252557

              • »
                »
                »
                »
                »
                »
                »
                »
                11 months ago, # ^ |
                Rev. 2   Vote: I like it -16 Vote: I do not like it

                if wanted its complexity can also be O(2*logn) or O(3*logn) -complexity at the heart

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

      thank you very much!

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

      Hey man, how were you specifically able to come up with the a >= 2 * b condition. Can you please explain your thought process behind it?

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

The tutorial is clear.

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

any one solve b by using Binary search ??

»
11 months ago, # |
  Vote: I like it -10 Vote: I do not like it

WTF you haven't said that sum of Ks over all test cases is at most 200000 in B!

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

Is the kind of reasoning used in problem E familiar to high-rated coders? Looking at the tutorial, I don't see any way I could have solved the problem on my own, so I want to know if people who solved it are well-versed with such kinds of reasoning or if it came to them naturally.

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

Can someone please explain what does area to Vika mean? Is it something other that the number of blocks between Vika and one of her friends?

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

Although i was unable to solve any problem during the contest, But i enjoyed a lot. Specially, problem A. Moreover, i felt a bit uneasy to read the statements.

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

Simpler Solution for A:

  1. Every move, the parity of R+C changes by 1 for both Vika and her friends. Therefore, a friend can catch up to Vika if and only if the sums of their coordinates have the same parity.

  2. Because the friend moves after Vika, she can always decrease the distance between the two of them. By contrast, Vika can only increase distance by moving in the same direction as the gap between her and her friend (e.g. if Vika is three units to the right of her friend, she can only decrease horizontal distance by moving to the right). Because the map is finite, Vika will be forced to decrease the distance between her and her friend after a maximum of R+C moves, and so she will eventually be captured.

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

    Nice .In both dimensions the distance cannot remain same .just follow vika steps .he will be caugth

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

Problem E Observation: # of odd divisors = # of distinct initial f can also be proved in the following manner:

  • Consider all the pairs of [l,r] such that $$${\sum_{i = l}^r i = x}$$$

  • We are sure the the lengths len of all these segments have to distinct

  • So we need to find what all valid lengths are there. We have the following formula

$$$x = len \cdot ((len+1) / 2) + len \cdot k$$$
  • Consider one of the case where len is even. The case when len is odd is similar to prove.
  • let len = 2p and p>=1
$$$x \equiv len \cdot ((len+1) / 2) \pmod{ len }$$$
$$$x \equiv p \cdot (2 \cdot p + 1) \pmod{ 2 \cdot p }$$$
$$$x \equiv ((2 \cdot p) \cdot p) + p \pmod{ 2 \cdot p }$$$
$$$x \equiv p \pmod{ 2 \cdot p }$$$
$$$x = (2 \cdot t + 1) \cdot p $$$
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why is question b tagged binary search

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

where did the formula (b+20x)(a-x) in D come from?

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

    In any case, except for 5 and 0, the last digits will start following the pattern of 2,4,6,8 after a certain point. so we can make the formula as for not taking a discount 4 times we will have an increase in b by 20(2+4+6+8) and a decrease in the number of purchases left by 4.

    if we do this process x times then the discount i can get is (b+20*x)*(a-4x).

    and the formula in the editorial is partially wrong(missed 4*x).

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

I have created video editorial for problem A,B and C in english link. If you understand it, upvote.

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

Why is this giving TLE in problem C? Submission ID:https://codeforces.com/contest/1848/submission/214346070 But this is not. Submission ID: https://codeforces.com/contest/1848/submission/214346500 I am not able to figure out the cause.

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

Why do we need to compare x and x+1? x = (5*k-s)/40; x = min(x,k/4); x = min(x+1,k/4); Isn't the first x already the largest?

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

Can anyone please give me a more intuitive idea of the induction of problem F? I mean how can we see it happen beside trying to prove the equation?

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

Maybe there is something wrong with problem A statement. What will happen when $$$n=1,m=1$$$?

In this case none of the girls can move to the neighbouring rooms, which violates your statement.

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

Finding $$$cnt_i\%3$$$ in problem C is not that hard I think.

$$$[a,b]$$$ will change like this $$$[odd,odd] \to [odd,even] \to [even,odd] \to [odd,odd] \to ... $$$

And $$$a$$$ can be $$$0$$$ in only $$$[even,odd]$$$.

(of course if both number is $$$0$$$ a is always $$$0$$$ and otherwise we can divide numbers by $$$gcd(a,b)$$$ so we can remove $$$[even,even]$$$ case)

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

Can anyone share there solution for D using ternary search. Mine is failing. My solution for D

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

In Problem D why are we only subtracting 1 from k after every iteration, shouldn't we take into account the fact that we are performing 4 * x number of operations and adjust k accordingly?

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

cf should do better

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

A can be done through brute force too , just go to each cell , if distance from vika's starting cell == distance from any of her friend's cell , then vika can't escape

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

I didn't quite understand the line Can someone explain it :

If Vika and the friend are in the same column, then the area to Vika is equal to the sum of the areas of all rows in the direction of Vika and the row where the friend is located.

Am I the only one not getting it ?

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

in problem C ,We will build the sequence from the end. Let's find the first moment when we obtain 0 . Before this zero, there is some number d . It can be easily proven that d is exactly equal to gcd(ai,bi).

How to prove it?

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

great contest, do consider making more contests please. [user:diskoteka][user:pavlekn]

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

I spent quite a long time upsolving C in coming up with the formulas to accelerate the procedure when $$$a>b$$$... I have no knowledge of gcd algorithms... how can it make the problem easier?

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

How to approach solve B by binary search??

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

the friends of vika try to checkmate her xD.

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

Has anyone solved question B using binary search? If so, could you please share the solution? My solution getting wrong on test 2. My solution for B

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

The solution of C is poorly written. "Then, the sequence of numbers will have the form: (ai,bi,ai−bi,ai−2⋅bi,bi,ai−3⋅bi,ai−4⋅bi,bi,…) ." is wrong take ai = 5, bi = 3: sequence will be :5,3,2,1,1,0 clearly bi(3) is not appearing again and again as written int tutorial.

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

Anyone who implemented the binary search solution of B. My Binary Search solution is failing on test case 2. Can someone help me out with this?

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

    I have a solution using binary search by answer https://codeforces.com/contest/1848/submission/214106278

    for each color, we save their coordinates including the last n in the array and then check the difference between them if it is greater than the middle, we paint this board once, if we have already painted the board, then we continue to look for this one in another color or in the answer

    This is not my solution I saw from another user.

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

Alternative solution to F using SOS DP:

Notice that the value of $$$a_0$$$ after $$$k$$$ operations is the xor of all $$$a_i$$$ such that $$$\binom{k}{i}$$$ is odd.

Why?

Lucas's theorem states that $$$\binom{p}{q}$$$ is odd if and only if $$$q$$$ is a submask of $$$p$$$. Thus, the value of $$$a_0$$$ after $$$k$$$ operations is the xor of all $$$a_i$$$ such that $$$i$$$ is a submask of $$$k$$$. This can be computed in $$$O(n \log n)$$$ using SOS DP. We know that after $$$n$$$ operations all $$$a_i$$$ become zero, so the answer is the first moment that $$$a_0$$$ becomes zero and stays zero.

Submission

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

    Yeah this was the solution I found (admittedly I didn't realize its truth was due to Lucas's Theorem). Let to a very beautiful implementation :)

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

F: Could the answer be -1? Why?

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

    3 2 2 0

    at this testcase isn't it -1?

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

I'm wondering how is one suppossed to come up with a proof such as one presented in tutorial E (or even think of proving the idea that number of odd divisors affects the answer)? Is that even Div2E level? The ideas used in the proof such as considering the parity of $$$cnt$$$ seem so random to me. I'd be grateful if any math gods would explain to me how to think about such problems or if you would show me more intuitive proof than the one in tutorial.

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

diskoteka could you suggest any learning resource or problems that could help me solve problems similar to problem A in this contest.

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

Could anyone please explain why in Problem C it is necessary to do x=(x%2*y), what is it essentially doing to find the first occurence of 0;

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

for the problem C what sum decreases there i don t understand it really.

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

Here is another way to think about the operation in Problem F which I like.

Since $$$\oplus$$$ is the same as addition $$$\pmod{2},$$$ let us consider the operation: $$$a_1, a_2, \ldots, a_n \to a_1 + a_2, a_2 + a_3, \ldots, a_{n} + a_1$$$ where addition is taken modulo $$$2.$$$ Indices mod $$$n.$$$

Let us iterate it and see what happens: After two iterations we get $$$a_1 + 2 a_2 + a_3, \ldots, a_{n} + 2 a_1 + a_2.$$$ After three iterations, we have $$$a_1 + 3 a_2 + 3 a_3 + a_4, \ldots, a_{n} + 3 a_1 + 3 a_2 + a_3.$$$

It looks like after $$$j$$$ iterations, the sequence looks like

$$$\binom{j}{0} a_i + \binom{j}{1} a_{i+1} + \cdots + \binom{j}{j} a_{i+j}$$$

Indeed, you can prove this using induction with pascal's identity. So what we really are looking at is Pascal's triangle mod 2, ie. Sierpinski triangle.

Now, we have nice properties of $$$\binom{n}{m} \pmod{2},$$$ such as $$$\binom{2^k}{m}$$$ is even for all $$$1 \leq m \leq 2^k-1,$$$ and $$$\binom{2^k - 1}{m}$$$ is odd for all $$$m.$$$ You can prove them using Lucas' theorem.

It follows that after $$$2^k$$$ iterations, the terms are $$$a_i + a_{i + 2^k}$$$ mod 2. So since $$$n = 2^k$$$ is a power of two we know that after $$$n$$$ iterations they all become zero, $$$a_i + a_{i + n} = 2 a_i = 0.$$$ I initially just showed it for $$$2^{k+1} - 1$$$ iterations, which is also not hard to see since all the binomial coefficients are odd.

It's also interesting to note that this is a linear map $$$f : (\mathbb{F}_2)^n \to (\mathbb{F}_2).$$$ Additionally, if you write out the matrix of the linear map, $$$M = \begin{pmatrix} 1 & 1 & 0 \ldots & 0 & 0 \newline 0 & 1 & 1 \ldots & 0 & 0 \newline & \vdots & \ddots \newline 0 & 0 & 0 \ldots & 1 & 1 \newline 1 & 0 & 0 \ldots & 0 & 1 \end{pmatrix}$$$

it is a Circulant Matrix so one may write out the eigenvalues explicitly and consider the restriction to the field $$$\mathbb{F}_2.$$$ This also makes it easy to compute the powers of the matrix. $$$\newline$$$ $$$\newline$$$ Finally, here's an nice mathematics problem which is (somehow) closely related to this problem; a friend shared this actually right around mid July, same week as this CF round.

Let $$$\varphi : \mathbb{Z}^n \to \mathbb{Z}^n$$$ be a function mapping on tuples of integers such that:

$$$\varphi(x_1, \ldots, x_n) = (|x_1 - x_2|, |x_2 - x_3|, \ldots, |x_n - x_1|)$$$

For some inputs, repeatedly iterating eventually yields the zero vector $$$(0,0,\ldots,0).$$$ ie. there exists some $$$k$$$ for which $$$\phi^k(x_1,\ldots,x_n) = \phi(\phi(\cdots\phi(x_1,\ldots,x_n) \cdots )) = (0,\ldots,0).$$$

For which positive integers $$$n$$$ is it true that repeatedly iterating $$$\phi$$$ eventually yields the zero vector, no matter what the input is?

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

can anyone tell what bug is in this code I tried using shadow clone jutsu on umnik submission but CF is finding the original one here

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

nvm