MateoCV's blog

Codeforces Round 856 (Div. 2)
By MateoCV, 21 month(s) 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. kalimm
  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

Comments Comments (162)
| Write comment?
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Veryyyyyyyy unusual time! (^-^)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -47 Vote: I do not like it

Please change time to usual.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    Randomness is the beauty of codeforces.

    → Reply
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    01:35 in China

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    23:05 in India

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    very good time for me, 6:35 in NZ. The usual time in NZ is 3:35

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The common CF contest is 6:35 am for US west T_T. And solving problems with a frozen dizzy brain is a skillset we have

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      True. I always do better on early morning contests due to all the practice on codeforces.

      → Reply
»
21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it -14 Vote: I do not like it

contribution can affect the rating?

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

MESSI is the champion!

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Midnight contest go brr brr!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Wish i do well in this div

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

late night contest

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    But I still will for the leetcode biweekly lol

    → Reply
»
21 month(s) 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
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

[redacted]

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Quite excited to participate in this Latam round ❤️

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -12 Vote: I do not like it

I think the time is a bit unreasonable.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I am a beginner do you encourage me to participate?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -13 Vote: I do not like it

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

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

Comfortable time for night owls (UTC+6)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

It is a good time.

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do you think is a good time for us?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I think starting the competition at 19:00 is a good time.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Waiting for something good

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Score distribution where?

→ Reply
»
21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

THE BEST CONTEST OF MY LIFE

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +45 Vote: I do not like it

This round needs an extra problem F.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

how to solve E ?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D?

→ Reply
»
21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you use DP to solve this?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      jiangly solve this using dp. Check his submisson

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

A>>>B

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Was E tree hashing?

→ Reply
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B?

→ Reply
  • »
    »
    21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1 2 1 60

        → Reply
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you solved it?

    → Reply
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
        • »
          »
          »
          »
          »
          21 month(s) 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
          • »
            »
            »
            »
            »
            »
            20 months 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

rank 2800 and got -10 rough contest

→ Reply
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem C?

→ Reply
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
        • »
          »
          »
          »
          »
          21 month(s) 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
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Nice math problems :)

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy A-C, hard D and E

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) 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
  • »
    »
    21 month(s) 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
»
21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Binary search

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It can be done in O(n)

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think binary search is more intuitive in this problem

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          idk, for me sliding window seems like the most straightforward, obvious solution

          → Reply
  • »
    »
    21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Any predictions for rating problem D?

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Solved.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the rating for question C ?

→ Reply
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

muchas gracias aficiónados esto para vosotros SIUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

→ Reply
»
20 months 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
»
20 months 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