Igor_Parfenov's blog

Codeforces Round #868 (Div.2)
By Igor_Parfenov, history, 12 months ago, In English

Hello!

On Apr/27/2023 17:35 (Moscow time) we will host Codeforces Round 868 (Div. 2).

The problems were written and prepared by Igor_Parfenov.

I would like to thank everyone who made this round possible:

This round will be rated for participants with rating lower than 2100.

You will have 2 hours to solve 6 problems.

Score distribution: 500 — 1000 — 1250 — 2000 — 2000 — 2500.

Good luck!

UPD: Editorial

UPD: Congratulations to the Winners!

Div.2:

  1. Low-Deny-Cup

  2. psz6

  3. BULBULBUL

  4. Epyset

  5. chenguoyi

Div.1 + Div.2:

  1. SSRS_

  2. maspy

  3. Rubikun

  4. heno239

  5. Crystally

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

Comments Comments (180)
| Write comment?
»
12 months ago, # |
  Vote: I like it +99 Vote: I do not like it

As a tester, Igor_Parfenov did his best to make sure the round is balanced and interesting. Hope you enjoy.

→ Reply
»
12 months ago, # |
  Vote: I like it +40 Vote: I do not like it

As a tester, I shall farm contribution.

PS: Hope you like the round and wish you positive rating :D

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +187 Vote: I do not like it

As a tester, I would recommend that you don't name yourself purp4ever, thinking that you'll be a Dominater069 of the candidates and then become an expert because your friends FzArK and MaherSefo will say awoo and make fun of ywooo. Then you would eat Shawerma out of sadness.

I know this is madlogic

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +154 Vote: I do not like it

    As a first-time tester, I am jealous of purp4ever's as a tester skills as I can't come up with such as a tester comment (

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    Probably the GOAT of as a tester comments?

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +130 Vote: I do not like it

    As a tester, I can't come up with any as a tester comment to post after reading this...

    ;(
    → Reply
»
12 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Thank you

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

Probably the shortest codeforces round announcement blog i have seen in a while

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

Edit: My bad I apparently can't calculate dates correctly.

→ Reply
»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I am unrated as I joined codeforces few days ago . I am thinking of participating in this contest . So Will I get rated after competing in this contest , or there are some conditions like you have to participate in 4-5 contests to get rated ? Please do answer .. It might be helpful for other new participants as well .

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Yes, you will get rated after participating in your first contest. All the best!

    → Reply
»
12 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Hope the problem statements would be as small as the blog :)

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    Yes, Plz stop making IELTS reading tests on CF, this decreases your social credit!!!

    → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +74 Vote: I do not like it

I couldn't come up with as a tester comment, that's why I don't have the right to write as a tester at the beginning of my comment.

→ Reply
»
12 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Igor_Parfenov Orz

→ Reply
»
12 months ago, # |
  Vote: I like it +100 Vote: I do not like it

As a Green tester,

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

good luck

→ Reply
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

As a gray participant, i'm not sure

→ Reply
»
12 months ago, # |
  Vote: I like it +2 Vote: I do not like it

A very streamlined competition announcement

→ Reply
»
12 months ago, # |
  Vote: I like it -45 Vote: I do not like it

"I would like to thank everyone who made this round possible"

"who" should be "that"

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

    Wrong. In English the relative pronoun "who" is used when referring to people and "that" is used when referring to things.

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

i wish to be pupil after this contest

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

now there are a problem in the server, all submissions stack in the queue, please fix it we do not want unrated contest

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

score distribution?

→ Reply
»
12 months ago, # |
  Vote: I like it +9 Vote: I do not like it

How far is purple?

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

There are so many submission still in queue, I'm really worried about getting stuck in the contest tonight.

→ Reply
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Good Luck for all participants

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

The difference between C and D is massive.

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

    See it this way:- D and E are of same points.

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

How far is gray?

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

I will be a pupil in this night! Good Luck for everyone.

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

madlogic wrote As a tester, Igor_Parfenov did his best to make sure the round is balanced and interesting. Is this contest really balanced after this score distibution?

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

    We'll see

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

    Spoiler alert, it wasn't

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      NOT BALANCED ROUND AT ALL...

      Since D and E are same points, I was hoping they would be of same difficulties. They are not... I started with E problem wasted more than 1 hour on that.

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

        Have you solved D? If not, what leads you to believe it's easier than E?

        I skipped D after a few minutes because I had no ideas on how to solve it, and was able to solve E.

        → Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope no queueforces

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

I wish to become an expert after this contest, please say good luck to me, thanks.

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

I wish to become an expert after this contest.

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

Do I get some penalty for Unsuccessful hacking attempt?

Do I get some reward for Successful hacking attempt?

→ Reply
»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Is it me or anyone else also feels that this contest was a bit tough?

A was a bit tough than usual?

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

    and it reduced the number of participants

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

      Number of registrations were also low. It was around 15k only.

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

    Yes i also felt that A was tough.

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

      guess you tried to solve a univariate quadratic equation. actually you can just enumerate the number of $$$1$$$ because $$$n$$$ is quite small.

      → Reply
»
12 months ago, # |
  Vote: I like it +34 Vote: I do not like it

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    Your submission time between problem A and problem B is suspicious. Did you wait to submit both problem at the same time

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

    What's even funnier about this meme here is that the standard approach to solving D involves abusing a repeating sequence of "abc" (with runs of unique letters sprinkled in between).

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

I will probably miss the chance of becoming CM because blind me couldn't see 1e7 * 1e7 * .... * 1e7(1000 times) isn't 1e10

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

    How did I do this exact same mistake lol

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

      Guess it's been too long since we last multiplied

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

        I think it's not good to comment this 15 minutes before the contest ends as others might doing the same mistake.

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

          Yeah sorry my bad... It just completely slipped out of my mind!

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

    This mistake costed me a lot of time :(

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

    contest is running bruh :/

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

      F my bad... but I doubt it'll help anyone since I didn't mention any question or something

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

    same

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

    but i didnt do that mistake and feeling top of the sky

    → Reply
»
12 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Thank you for 5 math tasks and constructive D

→ Reply
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For me, A was tougher than B and C.

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

    Me too

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

    Yep the key Idea for A is harder to catch than it is for B & C, B was simplified because of it being a permutation but still sad contest :(

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

Fantastic problem E. (Hint Sprague-Grandy function)

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

    How did you find the sprague-grundy function ? I think there are edge-cases with l = 1 but i'm not sure ...

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

      There are two different grundy values you need to calculate.

      The first one is the initial condition (it's a cycle), so it will become a single path. The second one is a path, it can be divided into two paths.

      Bruteforce them, and you will get a really nice table.

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

Submission to E Can somebody check where I got wrong? Wrong answer on test case 9

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Am i true that it is Sprague-Grandy function? Mine was:

    $$$sg[i] = 0$$$

    when i < l

    $$$sg[i] = i // l$$$

    when l<= i <=r+l-1

    $$$sg[i] = 0$$$

    when r+l<=i

    Taking %(r+l) yours solution becomes wrong. This pattern is easy to find if you look at the first for example 1000 sg[i], for O(n^2)

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

      Yeah, that is the Sprague-Grandy fucntion

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

      The explicit i < l case is not necessary

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

        Of course Yes, i see it only after AC submission:)

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

    Take a look at Ticket 16853 from CF Stress for a counter example.

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

      Alice goes first, takes 1 out. Now Bob is left with {2,3,4}, if he removes one of them say 2, then Alice has got {3,4} which he removes in one go and wins. If Bob removes two of them say 2 and 3, then Alice has got {4}, removes at once and wins. Feeling dumb, what's wrong.

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

        You're almost there. After Alice removes vertex 1, we have an L shaped graph. What happens when Bob removes the connecting point of both the perpendicular lines. Would that break the graph and force Alice to pick exactly 1 vertex in the next move?

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

          Right. Missed that case, thanks for the effort!

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

I kept getting TLE on C, probably some stupid mistake, can someone give a brief solution of C?

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

    You are creating an array of size $$$si$$$ each test case, you could just use std::map.

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

Please explain D

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    one thing to know that, n length string can produce max n palindrome.Now suppose u need 3 palindrome on a segment, then can simply print aaa.. you have to just maintain no different segment disturb others.. so take 1st 3 char abc and when you don't need more palindrome on that segment use abc cyclicly nullify extra one.

    suppose on a segment, need 4 palindrome in 10 length string then u can print:
    abc c abcab [3rd part for nullify]

    And when x[i]<c[i] No [x[i] len string can make max x[i] palindrome]
    also (x[i]-x[i-1])<(c[i]-c[i-1]) No [for same reason]

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

      adding to this, use new character for every query. There are max 20 queries, so we can use all 26 letters of alphabet. To create new palindromes, use new character, to not create new ones, use the used ones. This can be done in O(n) time.

      → Reply
»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I was solving quadratic equation for A without seeing n <= 100 !!!

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

    O(n) was not intended?

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

    I learnt to read constraints carefully in this contest :( they can cost so much time.

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

Can anyone explain the logic behind C

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 6   Vote: I like it 0 Vote: I do not like it

    We want the product of ai ... an to be equal to bi ... bn, Therefore their total prime factorisation should be the same (the prime factorisation of the product from ai to an). So we can keep track of the total prime factorisation (and the counts of each prime factor) of ai to an.

    We also realise that p^2 where p is prime, is a strongly composite number. This is because the factorisation will then be [1, p, p^2] which is valid. Therefore it would be best to form p^2, p^2, p^2 for every prime factor in your total prime factorisation.

    Now we have leftover primes, we realise again that prime * prime * prime will give you a strongly composite number. This is because the factorisation will be [1, p, q, r, pq, pr, qr, pqr], which is valid. Therefore we can group the leftover primes by groups of 3

    The answer will then be:

    1. ans += each prime factor count // 2
    2. leftovers += each prime factor count % 2
    3. Then after step 1 and 2, ans += leftovers // 3

    If anyone has any alternative solutions please feel free to share! I'd like to learn as well :)

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

    C is too easy question. Bad constraints.

    My logic:

    You have to find the prime factorization of the product of the array. But constraints are bad; finding a product will give TLE. The logic is simple. It is guaranteed that p^2, pqr is composite (here p,q,r is prime) so p^k will add total+=k/2 in the answer, and res+= k%2 will correspond to pqr type number. Therefore, the answer will be total(since directed composite) + res/3. Since 3 numbers are required to form pqr res/3 will be added to answer. Prime factorization finding can be done easily using this method

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

    The product of all the integers in the given array is same as the product of all possible prime factors, so the condition for product is already satisfied if you break each integer into prime factor. Now to find the integers of array B(i.e strongly composite numbers) you can see that if any prime factor raised to the power 2 will always be a strongly composite number, so the necessary condition is finding prime factors that have power >= 2, now since you only require minimum (2 prime integers to make them strongly composite) you can utilize the remaining ones to help make the prime integers that aren't strongly composite i.e they exist individually. To make a strongly composite number out of different prime factors you require atleast 3 of them(like 3, 5, 7 can together form a strongly composite number). So all that if left to do is to count the prime factors % 2 and then use them later on in pairs of 3 to form a strongly composite number. Here's my way of doing it: https://mirror.codeforces.com/contest/1823/submission/203710826

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

    Thanks everyone, I was able to find out that p*p*p = strongly composite and that p^2 = strongly composite in the contest but forgot that every number has a set of prime factors I can break them down into, just upsolved :)

    → Reply
»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Great contest, just incase someone is still struggling with Problem A, Problem B or Problem C, You can view the self made video editorial here — video solution

→ Reply
»
12 months ago, # |
  Vote: I like it +30 Vote: I do not like it

E is really close to this https://atcoder.jp/contests/abc297/tasks/abc297_g

also D you can get it with some search https://math.stackexchange.com/questions/1926549/number-of-distinct-palindromic-sub-strings-of-a-string

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

    :(

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I think in E similarity is very surface level: statement and code are kind of similar, but actual sulutions are completely different

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

      mehhhh, I can agree kind of the same procedure of solving thou don't you think also f(x) is really close

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

        Yea the function is almost the same

        Don't know about you, but in AtCoder problem I just thought about how mex on subsegment changes, and in E the main idea is that if $$$len \geq l + r$$$, then you don't need to think about mex at all, and the idea that otherwise answer is $$$\frac{len}{l}$$$ isn't the hardest part of the problem

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

      I think it depends on how you solve it. If you do not attempt to prove it, but believe in the patterns you see, you can write slow polynomial brute force, print tables for the grundy values for different values of $$$l,r$$$, find a pattern and submit it.

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

    E: I converted the problem into pile. and search on google. but how i missed this.

    How do you search? can you learn me the tricks (: -_-

    → Reply
»
12 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Screencast with commentary

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

Struggle is real. I was standing at 2450 rank and after resubmitting the same code i got a rank of 3800 just wow.

codeforces rul..

→ Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts.

i found out after i submitted another solution in the last minute just to try!

→ Reply
»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

welp, RIP those of us who got cute/lazy with C and FST/TLE :P

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

Feels like the third rated contest in a row i got D within minutes of the contest ending (cus of some if i forgot), feeling cursed

→ Reply
»
12 months ago, # |
← Rev. 4   Vote: I like it +41 Vote: I do not like it

A: Let there are i occurences of 1 and n-i occurences of -1, then k=i*(i-1)/2+(n-i)*(n-i-1)/2. Since n is small we can find i by brute force.

B: Let's classify indexes by i%k, then we can swap any 2 elements with adjacent indexes in the same class, so we can rearrange elements in the same class arbitrarily. Therefore, if for all i p[i]%k=i%k holds, we can sort the permutaion directly; if for at most 2 indexes p[i]%k!=i%k, we can use the preliminary exchange for them and sort the permutation.

C: We can see that "weakly composite" numbers are product of 2 different primes.

Proof

To solve the problem, first we need to find prime factorization of prod(a[i]) by prime sieve, assume prod(a[i])=prod(p[j]^r[j]), then we check for the array r[j]. If we need to get a strongly composite number, we need a square factor or 3 different prime factors. Therefore, if max(r[j])==1 and size(r)<=2, there's no solution. Otherwise, the answer is sum(floor(r[j]/2))+floor(sum(r[j]%2)/3), first part for numbers with square factor and second part for numbers with 3 different factors.

D: First, we have p(s, m+1)<=p(s, m)+1.

Proof

Therefore, if c[1]>x[1] or c[i]-c[i-1]>x[i]-x[i-1] there's no solution. Otherwise, we can construct a solution: First let s[1, 3]="abc", then p(s, 3)=3. Then we denote d[1]=c[1]-3, d[i]=c[i]-c[i-1] is the number of extra palindromes we need to create at position x[i]. Then for each i, we let s[j]=(char)('c'+i) for j in range [x[i]-d[i]+1, x[i]]. So we fill the first range by "ddddd...", second range by "eeeee..." and so on. Each range will create new palindrome equal to its size. By the condition that c[1]<=x[1], c[i]-c[i-1]<=x[i]-x[i-1] and 3<=c[1]<=c[2]<=...<=c[k] these ranges don't overlap, and by the constraint k<=20 we have 'c'+i<='z'. Finally, for all indexes i that s[i] is undetermined, we fill them by 'a', 'b', 'c' alternately, since there are no palindrome other than "a", "b", "c" in "abcabcabcabc...", they will not create any new palindrome.

E: We solve the problem by Sprague-Grundy theorem. Let's denote sg[i] as the SG number of situation of a single cycle with size i, then if i < l or i >= r+l, we have sg[i]=0, otherwise sg[i]=floor(i/l). I have idea to prove it but it's too complicated.

F: Let's forget everything of probability, and construct a path with following properties:

-Start at s, end at t.

-For each node i, the number of occurences of (i-->j) in this path is the same for every adjacent node j. We denote this number as dp[i].

Then we can get the answer by this path. Let t be the root of the tree and j be the parent of i, then the transition is dp[t]=0, dp[i]=dp[j]+1 if node i is on the simple path from s to t, dp[i]=dp[j] otherwise. That's because if i on the simple path from s to t, the number of occurences of (i-->j) will be one more than occurences of (j-->i). Finally, we have ans[i]=sum(dp[j]) if i!=s, ans[s]=sum(dp[j])+1, where sum is over all adjacent node j of i.

→ Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D and E should not have same score.

→ Reply
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem C is the most beautiful problem i ever seen

→ Reply
»
12 months ago, # |
  Vote: I like it +39 Vote: I do not like it

The implementation of the special judge of Problem D seems much more difficult than the solution.

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

    Yeah, my guess is they planned on asking if a certain string satisfied those conditions, but made the problem easier by only asking for a construction.

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

      I think it is easily possible to check a valid answer by using palindromic tree.

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

    Yeah when I was doing D I wondered how they are going to test it. How can we do better than O(n2)?

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

      Fastest way is probably Palindromic Tree. But it can be done with hashing in O(nlogn), by abusing fact that there can be at most 'n' unique palindromic substrings of any string of size 'n'.

      Core idea of this approach, is to consider the longest palindromes centered upon each index. For each such palindrome, insert its hash into a set and trim its outermost characters; repeat the process for each trimmed palindrome until it coincides with some palindrome in the set. The size of the set will be the answer.

      I guess it can technically be reduced to O(n) if you use unordered_set and Manacher's algorithm.

      → Reply
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't know why my performance is declining day by day :(

→ Reply
»
12 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Problem E is identical to this problem

→ Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    They're actually not the same. In problem E you can (after two removals) break a connected component into two separate components. You cannot do this in G. Constrained Nim 2. But it happens to be that the solutions are almost the same.

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

MLE on C :/

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

    Are you precomputing the prime factors? Also, use int instead of long long for this Q coz constraints allow it.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I was using long long, this was my code, ik i have to use sieve but got mle on pretest 1 which was weird.And yes I was gonna precompute. I know i've overcomplicated it but getting mle on pretest 1 is still weird to me.

      Edit: code still mle after precomputation

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

Hey, I solved C fair and square. I had almost one hour left, and I also refreshed in between to see for changes. How can they change the constraints after the contest, not at all fair. If I got tle before I would have corrected it with one penalty, but now my rank dropped from 2k something to 4k. I am not at all happy with this behavior.

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

    You didn't get TLE during the contest because your code was only run on pretests. The set of pretests doesn't contain all tests and passing them does not gurantee that the solution passes the full set of system tests. No constraints were changed after the contest. You just got unlucky that your code had a mistake that wasn't covered by pretests.

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

      his code didnt have mistakes , its just that you cant possibly say its ok to run a for till 1e7 1000 times . It was kinda obivious that it would get tle

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

        Did I word that badly? I guess I should've said that they had a mistake in their approach, not the code. But that's not the point of the comment, I just told them why their code changed from AC to TLE.

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

        Actually no, it runs till that last prime factor which is greater than sqrt(a[i]). Only one condition needed to be put instead of letting c increment till that last factor, we can just take the remaining value of a[i] after it reaches sqrt(a[i]). So that was the only mistake. Still it was nothing major and I could have corrected it instantly with only one penalty.

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

    :(

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

I have a question, why isn't this submission giving me runtime error? (On line 43). https://mirror.codeforces.com/contest/1823/submission/203713818 Would have solved it during contest if it did.

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

    The loop should go upto $$$k$$$, not $$$n$$$.

    UPD: Sorry, misread.

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

      I know that. I am interested in why it isn't giving me runtime error.

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

a great contest but if the problem D were easier the contest would be more interesting and balanced

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

Can anyone explain why is this give wa? https://mirror.codeforces.com/contest/1823/submission/203738224

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

Are there any special prerequisites needed to solve today's E?

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

    Game theory, as mentioned in the editorial.

    → Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

D was a very fun problem for me (even though i found A-C a bit boring), thanks!

gonna get to e tmr but i have an ap test monday XD and i must study

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

In problem C editorial: "...Since m is the number of di >= 2, then D >= 2^m..." can someone explain how it became D >= 2^m?

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Right now it doesn't allow to make any submissions, it shows "Unexpected error". What happened?

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

    Facing the same issue when trying to submit older problems...

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

      It would not depend on the problem you are trying to submit — it is a general issue with the platform.

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

    Now it looks like the queue is stuck.

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

Good Luck for all participants

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

Hello,

my submission 203696670 of the problem C (Strongly Composite) has been flagged as a rule violation because of it's similarities to the solutions of Aku30, stark_tony_, ek3ru8m4 and dmenezes with ids 203691212, 203691644, 203694434 and 203695366.

This is because all five of us decided to speed up factorization with a list of all prime numbers from 2 to about 3137. This list is obviously the same for each of us, as we all included the numbers in ascending order. I probaly don't need to mention this, but a list of these prime numbers has been published before the contest.

I would therefore like to appeal my disqualification, along with the disqualification of Aku30, stark_tony_, ek3ru8m4 and dmenezes, as I feel it was unjustified.

Thank you for your consideration.

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

    The only thing common among all of our codes is the list of prime numbers rest is completely different, and you can also notice the range of prime numbers taken into consideration varies with person. Therefore, along with the other participants mentioned above I would like to appeal my disqualification.

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

Hello, my submission of Problem C 203692110 significantly coincides with the submission of arbalestOvO / [submission:203688479]。In our submissions, we coincidentally use the pallard-rho algorithm to decompose prime factors, and this code implementation has been made public by others before the competition. Here is the link to the code: (https://judge.yosupo.jp/submission/82101). I would therefore like to appeal my disqualification. Thank you for your consideration.

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

Broo.can anyone please say why i am getting tle for palindrome question-D. i am not able to find the fault.(https://mirror.codeforces.com/contest/1823/submission/208179126)

→ Reply