By awoo, history, 17 months ago, translation, In English

Hello Codeforces!

On 20.10.2022 17:35 (Московское время) Educational Codeforces Round 138 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

| Write comment?
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to cross 1100 <3

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

    Best of luck bro

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

    What F*ckhead created problem C ?

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

      What is wrong with this problem?

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

        Oh excuse me, absolutely nothing.

        Its just IMPLEMENTATION IS TERRIBLE

        If you don't have a specific idea, you gonna (-s-u-c-k-) Perform bad

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

          Firstly, If you don't have a specific idea on any problem you cannot solve it

          And secondly, bruteforce with simulation which is two nested cycles and five simple ifs is not that hard to implement

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

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

When You Realize After The Contest You're Getting The WA Only Because Of a Typo

edit: and that was me today too I spent one hour because of a typo but gladly solved C in the end

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

Thanks awoo! Hope the problems will be as great as the last contest. And i hope to become a pupil again in this contest. Best of luck everyone!

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

.

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

»
17 months ago, # |
  Vote: I like it -105 Vote: I do not like it

I want to be the user with the lowest contribution in codeforces, can you help me?

»
17 months ago, # |
Rev. 3   Vote: I like it -19 Vote: I do not like it

Oh yeah by the way, awoo where's the list of testers?

upd: nevermind, realized previous edu contests didn't have testers either

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

This sleepless night, I'm going to hit my highest rating, you give me a good look.

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

HAPPY VIETNAMESE WOMEN'S DAY – October 20 ❤️❤️❤️

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

Edu Rounds are my best ❤❤

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

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

Hoping to cross 2050! Good luck!

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

time to be specialist

»
17 months ago, # |
  Vote: I like it -27 Vote: I do not like it

Hoping this contest to be math free ...

(Screenshot-2022-10-20-154601)

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

best of luck, guys! my second contest. hope to solve at least A again :)

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

I forgot my notebook and my school's computers don't have any IDEs nor compilers in them.

Gonna use an online compiler. Let's see how it goes

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

Thanks for the round, C is the stupidest problem I have ever seen.

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

    You couldn't solve it doesn't mean the problem was bad.

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

      It's not that I couldn't solve it, it's a trivial n^3 simulation, I just didn't feel like implementing it. I just don't think problem C should be just a straight forward implementation, instead it should be some smart idea.

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

Seeing the number of solves of each problem and my experience, I feel that it was a pretty balanced round with a good gradient of toughness of the problems. (Though, some users might have had a sour experience with problem C)

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

How to solve C?

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

    I've just simulated it; iterating through from k = 100 to k = 0, if Alice wins then print out the k and return

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

    Binarysearch, with greedily picking Alice the biggest less than or equal to k-i+1, and Bob picking lowest left value. Storing values in multiset.

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

    To win a game with k turns, the array must have at least k '1', and at least 1 number that is smaller or equal to 2, 3, ..., k. This is because Bob can use a strategy to lock the final move out by adding to each '1' once. Therefore, Bob can lock at most (k-1) '1', so the array must have k '1' to compensate. From there, just search out for the solution!

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

    C can also be solved in $$$O(n)$$$ time without using Binary Search. The important observation to make here is that during the $$$k^{th}$$$ stage Alice must remove an element $$$1$$$ from the array. Thus, the optimal strategy for Bob is to always remove $$$1$$$ (by adding $$$k-i+1$$$ to it) at every turn. If the count of $$$1$$$'s becomes zero before the $$$k^{th}$$$ stage is reached, Bob automatically wins.

    Hence, we store the frequency of every element $$$a[i]$$$ in an array $$$cnt$$$. Note that the answer is zero iff $$$cnt[1] = 0$$$ else the answer will be $$$\geq 1$$$. Now, we iterate over every $$$k$$$ from $$$2$$$ to $$$n$$$, while maintaining a counter $$$cur$$$ which stores the number of elements $$$\geq 2$$$ and $$$\leq k$$$ which have not been deleted yet. In every round, Alice must delete a number $$$\leq k$$$, so if $$$cur > 0$$$ we decrement $$$cur$$$, otherwise we decrement $$$cnt[1]$$$. We then decrement $$$cnt[1]$$$ to account for Bob's move. Now, if at this point $$$cnt[1] \geq 1$$$ then Alice can always make her final move and win if she chooses to play $$$k$$$ rounds. So we update $$$ans$$$.

    Submission: 177175786


    UPD 1: Why is a move by Bob equivalent to removing an element from the array?

    Claim: Any element modified by Bob in the $$$i^{th}$$$ round cannot be removed by Alice in any further round.

    Proof: Let Bob modify the element $$$a[j]$$$ in the $$$i^{th}$$$ round. Therefore $$$a[j]$$$ changes to $$$a[j] + (k - i + 1)$$$. Note that in the following rounds, all the elements Alice removes are $$$\leq {k - i + 1}$$$.
    However, from problem constraints,

    $$$a[j] > 0\implies a[j] + (k - i + 1) > k - i + 1$$$

    Hence, the Claim is proved, and we can say, for the purposes of the solution, that the element has been "removed" from the array.

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

readforces

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

.

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

    Binary search

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

    bob can win iff he can destroy all 1 in the array while alice kept choosing the largest possible option, then simulate with two pointers

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

      I was just curious looking the hacked solution of Unknown_VN_Coder by k12 and his submission to the same problem. And I think that it was a fake hack. I could be wrong though

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

        that solution will shut itself after outputing 'non' if t==13 for whatever reason and got hacked just as he wishes like piles of other such hacks, idk why people kept doing this

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

    Video Solution for Problem C and Problem D

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

Problem B : Justt think in a simple wayy O_O

Me : Bruhh lets do a simple graph and get 2x WR <(_ _)>

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

Isn't E a dp problem. Let $$$dp[i][j]$$$ means minimum number of extra cactus need to be added for right part of grid from column $$$j$$$ to $$$m$$$ if I put a cactus at $$$(i, j)$$$ .Why am I getting wrong answer.

Anyone help please, Submission: https://codeforces.com/contest/1749/submission/177209214

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

    Yeah, I tried many examples for last 30 mins but couldn't really figure out the counter example. I wish I could see the test 2 now...

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

      Many submission have got WA on same test case (563).

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

    UPD: this was invalid testcase. Look at the comment just below it for a test case

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

      I think your test case is invalid.You cannot have cactus on two adjacent cell. But i may have figured out where my solution is wrong.

      1
      6 6
      #.....
      .#....
      ..#...
      .#...#
      ..#.#.
      ...#..
      

      My solution will give 1 but actual is 0

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

      That is not even a valid placement of cacti. Probably the issue of most WA submissions was one-directional dp, while we needed bfs.

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

was it just me or C was really challenging?

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

    I think C is just a C, as always

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

      Actually C is bit easy in this round, but i wasnt able to solve b this round , C is prefixsum problem , in which there should be atleast "k 1's" , "k+1 numbers <=2" , "k+2 numbers <=3" , similarly till k , you can check this Problem_C_Solution

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

        it doesn't need much analysis actually. you just brute force all k and simulate the game. optimal action for both players is just simple greedy

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

Can someone tell me what is wrong with my modular arithmetic please? https://codeforces.com/contest/1749/submission/177211216 I got the algorithm done with 30 minutes left, then spent the rest of the time trying all combinations and figuring out how my modular arithmetic is wrong...

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

    The issue is the range of m. For example, you multiply by m/2. Use (m/2)%MOD instead.

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

      Thanks for replying! I already tried (m/2)%MOD, but it is still wrong... https://codeforces.com/contest/1749/submission/177211216 There are probably a lot of things wrong in there TwT

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

        you have another problem : int n,m; int ans = 0, minu = m; int po[300005];

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

          I already defined int to be long long so the int stuff should work out normally

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

        No, you are still multiplying by m/2. You need to do minu *= (m/2)%MOD; minu %= MOD. In the end, you also need ans %= MOD before if(ans<0)

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

          Sorry for posting the same solution :_: this is the with (m/2)%MOD but still wrong https://codeforces.com/contest/1749/submission/177215823 Do you have any links to learn modular arithmetic in CP so that these problems aren't happening again? Thank you!

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

            Change n, m, ans, etc to long long, then I guess it will be fine. What about wiki page? https://en.wikipedia.org/wiki/Modular_arithmetic Or you can just read the intro section of any elementary number theory book.

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

              Thanks for your help! Unfortunately, I still could not find out what went wrong, maybe finishing it tonight tho...

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

                minu = m % MOD. But seriously, the diagnostics message is already pointing the exact problematic line in this case. It doesn't make sense that you can't debug this.

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

                  thanks so much for all the help! I cannot believe how did I miss that either, was the difference between -20 and +80 this contest lol

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

                change this line : int ans = 0, minu = m; into this two lines :

                int ans = 0, minu = m;
                minu %= MOD;
                

                here is your code getting AC : 177225248

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

                  Oh my god why did I miss that... Thank you so much, forgot the initial part of modding the first

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

Can anyone please share their approach for Problem E?

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

    It's a shortest path problem, you need to find a path of '#' connecting the left side of the grid to the right side. All cells on the path must have the same color if we colored the grid like a chess board. Also you can't have 2 '#' beside each other, so some cells are "banned" of ever becoming '#' (because of the initial placement of '#'). After coding these constraints, it becomes simple dijkstra or 0-1 bfs.

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

after getting ac in a i accidentally submitted c in 'a' instead of 'c' but it didn't pass the first sample test would i get wa in 'a' after system testing?

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

Why is #829 and #830 on same day with only 30 minutes gap?

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

does anyone have a tricky test case for E??

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

Alice and Bob bullied me a lot today...

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

I solved B after noticing that many coders have solved it lol. Actually what I was doing earlier in intuitive way is that selecting the element with least spell which can be transferred to neighbors and then checking that element is leftmost, rightmost or at the center so that accordingly I can add spells to the ans and therefore stucked with WA, and then I realized at the last 3 min of contest that simplest way is to take n-1 min spells and thus finally able to submit it. uffff

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

I keep getting 726722623 as the answer for the fourth test case in D. Did anyone else have this issue?

My approach: In a non-ambiguous array, the $$$i$$$-th element must be divisible by the product of all prime numbers $$$\leq i$$$. The number of such candidates is equal to $$$m$$$ divided by this product (integer division, no modulo). Once the product exceeds $$$m$$$, all arrays of this size are ambiguous. The number of ambiguous arrays of size $$$i$$$ = $$$m^i - $$$ the number of non-ambiguous arrays of size $$$i$$$.

Submission: 177210359

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    ll nam = (m * (m/2)) % MOD;
    

    Doesn't it overflow?

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

      Ahhhh, I see now! Since $$$m$$$ is so huge, I pretty much need to apply the MOD on almost every calculation involving $$$m$$$. Thanks!

      I was able to AC now (but the contest is already over :( )

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

    Why is this true?
    In a non-ambiguous array, the ith element must be divisible by the product of all prime numbers <= i let say ith is 6 and element is 8. gcd(8,6) is 2 but 8 is not divisible by 3.

    array here is 1 1 1 1 1 8

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

      If there is an element 8 at index $$$\geq 3$$$, then you can keep picking the first element until 8 is at index 3. Then you can pick the 8 because $$$gcd(8, 3) = 1$$$, so this array is not ambiguous.

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

        oh i see. so any thing at ith must have gcd of everything from 2 to i not 1 and hence divisible by all the primes. Why did you have overflow problem? Wouldn't that be at max 10-15 primes before the product is larger than 10^12

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

          The overflow is because $$$m$$$ itself is as high as $$$10^{12}$$$. So even for $$$n = 2$$$, the number of non-ambiguous arrays is $$$(m * (m/2)) \% MOD$$$, but the intermediate $$$(m * m/2)$$$ already triggers overflow.

          In fact, I used binary exponentiation to calculate $$$m^i$$$ (total number of arrays of size $$$i$$$), but the multiplication for odd $$$i$$$ overflows unless I apply the $$$MOD$$$ on the base $$$m$$$ itself.

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

    Also you can check for such overflows by compiling with the flag -fsanitize=signed-integer-overflow. Helped me debug the exact same error

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

can anyone tell me their approach for problem c? I had couple of approach but none worked.I thought one with binary search,tho it was taking o(n^2) overall.

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

    It's optimal for Alice to always pick the largest valid number, while Bob always picks the smallest number. This means Bob will eliminate the smallest $$$k - 1$$$ numbers. Therefore, if Alice can win, she can win by picking only the $$$k$$$ numbers that are after the first $$$k - 1$$$ numbers in sorted order. In other words, she can pick the $$$k$$$-th number when her upper bound is 1, she can pick the $$$(k + 1)$$$-th number when her upper bound is 2, she can pick the $$$(k + 2)$$$-th number when her upper bound is 3, and so on.

    We can binary search to find the largest $$$k$$$ that fulfills this condition. My submission: 177165675

    With how small $$$n$$$ is, a simple linear check for each $$$k$$$ should work too (instead of binary searching).

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

How to solve E?

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

What is wrong in problem $$$D$$$ in this logic?

If $$$gcd(a[i],j)>1$$$ for all $$$2 \le j \le i$$$ and $$$2 \le i \le n$$$ then, the array would be unambiguous (obviously), also if $$$gcd(a[i],j)=1$$$ for some $$$2 \le j \le i$$$ the array would be ambiguous, because after $$$i-j$$$ moves by removing $$$1^{st}$$$ element, the $$$i^{th}$$$ index becomes $$$j^{th}$$$ index now, and now instead of removing the $$$1^{st}$$$ element in remaining array in $$$(i-j+1)^{th}$$$ move, I will simply remove the $$$j^{th}$$$ element.

But something is wrong as I can't seem to pass $$$4^{th}$$$ sample :(

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

    In Line 16: curr=(curr*m)%MOD; can overflow, since $$$m$$$ is so freaking huge. You should apply the MOD on $$$m$$$ first, before multiplying.

    Changing it to curr=(curr*(m % MOD))%MOD; passes the fourth test case, and will probably be Accepted.

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

How to solve D?

We know that one of the b would be an array of all 1. For something to be non-ambiguous, it must not have anything other than 1 in the b array.

My approach that ith element must be relative prime to all number from 2 to ith. Because if this is not the case, then at some point the gcd(ith, 2-i) != 1. It is just a matter of calculate how many number are possible that is less than m at ith.

How do you even do this though?

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

    Exactly man! Now I too made the same observation, now just see that since the product of first $$$12$$$ primes (upto $$$37$$$) is greater than $$$1e12$$$ $$$(m < 1e12)$$$, so any array of size > $$$37$$$ must contain an element $$$a[i]$$$ which would not be a multiple of some prime $$$p \le i$$$. So, any array of size > $$$37$$$ must be ambigious

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

    In an un-ambiguous array, the $$$i^{th}$$$ element must have $$$gcd>1$$$ with all $$$2\leq j\leq i$$$. This means it should be divisible by all primes $$$\leq i$$$*. The count of values $$$\leq m$$$ that are divisible by all primes $$$\leq i$$$ is $$$\lfloor \dfrac{m}{\prod_{j=1}^{j=i}{j\cdot isPrime(j)}}\rfloor$$$.

    *Why the $$$i^{th}$$$ element should be divisible by all primes $$$\leq i$$$: In an un-ambiguous removal sequence, the $$$i^{th}$$$ element's position will decrease by $$$1$$$ after each removal. So, it will hit all the prime positions $$$\leq i$$$, and any composite position $$$\leq i$$$ is just a combination of primes $$$\leq i$$$.

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

      How to proof the conclusion in the last part?Is it a theorem or something else?

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

        Which conclusion exactly?

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

          "The count of values ≤m that are divisible by all primes ≤i is ⌊m∏j=ij=1j⋅isPrime(j)⌋"

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

            For any value to be divisible by all the primes $$$\leq i$$$ it has to be divisible by their product ($$$prod=\prod_{j=1}^{j=i}{j\cdot isPrime(j)}$$$). These values are: $$$prod, 2\cdot prod, 3\cdot prod, ..., k\cdot prod$$$, where $$$k$$$ is the maximum integer such that $$$k\cdot prod\leq m$$$. So, $$$k=\lfloor \dfrac{m}{prod}\rfloor$$$

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

            There is nothing to prove bro.

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

The $$$u=v$$$ case of problem F is very similar to Sprinkler from JOI Spring Camp 2022. Dealing with $$$u \neq v$$$ is pretty easy.

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

Almost solveD...
Just avoid overflow issue and now get passed. Feel sad...

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

I have a two pointers solution for B here.

I'm not sure if it works 100% of the time as edu round pretests are usually weak. Can anyone try and hack it?

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

    keep the largest b value greedy. ur right

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

Problem C can be solved in O(n*logn*logn) with binary search + multiset. Why were the constraints kept low for this problem? Even a O(n^3) solution will pass.

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

I see many solutions of D calculating LCM directly. Idk how lcm is not overflowing. I was thinking of same approach but I thought lcm will overflow.

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

    we will calculate it until lcm<=m (m<=1e12) .if lcm>m there will always be ambigous solution.

    so there wont be overflow

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

Anyone else overcomplicate B?

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

According to me , in problem B the testcase given below should have answer 244 but the correct answer is 242. Can anyone please explain why?

1
7
1 50 10 100 10 50 1
1 5 2 7 5 6 1

Also when we remove an element do we have to add its strength to both of its neighbors or just one of them?

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

    You add to both neighbors if it has two neighbors. Also, to get 242, u remove the left 3 then remove the right 3 and then remove middle.

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

    remove the elements in this order 7 5 6 1 2 3 4

    you will get 242

    we should add its strength to both neighbors

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

    The answer is the sum of all $$$a[i]$$$ and $$$b[i]$$$ minus the largest $$$b[i]$$$.

    This is because you can always kill an enemy who is currently at either the left end or the right end, so the $$$b[i]$$$ gets added only to one enemy, and never to two enemies. The last enemy you kill will not have their $$$b[i]$$$ added, so the optimal choice is for the maximum $$$b[i]$$$ to be the last enemy to kill.

    So one solution here is to kill the first three from left to right (each $$$b[i]$$$ gets added to only one enemy), then the last three from right to left (again, only added to one enemy), and then finally kill the remaining element (which has the maximum $$$b[i]$$$, but it is not added to anyone's health, due to being killed last).

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

My head hurts after getting WA 5 times in a row on C

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

D is too easy for its position.

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

Nice A And B is also nice but not as good as A

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

    Was A really a good problem? All you had to check was n == m.

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

      Really good.

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

      Yes, it's a good problem imo. It's not an arbitrarily contrived scenario, nor is it a trivial problem (it may not be immediately obvious as to why $$$n != m$$$ suffices). The simplicity of the solution only makes it better.

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

How to solve problem D I was only able to come across observation that For an array to be not ambiguous It's Ith element must not be divisible by 2,3,...i for all I >= 2 (1 based indexing) How to approach this question further I am goota stuck here New methods are also appreciated Thanks in advance

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

    You are pretty close. Just think about is there any array with zero or one removal sequence?

    At least two is equivalent to excluding zero and one.

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

Plese help me To become lowest contributor in codeforces history

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

Can someone explain D ??

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

    Copied from my other post:

    D. Counting Arrays

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

      Thank u

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

      can you explain how you are calculating the

      number of k from 1 ... m for an i such that , GCD(k, p: p | i) > 1

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

177174924 do this one is ok?

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

I got 66th place (and 18th for rated participants); pretty good!

My solutions (video):

A. Cowardly Rooks

Solution

B. Death's Blessing

Solution

C. Number Game

Solution

D. Counting Arrays

Solution

E. Cactus Wall

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

For Problem B, the constraint on a is (1 <= a <= 10^9) but in the pre test 3 Test case 13 one of the input is 2453494488, this is not expeted right 1749B - Death's Blessing 177245405. Can anyone confirm is this fine

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

    That's a number you're outputting; it's not from the input.

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

      No a and b are array inputs for this problem. If you see my attached submission i tried to print that input to verify if it's below 10^9.

»
17 months ago, # |
  Vote: I like it -62 Vote: I do not like it

I FUCK EDUCATIONAL ROUND. Educational Codeforces Round 138 [Rated for Div. 2] was the worst match I've ever seen.Fuck you....................................

»
17 months ago, # |
Rev. 3   Vote: I like it -27 Vote: I do not like it

Sorry for posting such lenghty code instead of a link.

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

    Never post code like this way. You should use link of the code.

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

Waste almost 30mins to solve Problem D just because of OVERFLOW. XD

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

Nice !

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

Can anyone please tell what is be wrong with this solution 177255794? I have tried to make sure that overflow doesn't occur anywhere, but still for the large test cases, I am getting a different output.

Edit: nvm, found my mistake

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

I don't know why people still don't use templates for modints. This can help you avoid adding additional logic for overflow and makes code look a lot cleaner. And for taking inverse you can just put a simple division operand and it will handle everything. Code and usage is in spoiler

Modint template(which I took from someone whose name I don't remember)
»
17 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem E is easy if you solved this recent Indian ICPC problem.

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

When will system test start?

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

when will the editorial be updated ?

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

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

In question number Everyone approach is Sum(health)+sum(strength)-max(strength) But it fails on test case 4 2 6 7 3 3 6 1 5 its correct ouput is 28 But its outout from this approach is 27

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

    are you sure????

    It is the correct solution.

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

      Yes I am sure 2 6 7 3 3 6 1 5 You can check by doing dry run

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

        2 6 7 3 3 6 1 5

        +2

        9 7 3 6 1 5

        +3

        9 12 6 1

        +12

        10 6

        +10

        =27

        Why not 27? You sure what? Lmao

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

        just wait for the editorial and try to understand why the solution is like that.

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

          I understand Sir...We have take only boundaries values so that sum can be minimize

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

            then why don't just simulate this solution in your testcase?

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

Ratings updated preliminary. Unfortunately Mike won't be in touch until Monday, so cheaters will be removed later.

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

Problem A does not require rook positions [Lol] [Lol]

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

Please provide editorials....asap

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

Where's the editorial? Please post it as soon as possible.

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

Thanks for the contest! I really enjoyed upsolving(I had school when it was held T_T).

I think c,d are interesting and I like solving e a lot(even though I completely bricked it for the first 1 hour i spent solving it :P)

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

EDIT: Please disregard the comment. This is due to an issue in the way I printed the test.

There is potentially an issue in the tests of https://codeforces.com/contest/1749/problem/E It seems like the case 17 of the test 2 violates the constraint of no side adjacent cacti in the grid. However, in the statement it states that the initial state satisfies the constraint. Following is the test case. Am I missing something?

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

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

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

Never give up :)

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

    Grats to you for finding out that upper_bound is essentially the same with lower_bound with a very small value added. You tried to fool the plagiarism test by swapping out one function and making the indents a big mess. Good try, but I think you failed.

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

      UPD (Yes, it had to be a separate comment): Thank you, comment OP, for trying to conceal your sins and making me look like a motherfucker. Thank you very much.