MateoCV's blog

Codeforces Round 856 (Div. 2)
By MateoCV, 4 weeks ago, In English

Hola Codeforces!

I am happy to invite you to Codeforces Round 856 (Div. 2), which will take place on Mar/04/2023 20:35 (Moscow time). Notice the unusual time! The round will be rated for participants with rating lower than 2100. You will have 2 hours to solve 5 problems. The problems were authored and prepared by me.

I would like to thank the following people who made the round possible:

See you in the standings!

UPD:

Scoring distribution: $$$750$$$ — $$$1000$$$ — $$$1250$$$ — $$$2000$$$ — $$$2750$$$

UPD: Editorial

UPD: Congratulations to the winners!

Official winners:

  1. lunchbox
  2. Meaf
  3. 14th_onresp
  4. ErdemKirez
  5. izhang

Unofficial winners:

  1. jiangly
  2. maspy
  3. neal
  4. potato167
  5. arvindf232
  • Vote: I like it
  • +605
  • Vote: I do not like it

»
4 weeks ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Veryyyyyyyy unusual time! (^-^)

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    This contest will have least number of participants in this year

    → Reply
»
4 weeks ago, # |
  Vote: I like it -47 Vote: I do not like it

Please change time to usual.

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

    Randomness is the beauty of codeforces.

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

      We could not, for example, arrive at a principle like that of entropy without introducing some additional principle, such as randomness, to this topography.

      U get it? I don't, if u do pls enlighten me Sir.

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

      Heisenberg would agree.

      → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +209 Vote: I do not like it

OP has set two contests and the times are

March 4 2022 21:05 — March 4 2022 23:05 and

March 4 2023 23:05 — March 5 2023 01:05 (times are in IST UTC+5.5).

Without paying attention to the year it may seem two contests happen back to back without any break. A real coincidence

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

    They say he is the real life Sōsuke Aizen(Bleach Reference).

    → Reply
»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Omg, it starts at 00:35 in Vietnam, not a comfortable time for me.

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

very excited about Argentinian round, and congrats once again to you and your team for getting LATAM Champions! all the best, hoping to see some nice problems in this round

→ Reply
»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Shortest announcement

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be hacking phase in this too. I wanna try my luck in hacking too.....kekw

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

    You can attempt hacking only if you solve a problem and lock it.

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

      In 855 (Div 3), there was no option of locking, it was open hacking after contest.

      Is it there in 866 (Div 2) too, or it's just that hacking allowed in Room :(

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

        Usually it's rooms in div 1, div 2 and div 1+2. There is no open hacking phase.

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

it's very good

→ Reply
»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

contribution can affect the rating?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

23.05 in India, but still i will give this contest. hope i'll get to learn something new from the contest. all the best to everyone.

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

    You are giving you first contest at uncomfortable time, good experience for you.

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

      In the second contest with awkward timing and not the first contest!

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

MESSI is the champion!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I got -70 last round :( I hope I can get some of that back. Good luck to all participants!

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

A round with unusual time and longer duration than normal div2 round!

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

Midnight contest go brr brr!

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

as a tester, I think this will be a great contest.

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

    bro I got a question.

    How do you guys make test cases?

    I know this is a very abstract question.

    But I've been thinking about this for a while.

    Kindly explain with a relevant example when convenient.

    All the best for your tester role!!!

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

      I was querious about the same things.. can someone pls explain

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

      People write code to generate test cases

      checkout testlib.h on github

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the round is on unusual time if it is not based on some onsite round?

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

    Author's time zone is GMT-3. Same issue with football tournaments such as Copa America and World Cups hosted in South America xD

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

I'm glad that I ended up testing a South American round. Expect great problems :3

→ Reply
»
4 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

Thanks you MateoCV for lisening me

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

hope to see first egyptian lgm this round

EGYPSHIAN LGM TIME IS COME!!!!!!!!

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

Wish i do well in this div

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When scoring distribution will announced?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is c2 ladders a good way to increase someone ratings or should I try something else?

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

    whatever the answer maybe is it the right place to ask this question?

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

Really appreciate the unusual time, I'll get a little extra sleep instead of waking up at 6:00.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

late night contest

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

Rare American friendly contest time :D for once I won’t need to wake up at 6am to attend

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

    But I still will for the leetcode biweekly lol

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

BTW where is the # before the number on the contest page? I can't find it anymore in any numbered contests...
If this is a persistent change, I must join the round as a memory though it starts at 02:35(UTC+9) :)

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

[redacted]

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Quite excited to participate in this Latam round ❤️

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

I think the time is a bit unreasonable.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am a beginner do you encourage me to participate?

→ Reply
»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

8 pm in india

→ Reply
»
4 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

very 《good》 time to compete for Chinese...

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Vamos Argentina The world Champion campeons del mundo

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i think this contest originally was 2.5 hours to solve 6 problems~! :|

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How does the change in rating gets affected by the number of people

→ Reply
»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

OMG i hope at this hour there will be no indian cheaters.

To indian cheaters, please go to sleep. Don't ruin everyone' fun with your small pp energy, go cheat elsewhere

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good time for south-asians. Hope I can at least solve one :)

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So sad I can't say " Hope this is my CM promotion contest "

I need 120 this time :(

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

I like the timing. Please host more contests at this time.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope this time I will be Pupil

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

omg unusual time

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

Comfortable time for night owls (UTC+6)

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

It is a good time.

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

Omg, it starts at 1:35 in China, not a comfortable time for me.

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

Waiting for something good

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

Score distribution where?

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

Finally a contest with a good start time for US west coast participants! Would love to see more contests at this time.

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

today I drove for 8 hours, around 300 km. Pretty scary road. I am tired as F**K. I was looking forward to this round but didn't see the timings. I feel like attending the round, but I might be too sleepy to attend it. upvote if I should take part, downvote if I should take rest !!!!

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

    Really Good and straightforward problems.

    Tried my best. Got stuck on B for LONG LONG (56 Minutes long) time, and solve C in 18 minutes. Feel disheartened for not seeing the pattern in B quickly :( .

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

22:35 in Turkmenistan.unusual time.everybody Good luck!

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

looking at the score distribution , i can predict it will be an unbalanced contest and will have a huge difficulty gap between C and D

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems to be hard ;)

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF

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

THE BEST CONTEST OF MY LIFE

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can you open the regestiration again. i forgot that.

i solved three three problems.

i need this contest please

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

This round needs an extra problem F.

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

how to solve E ?

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

How to solve D?

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

A was unique for a problem A. I actually solved C faster than A and B, so I thought C was cute. B made me want to pull my hair out. I basically reached the maximum penalty then bashed it until I saw AC.

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

My solution for $$$D$$$:

This problem has an $$$O(nlog^2n)$$$ solution.

Note $$$diff$$$ as the number of different prime numbers.If $$$diff<n$$$,no solution.

Note the number of occurrences of $$$x$$$ is $$$cnt_ x$$$.

Construct polynomial: $$$(1+cnt_{p_1}X)(1+cnt_{p_2}X)...(1+cnt_{p_{diff}}X)$$$

Expand this polynomial and note the coefficient of $$$X^n$$$ is $$$facn$$$.

The answer is:$$$facn\frac{n!}{(\Pi cnt_i!)}$$$.

Why?
→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    How can we find coeff of X_{n} in nlogn

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

    This is exactly the formula I came up with but couldn't implement properly because I had never used fft before.

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

    How do you expand polynomial in O(n log n) ? Is dividing in the middle and combining them with FFT O(n logn) or O(n log^2n)?

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

      You're right,I think it's $$$O(nlog^2n)$$$

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

    can you use DP to solve this?

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

      jiangly solve this using dp. Check his submisson

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

A>>>B

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

    For me it was opposite. Got Fst on B. Haha solved a in 5 min.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Misinterpreted the C´s formula but learned something today, Thanks for the contest.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was E tree hashing?

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

Got D accepted 1 minute before the end of the contest. I am feeling so happy right now.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B?

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

    Turn all 1's to 2's in one iteration . Once that is done , check for every 'i', whether A[i+1] is divisible by A[i]. If yes, increment A[i+1] by 1 and move on.

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

    you basically increment all the elements that are 1 after this you traverse whole array and if a[i+1] is divisible by a[i], increment a[i+1], this solution will assure that the array already corrected will not be messed up, and the moves required will be always less than 2n

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      for (int i = n - 1; i > 0; --i) {
        while (a[i] % a[i - 1] == 0){
            a[i-1]++;
           
        }
    }

      Can you suggest a test case please, couldn't find why it doesn't work

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

        this solution can exceed the 2*n moves limit sample test: 1 120

        your algorithm will take 5 steps to make good array in this sample while allowed moves are only 4

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

          omg, couldn't find it 2 hours, thanks a lot!

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

            just two numbers 1 and n! Then you need yours algorithm needs n operations (1->2-> ... -> n+1)

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

        1,1,2. In this case, it will become 2,2,2 and it will not pass.

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

        1 2 1 60

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

I loved problem D, thanks! (might be biased because I am a math major ^^').

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

    How did you solved it?

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      • Step 1: Find the number of occurences of each number in the input.
      • Step 2: Split the numbers and their counts into two parts: primes and non-prime numbers.

      Step 3: How do we get a valid prime decomposition? - First, we need to pick exactly $$$n$$$ distinct primes. (also note that for two different sets of primes, they will never give a same number, no matter how the powers are picked) - Then, we need to count the number of non-equivalent ways of putting the exponents. This is $$$n!$$$ divided by the product of the factorial of the exponents. - When summing over all the possible arrangements of the expronents, a prime a number has a contribution of 1 over its number of occurences if is not in the decompposition, and 1 otherwise. To compute the sum, I realized it was just the elementary symmetric polynomial of degree (number of prime numbers — n) computed on the inverse of the counts of the prime numbers.

      Step 4: The elementary symmetric polynomial can be computed with dynamic programming.

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

        In step 3 what do you mean by "a prime a number has a contribution of 1 over its number of occurences if is not in the decompposition, and 1 otherwise" ?

        How do you realize "To compute the sum, I realized it was just the elementary symmetric polynomial of degree (number of prime numbers — n) computed on the inverse of the counts of the prime numbers." ?

        Any resources ?

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

          Reading again my last message, I realized the explanation was terrible. x’)

          Denote by $$$\alpha_i$$$ the number of occurrences for the non-prime numbers and by $$$\beta_i$$$ the number of occurrences for the prime numbers $$$p_i$$$.

          When picking exactly $$$n$$$ distinct prime numbers, the number of valid decompositions is $$$\displaystyle\frac{n!}{\prod \alpha_i! \prod (\beta_i - 1)!} \prod \left( 1 ~\text{if}~ p_i ~\text{is used else}~ {\beta_i}^{-1} \right)$$$

          The right product is what I meant by "a prime a number has a contribution of 1 over its number of occurrences if is not in the decomposition, and 1 otherwise". The left factor does not depend on the primes which were picked.

          In order to compute the sum of all the right products, I rephrased it as “I want all the ways to pick $$$n$$$ 1’s (for the primes that divide the number) and fill the rest with the inverse of the number of occurrences”. This is can be computed as the coefficient in front of $$$X^n$$$ in $$$\prod (X + {\beta_i}^{-1})$$$ (You can see that a bit like the combinatorics argument for $$$(1+X)^n = \sum \binom{n}{k} x^k $$$: to get $$$x^k$$$, you need to pick $$$k$$$ positions for $$$x$$$ among the $$$n$$$ possible positions).

          In order to compute this coefficient, you can use a mix of FFT and Divide & Conquer which runs in $$$O(n log^2 n)$$$ but I did not want to bother with that and I checked the problem constraints: a $$$O(n^2)$$$ algorithm will do the job.

          To compute this coefficient, I used the first equation in the properties section the Wikipedia article on elementary symmetric polynomial (I actually knew it from my studies). Evaluating elementary symmetric polynomials can be done by dynamic programming thanks to the following equations (I also knew them from my studies).

          Notation $$${e_i}^{(j)}$$$ is the $$$i$$$-th elementary symmetric polynomial on $$$j$$$ variables.

          $$$\forall j, {e_0}^{(j)} = 1 ~\text{and}~ \forall j, \forall i > j, {e_i}^{(j)} = 0 $$$
          $$$ {e_{i + 1}}^{(j + 1)}(x_1, …, x_{j+1}) = {e_{i + 1}}^{(j)}(x_1, …, x_j) + x_{j+1} {e_{i}}^{(j)}(x_1, …, x_j)$$$

          EDIT: I missclicked on "post" instead of "preview". I am going to edit this post with the full answer.

          EDIT 2: I finished updating the message.

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

            Thank you so much for detailed explanation, people like you make codeforces a better place :)

            → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A's problem statement was deceptively simple, I thought there should be a two liner solution but I couldn't find one. However, I think I did come up with an elegant sorting solution for A:

void solve(){
    int n;
    cin >> n;
    vector<string> v;
    for(int i = 0; i < 2*n-2; i++){
        string temp = "";
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end(), [] (string& a, string& b){return a.length()<b.length();});
    bool ok = true;
    for(int i = 0; i < v.size()-1; i+=2){
        reverse(v[i+1].begin(), v[i+1].end());
        if(v[i] != v[i+1]) ok = false;
        
    }
    if(ok) cout << "YES" << endl;
    else cout << "NO" << endl;
}
→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yours solution is good. But there will be no more than 2 substrings that contain (n-1) size. Just find those two substrings and reverse any of them, if those two substring matches, the ans is "YES", otherwise "NO".

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

      What an Elegant Solution, Wow impressive problem A, I didn't give this contest as I couldn't solve A so left it and in India it was midnight. Now I realise this contest has very impressive problems, so I'm solving problems now.

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Let me say it's a clear statements, thank you.

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

rank 2800 and got -10 rough contest

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

D solution: first group the number by their count. Then solve base on this. We will split the problems into two combination: The base and the power. The base has to be unique

Let's call DP[i][j] mean at index ith, we have j prime factors left. This would uniquely determine the number of the power slots left, because if there are X numbers from i + 1 to the end, and j number has been used as base, then there are j — X numbers that were used in the power slots. This means there are n — (j — X) slots left to be used as Power. The number of ways to select number i into factor slots is (n — (j — X) choose count if i. Do the same if the number at i is prime but with one less prime count.

from there just do a count of unique combination

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem C?

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

    just observe that if the d is the size of your subsequence, then you should not have anything that is less than d, since you can always remove it and make the value larger.

    so to solve for ith, let say you add ith into your subsequence, then you start removing the smallest element until the value of this element is not smaller than the size. That'd be your answer.

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

      can you please elaborate it with an example it's still not clear to me

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

        Easier, more straightforward way to do this is by going in reverse. You start by computing the best answer for the whole array. That's easy to do because you just greedily go from the last number until you can't add the number without decreasing the m parameter. How do you do that? First, let's make use of one observation — for a segment (l, r) the numbers that you are going to use in the optimal solution are going to be the largest numbers because the formula is their product divided by c! where c is their amount. Now, after this step, we should have two things : the answer for k = n and the index where the next number lies (going through the reversed sequence). Now, simply iterate from the end to the beginning, removing numbers one by one and greedily adding numbers from index and moving it towards the start as long as it doesn't decrease m. We don't actually care about the exact value of m. Why? Because the formula is the product divided by c!, if we want to add a number, we would multiply m by it and then divide m by (c + 1) we can notice that as long as our number is larger or equal to c+1, m doesn't decrease.

        You can find the implementation in my submissions

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

          So basically we are just moving from right to left and we keep moving until and unless Ai<m (here m is 1,2,3...n) because if m becomes greater than Ai and if we take it then it (Ai/m) doesn't contribute in maximizing so as soon as we encounter it we will break at that point and length of maximized scored subsequence would be r-l+1.Am I thinking in the right way? If I am thinking in the right way how do I implement the above approach using Binary search. I think I might get TLE if I do something else other than BS because for every point we ned to get (l,r) and that would take O(n^2). Right?

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

            it's O(N), let me say it in a simpler way

            First observation is that we always want to take the highest numbers possible. You are right with the Ai < m, yes. The length is r — l + 1 but you can notice that it's not going to be O(n^2) since we are always going to move l at most n times (since we only ever move it to the left) and r exactly n times (by "removing" elements). And since every move results in a new subsequence we will have not more than 2 * n subsequences which results in O(n) solution. It's called the "sliding window" technique if you want to read more about it.

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

              thank you for clearing out my query sensei(I hope you do watch anime)

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

        My humble attempt to explain: -> https://www.youtube.com/watch?v=yJB3TEus8SA&ab_channel=CodebyShuvam

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

Nice math problems :)

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell we if i am right. D:

Let's call b a set consisting all numbers from a, p a set of all primes in a, k is length of this set, then:

ans =

SPOILER, maybe...
→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i just used wrong modulo, but i am pretty sure this should work...

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

What do you guys think was the rating number for problem A?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy A-C, hard D and E

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why my solution is MLE https://codeforces.com/contest/1794/submission/196011471

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

here after the contest. I am a night owl so this is the best time for me. Hope more contests can happen around this time. The first question implementation took really long time for me. B was surprisingly much easier.

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

pov: aped B with dp after trying and failing to come up with anything ;-;

Spoiler
→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I reached max penalty for B and wrote random code until I saw green.

    → Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

just noticed mateoCV always comes on 4th march with amazing contest.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't get any approach for problem C anybody please let me know in what direction should i think for it.

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

    Binary search

    → Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint

    Maybe that's too subtle of a hint, but the editorial is also out if you're stuck for too long.

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

    In C you need maintain the multiset, where the min element is >= size of set. The answer is size of set on each step. So the approach is just to find math observation and then implement it.

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

      Ohhh I see thank you it's completely clear now i think i will be able to solve it easily

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

    My humble attempt to explain: -> https://www.youtube.com/watch?v=yJB3TEus8SA&ab_channel=CodebyShuvam

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

Ratings updated preliminary, it will be recalculated after removing the cheaters.

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

    Is this already done? My delta remain unchanged, which is rare if it is done.

    → Reply
»
4 weeks ago, # |
← Rev. 4   Vote: I like it -27 Vote: I do not like it

it is a good contest

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any predictions for rating problem D?

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

For problem E, I thought lets make the 2 lists pri, comp where pri stores the count(non zero) of each prime element and similarly comp for composite. Let us denote them by pri={x1,x2,x3....}, comp={y1,y2,y3....}. Then my answer is ((x1+x2+x3....+y1+y2+y3.....-n)!/((x1!)(x2!)(x3!)....(y1!)(y2!).....))*(Sum of elements in pri taken n at a time). The idea is that lets select the primes which will be in the base then the powers can be arranged as (x1+x2+x3....+y1+y2+y3.....-n)!, then just to remove the repetition we will divide it by x1!,x2!....and for yi if we have used yi the divide by (yi-1)! else divide by yi! and for that I used the sum of element thing.

Here is my submission:196054295

Can anybody find my mistake ? And sorry for bad English.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

first question was tricky.

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Thanks for the nice round !

Here is my feedback about each problem

A
B
C
D
E

I'm looking forward to take part in other rounds that you set!

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

    +1 specifically for the comments on div2A

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

Solved.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why round not rated for me (2071 rate) MikeMirzayanov?

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

Due to the uncomfortable time in China I didn't have a chance to participate in this great contest. However, after my virtual participation today I'd like to express some of my points so far. Here are them:

  1. for A,B and C, I don't have many words to say. They are intersting but just a little easy.
  2. for D, I think it's not very proper to place a simple and standard dp on the position of the last two problems of div2 contests. However, solving this problem did strengthen my dp skills.
  3. for E, I think it's too easy to be a div2 E. You can solve it quickly as long as you have once learned tree hashing. And the annoying part of hacks in selecting modular numbers is also boring. Anyway, the E should be replaced in order to make a more balanced and interesting problemset.

However, though some problems exists, the whole quality are definitely all right. And Thanks for the authors' and testers' hard work in the contest!

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the rating for question C ?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I getting WA on test 9 ? My code I have used bottom-up dp. Could someone help.

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

please upvote::https://codeforces.com/blog/entry/113556#comments

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C, let's say we have sequence 1, 7, 9..... and we want to get the val of (1*7)/(3*2). Which is ofc greater than 1. but if we consider it as (7/2) and (1/3) then 1/3 is omitted as it is less than 0. But it should be included as overall prod>1. Isn't it?

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

muchas gracias aficiónados esto para vosotros SIUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

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

i think it is from the best contests i see in my journy till now.

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

ususual time

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just this contest?So easy.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is it bag?

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

MikeMirzayanov I got a rules violation for my A solution. I didn't copy or leak my solution. It's a pure coincidence the solutions are so similar.

→ Reply