diskoteka's blog

Codeforces Round #867 (Div.3)
By diskoteka, 20 months ago, translation, In English

Hello! Codeforces Round 867 (Div. 3) will start at Apr/24/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, and Vladosiya for coordination of our work. Problems have been created and written by: diskoteka, pavlekn, playerr17, isosto.

We would like to thank: pashka, purplesyringa, Alexdat2000, I.Gleb, Serik2003, TkachDan, maksimb2008, _--, 74TrAkToR, Gornak40, ut-k8g, Rudro25, Jostic11, yorky, tolbi, AhmetKaan, Splatjov, BF_OF_Priety, vrintle, KoT_OsKaR for testing the contest and valuable feedback.

Good luck!

UPD: Editorial

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

Comments Comments (191)
| Write comment?
»
20 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Problem A: find missing space

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

Really excited for this contest. Don't know why.(◠‿◠)

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

as a tester, I can assure that problemset is perfectly balanced , all problems are interesting and I recommend to read all the problems

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

As a participant, I will appreciate the work of authors and testers. Thank you for the contest!

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

As a !non-Tester, I tried to solve problems and give proper feedback. glhf

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

As an author, I wish all <1600 participants getting their free expert this round!

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

    practically and theoretically not possible

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

      :D

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

        Bro, That's surely a joke. No need to take everything serious in life. Chill out and enjoy every bit of it.

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

          :D :D :D From the downvotes, I think you're right.

          Lesson learned: Laugh at every nonsense on codeforces

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

            Don't think because of downvotes. I mean in general you should be not be serious all the time. It's not related just to codeforces. It applies to your daily life activities too. Just be chill and not serious all the time.

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

              1) You are saying not to take things seriously. but your username(handle) tells different story.

              2) I am 90 % sure, your spelling for LOSER is wrong.

              xD

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

this is gonna be my first contest! wahoo!

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

As a participant, I will achieve a 4 long streak of losing rating in div3

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

it's not related to this blog :

can some one give me the list or easy to medium problems for DP to kickstart my learning ( like any difficulty wise or something ) for beginner level to medium and you can share any resources or suggestions ....

Thanks in advance!

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

Really excited for this contest. Looking forward to becoming a pupil soon:)

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

How can we be a tester? Plz don't downvote.

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

As a non tester....... how to be tester? (I thought only purple+ can test).

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

hope to become an expert

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

Give me contribution

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

How to hack a solution during contest?

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

    You can't in div3 or edu rounds. They have their seperate period of time for hacking after the contest.

    But for Div2 you can try that. Just lock the problems and go to room section. And start watching other people solution if you found some counter-testcase hack it.

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

    When the contest ends in some of them there is a phase called: The Open Breaking Phase. And it is in this phase that you must enter someone's solution and press the "Hack!" Soon you are given a choice on how you will hack: with a generator or a manual hack? For the generator you write the code for the test. For a manual one, you write the test by hand. But you can't hack during the contest, only after it.

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

yayyy my first contest!! let's so how it goes

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

    Welcome to the community on the behalf of specialist community Sir. Hope you have great time and learning.

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

Please provide hints and proofs for the problems along with editorials

It helps in upsolving and understanding concepts for beginners instead of directly jumping to solutions :)

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

This is my first round in Codeforces. I really want to get more ratings.

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

hoping for 160 + Delta. feels like mission impossible... xD

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

I'll try my best, wish me luck

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

glhf

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

Hope everyone after this contest will change color:)

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

    *positive change

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

      sure, Did you have a good contest?

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

        yes :), wbu?

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

          I have AC A,B,C,D . A good contest :)

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

            congrats! 1st account?

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

              Thank you! I have an another account but its performance is not good so I use unrated account :) And, how about you? How many problems did you accepted? (and Why can you go to Specialist :))

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

                Ohh good to hear. Yesterday, mine 1st 6 questions were accepted :). I got to specialist because I practice C questions a lot :)

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

I've participated in more than 5 rated contests and my rating is <1900 why I'm not in the official standings table?

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

    This is a div 3 contest which is rated only for accounts having less than 1600 rating.Your rating is greater than 1600,so you're not an official participant.

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

      The blog mentioned 1900, right? 2nd bullet in 5th paragraph?

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

        That just mean that your are a trusted participant

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

        You are a participant of the third division if and only if you currently have rating less than 1600. This can be seen in the fact that only < 1600 rated participants are rated in a Div.3 contest.

        If you are a trusted participant of the third division, it is assumed that you must be a participant of the third division (i.e. have rating < 1600). The two constraints are extra for determining if you show up on the official leaderboard.

        Here "do not have a point of 1900 or higher in the rating" means that if you have reached 1900 rating and then dropped back to < 1600 rating, you will not be considered a trusted participant of the third division and you will not show up on the official leaderboard. But the contest will be rated for you.

        You are not a participant of the third division; thus you don't show up on the official leaderboard.

        I agree that the wording is quite unclear.

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

is there anyone else who did not read the problem C properly and just guessed the solution from sample test cases?

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

did g and f leak? Sudden increase in submissions for both

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

When can you submit in practice?

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

How to do G2?

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

    Trick : number of factors of a number (10^9) that are perfect squares is less than 100

    Somehow iterate over those factors...

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

    $$$a[i] \cdot b \cdot b=a[k]$$$

    if $$$a[i] \leq b$$$ then $$$a[i]^3 \leq a[k]$$$

    if $$$a[i] > b$$$ then $$$b^3 \leq a[k]$$$

    So you can solve problem in $$$O(N \cdot M^\frac{1}{3} \cdot logN)$$$

    My solution works ~1200 ms.

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

    You need no fancy algorithms. Casework on if the common ratio is greater than the first term. For each $$$a_i$$$, enumerate the common ratio from $$$2$$$ to $$$(a_i)^{\frac{1}{3}}$$$ to count the number of triples where the common ratio is less than the first term where $$$a_i$$$ is the greatest term, and then if $$$a_i\le 10^6$$$, enumerate the first term from $$$1$$$ to (and excluding) $$$(a_i)^{\frac{1}{2}}$$$ to count the number of triples where the common ratio is greater than the first term and $$$a_i$$$ is the middle term. Remember to add the case of three equal terms.

    This runs in $$$O(MAX^{\frac{1}{3}}n)$$$ using a custom hash unordered map. Implementation at https://mirror.codeforces.com/contest/1822/submission/203344438

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

      Can u elaborate more on your explanation? I didn't get the common ratio part

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

        My bad, the common ratio refers to $$$b$$$.

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

Thanks a ton for such a contest. Getting to Expert in style :)

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

Is G2 based on the fact like finding all unique GPs of common ratio upto 30 then doing some trick(no idea) to find GPs of ratio greater than 30 also using the GPs of common ratio upto 30?

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

Div.3: The contest where you can literally ask WolframAlpha to solve C, without reading description at all

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

Finally Expert this time.

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

Such a great contest, really loved it, Problem F was the nicest and cute problem!

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

    Thanks! We are glad that you enjoyed the contest!

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

As a pupil I'm becoming a newbie

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

What was the logic in problem C? I guessed from the test cases.

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

    for D also, I found the pattern, but couldn't solve it

    Am I becoming a pattern recognition model?
    → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same i just copy pasted from oeis.

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

    For C, I saw that:

    • There are 4 edges with length $$$n$$$, which are the edges of the square as well.

    • In the square, the length of each adjacency edges is decrease from $$$n - 1$$$ to 1, and $$$n - 2$$$ to 1.

    • In the middle, there is an edge with length 1.

    In conclusion, the formula I used without simplifying is: $$$4 * n + sum(n - 1) + sum(n - 2) + 1$$$ (Note that $$$sum(k)$$$ is the sum of the sequence from 1 to k).

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

    n * (n + 1) + n + 2 I reached at this after a lot of rough work but its sad to see people directly guessed the test cases or used WolframAlpha/Oesis to guess the pattern.

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

      Personally I also used WolframAlpha, because I didn't remember how to solve recurrence relations. I think this is a weakness of CodeForces, maybe especially in the lower ranks: a lot of problems are really math problems more than coding problems.

      Incidentally, the problem could also be solved by brute-force without finding a closed-form solution.

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

        it seems to me it gets compiler optimized, because otherwise this would be O(max) which is too high.

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

          The compiler has optimized it somewhat (in a pretty impressive way actually) but it has not eliminated the loop, so it is still O(max). You can see the optimized code here: https://gcc.godbolt.org/z/K413jocrE

          The inner loop is still present but it's very compact:

          .loop:
        add     rdx, rax
        add     rax, 2
        cmp     rax, rcx
        jne     .loop

          This is fast enough to do a billion iterations in 3 seconds on a reasonably modern CPU.

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

      Is wolframalpha a math formula solver website? And Oesis is for finding sequences?

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

        OEIS is the Online Encyclopedia of Integer Sequences: https://oeis.org/

        Wolfram Alpha is a solver for mathematical functions in a very broad sense. For this problem you could feed it 26 + sum x=5..n (2x + 1) or f(4) = 26, f(n) = f(n - 1) + 2n + 1 and it would calculate a closed-form expression for you.

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

I saw problem E before in codechef but with minimum difference prob

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

Why TLE?

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

    There are two problems here:

    1. a check like mp[v[j]*r] > 0 is relatively costly because it will insert an element into the map if it didn't exist before. It would be better to use map::count() or map::find() to check if an entry is present without modifying the map contents.

    2. you should probably break out of the inner loop when v[j]*r*r is larger than the maximum value in v, otherwise you end up doing 1000×N = 100 million iterations in the worst case.

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

      AC Thanks A Lot. 3900 ms.

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

Problem G1 :

when I use vector freq((int)1e6 + 1);

I got TLE

after replace it with int freq[(int)1e6+1];

I got Acc

How can this happens?? If I use array by luck I got Acc!! it's bad tests

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

    Array allocation works in O(1) because it doesn't set the value. Vector allocation works in O(N)

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

    memset is faster than allocating a vector every time. But your solution might still be hackable.

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

A: If a[i]+i-1<=t we can choose the i-th video.

B: First we can choose (i, j) where a[i]*a[j] is the maximum product and remove all other elements. We sort all non-zero elements in a[i] and consider the maximum non-zero product. If there's less than 2 non-zero elements, the answer is 0. If there's 2 non-zero elements, the maximum non-zero product is their product. Otherwise, there must be 2 elements with same sign, and their product will be positive. We need to pick 2 elements with same sign and maximum absolute value to get the maximum product.

C: The answer is (n+1)^2+1 (by looking at examples), but how to prove it? Well, if we change the size of a cinnabon roll from n-1 to n, we need to add 2*n+2 chocolate outside, add 1 chocolate and remove 2 chocolate inside, so we have ans(n)=ans(n-1)+(2*n+1). Therefore we can get answer by induction.

graph explanation

D: First if i>1 and a[i]=n, we have b[i]=(b[i-1]+n)%n=b[i-1], so b[i] cannot be a permutaion, then we have a[1]=n. If n is odd, (n+1)/2 is integer, then we have b[1]=a[1]%n=0, b[n]=(1+2+...+n)%n=(n*(n+1)/2)%n=0, so b[i] cannot be a permutaion. If n is even, let a={n, n-1, 2, n-3, 4, n-5, ...}, then b={0, n-1, 1, n-2, 2, n-3, ...} is a permutaion.

E: If n is odd there's no solution. If there's any char c that there are more than n/2 occurences of c, there's no solution because by the piegonhole principle, there are n/2 pairs of symmetric positions and there are more than n/2 occurences of c, so there must be a pair of positions occupied by c. Otherwise, solution must exist. To calculate the minimum number of operations, let's see what can we do in one operation: For something like ..a..b..|..b..a.. (where '|' denotes the axis of symmetry), we can swap (ba) to turn it into ..a..b..|..a..b.. and remove 2 bad pairs; for something like ..a..b..|..b..c, we can swap (bc) to turn it into ..a..b..|..c..b and remove 1 bad pair. In other words, we can remove 2 different bad pairs or 1 bad pair in one operation. So we can calculate the number of bad pairs of chars from 'a' to 'z' and then we can get the answer.

F: Let ecc[i]=max(1<=j<=n)(dist(i, j)), then the cost of the tree rooted at i is k*ecc[i], and the cost of moving root from 1 to i is c*dist(1, i), so the answer is k*ecc[i]-c*dist(1, i). We can calculate dist(1, i) by BFS, and to find ecc[i] we can find a diameter of the tree, if (u, v) is a diameter, then ecc[i]=max(dist(u, i), dist(v, i)).

G1: The number of good triples where b==1 is sum(cnt[t]*(cnt[t]-1)*(cnt[t]-2)) where t iterate over all values of a[i], so we assume b>=2 for other good triples. For each possible value of k, we can see the maximum possible value of b is not greater than sqrt(a[k]), so the contribution of k is sum(cnt[a[k]/b]*cnt[a[k]/(b*b)]) where 1<=b, b*b<=k. The complexity is O(n*sqrt(A)).

G2: To optimize the solution of G1, we can see that if a[k]/(b*b) is integer, let c=a[k]/(b*b), we have a[k]=b*b*c, then we have b<=cbrt(a[k]) or c<=cbrt(a[k]), so we can find all possible combinations of (b, c) in O(cbrt(a[k])). We can solve the problem in O(n*cbrt(A)) using Hashmap or O(n*log(n)*cbrt(A)) using Treemap for checking cnt[t].

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

    I don't really get the difference in ACC between G1 and G2, the difference in difficulty does not seem that big.

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

      Because many people thought it would be related to some advanced topic like convolution and left

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

    For E, I did i = [0, n/2] and if ( s[i] == s[n-i-1] ) count++; Now, return ceil(count/2). What's wrong with this?

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

    really nice solution for G2!!

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

    Hi, for G2, isn't O(n*log(n)*cbrt(A)) around 1e9? I tried the method and it indeed passes, which is really weird to me. Another weird thing is I used std::map in G1 initially and it TLEed (complexity is O(nlogn sqrt(A)), so should be same, as in G1 A=1e6 and in G2 A=1e9), so I guess the test cases are built such that O(n*log(n)*1000) passes for G2 (and only in G2)?

    → Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

deleted

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

Can someone explain why my solution to G1 is timing out? https://mirror.codeforces.com/contest/1822/submission/203347556

Basically I check all possibilities for the middle element. For each distinct element a, I go through all factors x of a and add up (# of a/x)*(# of a)*(# of xa). This should take O(120n) since each number in [1, 10^6] has <=120 factors, which should pass; however, it TLEs. Can someone help? Thank you.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it 
        for (int x=1; x<=1000000; x++){
      if (c[x]>=3) T+= c[x]*(c[x]-1)*(c[x]-2);
    }

    This code block will be executed for each testcase, and there can be 10^4 testcases, so the code will run for 10^10 times.

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

Problem statement C was very hard to understand. At least for me.

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

    I just solved it by guessing the pattern in the samples.

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

Could someone explain problem D?

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

    There is to cases : n is even or odd, if it is odd the answer will -1, odd numbers will give two same numbers in mod operation so there is no solution, the corner case of odd numbers is 1 because it has legnth 1, the second case : if it is even the answer will begin with n then n-1, and flip between odd and even numbers from 2 and n-3, this is a valid solution like test case 4.

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

      For the case that n is even, I can't figure out the way to assign the permutation with $$$n, n - 1, 2, n - 3, 4,...$$$ like that. Is there any trick to come up with it?

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

        You want to sum up in a way that you go through all remainders $$$mod\, n$$$ exactly once. You have to start with $$$n$$$, otherwise you would not ever have a chance to use $$$n$$$ again, since $$$ (x+n)\, mod\,n = x\, mod\, n $$$. One way I saw to do it was to having two cursors for the remainders $$$l = 0, r = n - 1$$$ and iterating with $$$l$$$ frontwards and $$$r$$$ backwards. For example:$$$ n = 4 $$$, you want to have these remainders $$$\begin{bmatrix} 0,3,1,2\end{bmatrix}$$$, and the construction would be $$$\begin{bmatrix} 4,3,2,1\end{bmatrix}$$$. I'm not exactly sure why this construction works yet, just felt right to me. I'll try to update when I figure it out. my submission

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

I want to ask why the problem G1 my code's time complexity is (2e5*ln1e6) , but I get several times Time Limit Exceed? Can someone help？Thank you very much! This is my code:

#pragma GCC optmize(3)
#pragma GCC optmize(2)
#pragma GCC optmize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1000010,mod=1e9+7;
int a[N],n;
long long c[N];
int b[200010];
void solve()
{
	cin>>n;
	int mx=0;
	for (int i=1;i<=n;i++)
	{
		cin>>b[i];
		c[b[i]]=-1;
		a[b[i]]++;
		mx=max(mx,b[i]);
	}
	long long ans=0;
	for (int i=1;i<=n;i++)
	{
		long long res=0;
		if (c[b[i]]!=-1)
		{
			ans+=c[b[i]];
			continue;
		}
		if (a[b[i]]>=3)
			res=res+(a[b[i]]-1)*(a[b[i]]-2);
		for (int j=2;j<=mx/b[i];j++)
			if (b[i]%j==0)
				res=res+a[b[i]/j]*a[b[i]*j];
		ans+=res;	
		c[b[i]]=res;			
	}
	for (int i=1;i<=n;i++)
		a[b[i]]=0;
	cout<<ans<<'\n';
}
signed main()
{
	cin.tie(0)->sync_with_stdio(false);
	int t=1;
	cin>>t;
	while (t--)
		solve();
}
→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    If $$$b = [1000000, 1, 1, ..., 1]$$$, then $$$mx = 1000000$$$ and $$$mx / b[i] = mx$$$ for every $$$b[i] == 1$$$ which means that the inner for loop iterates from 2 to $$$mx$$$ on every iteration. Your complexity is $$$O(n * mx)$$$.

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

      But I have the code' if (c[b[i]]!=-1) continue' to skip the repeat b[i],so every b[i]==1 just can operate one time.

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

        Oh, I missed that line. But the complexity of your code is still at least $$$O(test cases * mx)$$$ though. Consider $$$1e4$$$ test cases of the array $$$b = [1000000, 1]$$$. Your inner for loop would make $$$mx$$$ iterations every time since you are resetting $$$c$$$ in every test case.

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

hacked :(

→ Reply
»
20 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it
  • What is the expected rating of problem E?
  • What is mostly rating range of problem E in Div 3?
  • What is mostly rating range of problem D in div2?
→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    1. Excpected rating of 1822E - Making Anti-Palindromes is 1615, according to CLIST:

    2. During the last 20 Div.3 contests, the rating of Div.3 E has always been in range [1400, 2000] according to CFTracker

    3. During the last 20 Div.2 contests, the rating of Div.2 D has always been in range [1600, 2500] according to CFTracker

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

Wonderful div3 round,i learned new things this round.Thanks to problemsetters!

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

Any hint or idea for problem D ?

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

    for i > 1; let a[i] = n; thus, b[i] = (b[i — 1] + n) % n = b[i — 1]; not possible since b is permutation; thus a[1] = n and b[1] = 0;

    if n is odd : b[n] = (n*(n + 1)/2) % n; n + 1 is even; b[n] % n = 0 but b[1] = 0; thus no "-1" if n is even : b[i] — b[i — 1] must be unique; here i think you need to use pen paper to observe or just check the last sample case;

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

Why does G1 has to have so tight constraints I submitted it in python and got that question hacked. Please make it fair for all languages. Atleast try to make in python and c++ many beginners use python.

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

    Actually it's not about python speed. In fact, pypy3 is fast enough to pass this problem. it is because someone generate a special test case to make python code that use dictionary to be TLE.

    You can sort the array before putting them into the dictionary, and it will be accepted. Here is your accepted code: 203372619

    → Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it -62 Vote: I do not like it

A rated round should not have had problem F. Its a blatant copy of the general standard problem of finding max distance of a node from each node of a tree. https://cses.fi/problemset/task/1132.

I highly doubt setters were unaware of this since its literally in cses. Please unrate the round in the future before pulling such schenanigans. Contest is not meant to copypaste submission and modify 2- 3 lines to get AC. (I say this as someone who got the problem in under 4 mins due to this exact reason)

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

    is not wanting cses problems to appear in cf rounds bad? :(

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

      It is not a good problem, but there is no reason why the round should be unrated, espically since div. 3 rounds are supposed to be educational anyways. The problem is also not a copy of the cses problem and no evidence suggests that.

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

        I didn't say the round should be unrated, rather such a problem shouldnt ever show on rated rounds, a minute difference being that i dont call for this round to be unrated, just any future ones trying to use cses problems.

        As for the copying part, cses problem : find max distance from each node, div3 problem : find max distance from each node, call it dist, and output max(k * dist — c * depth) instead

        Adding one extra step makes it non copied? (I do not joke when i say i only had to change 3 lines in my cses code aside from clearing global arrays due to this being multitest)

        Educational rounds can manage without having problems directly from cses, im sure div3 can too.

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

    This problem had same thing https://mirror.codeforces.com/contest/1805/problem/D.
    My solution which uses the cses questions code https://mirror.codeforces.com/contest/1805/submission/200411445.

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

      that problem required many other observations, div3F was more of a direct copy.

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

      I dont agree actually, yes that problem had a subpart which was basically that cses problem, but reducing it to that was a step, and not a small one to me.

      This problem is just directly asking for the ezact same thing as the cses one.

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

    It is quite standard, but not a direct copy, so there should be no reason to be unrated

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

Could please someone explain why this submission of G2 TLE's

My calculation of complexity
→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    First of all, $$$2 \cdot 10^9$$$ operations may TLE regardless due to the high constant factor of std::map. The reason why your solution gets TLE is due to multitest cases, which your calculation does not take into account. The test that your code failed on is just $$$10000$$$ copies of this test:

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

My current rating is 401. I've submitted solution of 5 problems of Codeforces Round #867 (Div.3), and all submissions was accepted. a This is my 2nd contest, but still my rating is not increased. Can anyone tell why?

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

To be honest ,I still do not understand Problem C,but just by observing the test cases,I came out to the solution

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

    check out YocyCraft solution above in comments. He's explained it pretty well.

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

    Just add 4n (outer layer), Σ(n-1), Σ(n-2) and 1. You can observe the pattern of the chocolates. But yes, it was decipherable from the test cases.

    On the other hand, I got problem-D AC by guessing the pattern from test cases. Odd numbers dont have solutions, and for even, start by placing n at the beginning, and n/2 in the middle, and on both sides of n/2, place the numbers n-1, n-2, n-3, etc, but in alternating order on left and right sides

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

Is there anyone like me who like Div 2 rounds more than the Div 3 ones?

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

    Yeah, me. I was able to solve A-D in this contest, out of which A,B were very easy, and C,D were guesswork from testcases. I got good rating change, but didnt teach me anything.

    On the other hand, altho I usually lose rating in Div 2 rounds, There's always something I learn, either during the contest or after it.

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

I'm new in contestant in Codeforces. I wanna clear that is Codeforces Round 867 (Div. 3) was a rated contest? I solved two problem(A & C) but my rating/rank is looks like that...

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

    It is a rated contest. Since the rating change is not completed yet, it doesn't show the rank. It will be updated as soon as the rating change is completed.

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

This is the first time ever I solve a div3 F instantly. I can't believe that there was a time when I struggle to solve div3 E. It feels pretty amazing

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

no way,i think e is harder than f and g1 XD

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

Hello friends, I have uploaded the video editorial of this contest from A to F. Editorial. If want, You can watch it!!!

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

I feel like problem C and D are just "guess correct solution" problems / see pattern. Is this kind of problems okey for you guys?

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

Hello! I'm kinda new here so please don't be soo critical T_T for the first problem this works fine on my codeblocks but for some reason it gives different outputs when submitted https://mirror.codeforces.com/contest/1822/submission/203327103

and what is more confusing is that the output change when I change the variables type from int to ll Can someone please help me T_T

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

    This line - for(int i=0;i<n;i++) { cin>>b[n]; } should be- for(int i=0;i<n;i++) { cin>>b[i]; }

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

I don't know why i am unrated even though it's division 3 and I'm a newbie who participated first contest in Codeforces. can someone explain why for me?

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

    It's not unrated for you. You are just not a trusted participant yet. You need to participate in atleast 5 contests to be a trusted participant. The round will still be rated for you, it's just that you will not be in the official standings for the contest.

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

Is the round unrated? I am below 1600 and have participated in a lot of CF contests, still it is unrated for me, anyone know why?

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

Can someone explain why my code got accepted in the contest, now after system testing it's showing TLE there weren't any pretests as far as I remember.

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

    New test cases created/generated by participants during the hacking phase are added to the original set of test cases. During system testing, the solutions are rejudged with this new set of test cases. Your code might be failing on the new test cases.

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

    after the contest ends hacks and more test cases are added to the original test cases

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

Why I did not get contest rating points despite solving 3 problems?

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

when will updated??

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

Pretty bad systests for G2 O(sqrt(a[i])*n*log(n)) with some small constant optimisations is AC

[upd] all hash tables(with custom hash also) instead of map give TL, which is quite funny

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

    Yeah the tests are really weird.

    Edit: Wait you mean sqrt instead of qbrt? That would be roughly 1e11 right? How on earth can this pass.

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

      Yes, that is the point. Constant optimizations)

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

Has anyone solved Problem F using Rerooting?

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

Can someone hack these solutions? solution1 solution2

They both failed on this test case:

Spoiler

UPD:Thank's pavlekn for hacking them

→ Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
#include<bits/stdc++.h>
//#pragma GCC optimize(3)
#define int long long
using namespace std;
const int N=200005;
int a[N],n,T;
map<int,int> mp;
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;
		mp.clear();
		for (int i=1;i<=n;i++)
		{
			cin>>a[i],mp[a[i]]++;
		}
		sort(a+1,a+n+1);
		int ans=0;
		for (auto u : mp)
		{
			int x=u.first,res=u.second;
			ans+=res*(res-1)*(res-2);
			//cout<<x<<" "<<res<<endl;
			if (1*1!=x) ans+=mp[1]*res*mp[x*x];
			for (int b=2;b*b<=x&&b*x<=1e9;b++)
			{
				if (x%b!=0) continue;
				if (mp.count(x/b)&&mp.count(x*b)) ans+=mp[x/b]*res*mp[x*b];
				if (b*b!=x&&mp.count(b)&&mp.count(x*x/b)) ans+=mp[b]*res*mp[x*(x/b)];
			}
		}
		cout<<ans<<endl;
		//cout<<mp.count(2)<<endl;
	}
	return 0;
}

This is my code for problem G2, it got Accepted. But if I use a std::vector to traversal all numbers,it
get TLE 203456289. Why std::vector is so slow and std::map is efficient?

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

For problem F, I only considered one endpoint of the diameter and didn't consider the other one, but it still passed tests. Why does that work? The endpoint I considered was the furthest node from 1.

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

    If you are already on the diameter then the cost to get to the closer end will be <= to the cost to get to the furthest end (and it's obviously optimal to stay on the diameter).

    If you aren't on the diameter every move will change the distance to both ends of the diameter by the same amount until you reach the diameter (at which point you move to the closer end).

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

I think i have used ideone in public mode by mistake and I was absolutely unaware that someone can see my solution there because of which my solution has been copied by somebody/ or it can be an absolute coincidence! Sorry for this but I will take care of it from next time while using ideone. Please have a look into this . MikeMirzayanov . Question F of the recent div3 round caused this issue :( . Please revert back my ratings . 203313670 Submission ID for the question . Please revert back my ratings

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

So my solutions for B and C have been reported as cheating, since they are too similar to others (from https://mirror.codeforces.com/profile/KudoConan) B: Mine: https://mirror.codeforces.com/contest/1822/submission/203276161 His: https://mirror.codeforces.com/contest/1822/submission/203330555 C: Mine: https://mirror.codeforces.com/contest/1822/submission/203281804 His: https://mirror.codeforces.com/contest/1822/submission/203329843

As you can see they are almost excactly the same. I don't know what to do now, since i have not shared my code with anyone and as you can see my submissions have been an hour before his. Since the solution are very "easy" and there isn't much room for different approaches in Python it feels like there should be a lot of similar solutions for these problems.

Well I guess the only evidence I have is that his A is different from mine and that I also solved D and E, still I am not sure what to do, if there is anything I can provide please let me know.

→ Reply