Educational Codeforces Round 148 [Rated for Div. 2]
By awoo, history, 19 months ago, translation, In English

Hello Codeforces!

On May/12/2023 17:35 (Moscow time) Educational Codeforces Round 148 (Rated for Div. 2) will start.

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

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

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

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

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space

Your Path to Success Starts at Harbour.Space Bangkok

Hello Codeforces!

We are excited to announce that we are offering 10 full scholarships to study Computer Science or Data Science at Harbour.Space, Bangkok Campus!

We invite you to apply to our university in Bangkok, Thailand, where we offer a full scholarship for qualified participants.

Our university has a vibrant and inclusive community, where you'll have the opportunity to learn from and collaborate with some of the brightest minds in your field, such as the one and only Mike MikeMirzayanov Mirzayanov. Additionally, our state-of-the-art University is designed to support your academic success and personal growth.

If you want to pursue higher education, get accreditation and expand your horizons, we encourage you to apply! As members of the Codeforces community, we recognise your talent and dedication to problem-solving, and you would make an excellent candidate for our programme.

Requirements:

Study Commitment: 3 hours/day. You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.

University requirements

  • CV
  • High School/Bachelor's Degree
  • English proficiency
  • Medalist in any Programming competition is a plus!

Make sure to apply before June the 30th, 2023, to be eligible for the scholarship and reduced application fee!

Apply here →

We look forward to hearing from you and welcoming you to our community.

All the best, The Harbour.Space Team

UPD: Editorial is out

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

Comments Comments (132)
| Write comment?
»
19 months ago, # |
  Vote: I like it -109 Vote: I do not like it

Ready to get +DELTA (◠‿◠)

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

    I have seen you commenting things like "Fingers Crossed for +delta (◠‿◠)" on almost every blog but the last time you really participated in a contest is 6 months ago. Is contribution really the whole thing you came to Codeforces for?

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

      At least, I am willing to participate but because of some reasons I am not able to do so. So you better concentrate on your contests rather than checking mine.

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

        I wish that all your problems & issues are resolved ASAP so that you can participate in the contests like you did before =)

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

awoo's round.

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

    Kindly keep your homoerotic comments about awoo to yourself.

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

      Same to you. Just putting the rude comments in every blog make conflicts.Do participate in any contest.

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

      Bro wtf. It has been a year and you haven't participated with this id. What's the plan?

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

As a participant, give me a contribution.

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

As a cyan tester,I recommend you to see all problems.

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

Hope for the _Best_

See in person
→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping for a nice contest

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

It is my first codeforces contest, please say good luck to me.

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

I'm ready to get educated.

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

    I have observed the process of your rating change. How were you able to consistently improve your skills like this?

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

crazy standing XD，but Why did more people pass E than D

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

    Ay the end — this was not true. Although i saw E getting more sollutions and went for it instead.

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

bad round :dislike:

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

I really enjoyed this round. The dynamic programming idea behind E is so fun!!!

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

ABCforces

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

is E convolution?

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

    After dealing with all the math it ends up being something like the O(N*R) dp for calculating nCr on steroids.

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

      i tried to understand your code, i understood why we are using pref[k][i] = pref[k-1][i-1]+pref[k][i-1], but i have a silly doubt why the solution getting stored at 1 index more than the original index(eg: pref[1][k] at pref[2][k])?

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

        Yeah, I messed up something with the indexing and saw that as an easy fix. During a competition I don't really care about being exact in my indexing/naming.

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

    Apparently it can be solved using that within the time limit (comment by physics0523), but this is (probably) not the intended solution. There exists a much simpler and (imo) more beautiful solution using properties of the binomial coefficients and dp (and the fact that k is small).

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

    Dynamic programming. If you remember the recursive formula for the f(x, y) = f(x — 1, y — 1) + f(x — 1, y), then the solution is quiet obvious Let dp[i][j] be the solution for the problem find $$$b_j$$$ if k = i, then dp[i][j] = dp[i -1][j — 1] + dp[i][j — 1] Then its just simple optimisations.

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

E: orz to Nyaan's extremely fast Convolution (Large)

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

    How long the code is! Nyaan must have written the template a long time ago ...

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

I got thought of the B and C, but I can never pass them... pity! hoping for your next contest!

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

Can someone explain how in problem B 6 2 15 22 12 10 13 11 got an output of 46 max I could calculate was 40

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

    Apply 2nd operation 2 times.

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

    Yeah. Even i was stuck on it. Then I realize it was just and easy bruteforce problem. Just try every k lol.

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

I think there should be an explanation to the sample test in task E

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

Solved A-E. But it seems that the number of accepted solutions of F is far less than it should be.

A: Let n be the length of string s, then we only need to check first floor(n/2) chars of s. If they are all the same, we can't get any another palindrome. Otherwise we can choose 2 different chars from them and swap them (and chars on the symmetric positions on the right half) to get another palindrome.

B: Sort the array and calculate the prefix-sum. Assume we use the 1-st operation for t times, we will remove 2t elements from the front and t elements from the back of the array. We can try all possible options of t from 0 to k to get the answer.

C: First we can remove all adjacent elements with equal value, and the contrast value will remain the same. Then we only need to remain local maximum and minimum elements of the array (including the first and the last), since if a < b < c or a > b > c we have |a-b|+|b-c|=|a-c|.

D: If k<=n, we can add values from 1 to k on different elements of the array. But if k>n, some values from 1 to k will be subtracted from the array. To make the numbers subtracted be as small as possible, the increments of each operation will be like this: 1, -2, 3, -4, 5, -6, ..., k-2, k-1, k (there are n or n-1 positive values on the back of this sequence, depending on the parity of k-n), then we need to subtract 1 from any values of the array for ceil((k-n)/2) times, and add inc=(k-2*ceil((k-n)/2)) values (from k-inc+1 to k) to different values of the array. To simulate this process, we need to sort the array, and add k+1-i to a[i] for 1<=i<=inc, and find the minimum of the array (we can do this fastly by pre-calculating prefix-minimum of a[i]-i and suffix-minimum of a[i]), then do the subtract operations on some maximum values of the array.

E: The prefix-sum of a[i]:

a[1], a[1]+a[2], a[1]+a[2]+a[3]...

The prefix-sum of the array above:

a[1], 2*a[1]+a[2], 3*a[1]+2*a[2]+a[3]... (which is b[i] when k=1)

The prefix-sum of the array above:

a[1], 3*a[1]+a[2], 6*a[1]+3*a[2]+a[3]... (which is b[i+1] when k=2)

The prefix-sum of the array above:

a[1], 4*a[1]+a[2], 10*a[1]+4*a[2]+a[3]... (which is b[i+2] when k=3)

By this pattern we can solve the problem in O(n*k) by calculating the prefix-sum for k+1 times.

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

    What is the intuition behind coming up with successive prefix sums to replace these complex i choose K operations ? in E ?

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

      C(n , k) = C(n — 1, k) + C(n — 1, k — 1) So b[n][k] = b[n — 1][k] + b[n — 1][k — 1]

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

    How to solve D with Binary Search?

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

wtf is D

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

I think problem E is interesting, even if I didn't solve D or E. Can anyone explain the idea of problem D? Thanks!

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

    First of all, if k <= n the solution is easy, so everything I will say is for k > n.

    If you perform an even number of operations on an element you are guaranteed to decrease some value from it, since for each number you add you subtract a bigger number right after, so if you are trying to increase a value (and therefore made an odd number of operations) it's really only the last number you add that is the "deciding factor".

    Knowing that, you should try to have the smallest number of your array, let's call it a(0), be added by K and a(1) by K-1, a(2) by K-2, ..., a(n) by K-n.

    If (K-n) is an even number you can do it, because for each of the operations before getting to k-n you can just do an even number of operations on each element you change and you are going to end with all elements being ready for an addition.

    Also, performing an addition and right after a subtraction, is going to result in decreasing the element by one, so you just have to add each (K-i) to each a(i) and then remove (K-n)/2, in total, from the elements of the resulting array, distributing it the best way to get the biggest minimum value.

    If (K-n) is odd you won't be able to increase every element of the array, because to do that you need an odd number of operations on each element, but at least one element will necessarily have an even number of operations on it, so the best you can do is make this element the biggest one, a(n), and not add anything to it (instead of decreasing it) then you can add each value from k-n+1 to k to each element from a(0) to a(n-1) and you are gonna have an even number of operations left. Then again, you will remove (K-n+1)/2 from the resulting array in the best way possible.

    If you want to solve D2 you do the same thing, but with some tricks to make it all faster, I can describe them if you want.

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

Can anyone share their solution for C? My approach was to find increasing/decreasing segements of the array and remove all elements of segment exacept endpoints, either my approach is wrong or i failed to implement it properly. Please someone tell how to solve.

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

    You throw away all elemnts but the 1st, nth, and local minimums and maximums.

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

      The idea. |a — b| + |b -c| == |a — c|.

      Only if all values between a and c are >= a and <= c. This can be easily proved using co-ordinates points on a cartesian plane.

      |1 — 3| + |3 — 7| = |1 — 7|.(if it is increasing like 1, 3, 7, ....) Similarly for decreasing sequence

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

    you check checkout this video editorial — here

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

    This approach leads to alot of bugs but I did the same thing:

    https://codeforces.net/contest/1832/submission/205604237

    I had to remove consecutive duplicates for it to work properly

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

Spent last 1 hour 54 minutes doing recursive dp . TLE with memo array and MLE with memo map . Some different idea involved in B ?

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

Class 11 combinatorics revise karlo frandss

(Hint: Use (iv) to create a recurrence for b(n, k))

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

Nice contest! Incase you are stuck on Problem A, Problem B, Problem C. then you can check this video editorial link

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

    Thanks for the such a fast and helpful video editorial ^ ^

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

    Thanks for the video editorial, I will upsolve C. Sure.

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

    Thank you

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

    Thanks for the editorial video. I came up with the solution idea for C, but kept getting WA in test 2. Later realised it had the bug of equal to sign i.e "<=" and ">=". So,I should have ignored duplicate elements.

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

I think arbitrary $$$MOD(1 \leq MOD \leq 10^9)$$$ would have been a better choice for problem E to cut convolution solution.

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

Given that Edu rounds weighs all problems equally, it doesn't feel right for there to be a 2-part problem in Edu round unless the two parts are extremely different in difficulty. In the context of today's contest problem D is essentially weighed double that of problems E/F, which clearly should not be the case.

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

    Thought the same about Codeforces Round 855 (Div. 3) but in contrast, I'd come to appreciate how the final problems of before-then div4s were split... so I ended up not posting about either :P

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

10 minutes after contest, >20 hacks on D :)

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

    even legendary grandmasters are hacked for D1 :(

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

If anyone facing difficulty understanding D1, Please check Tourist's solution. It is very elegant and easy to understand.

solution link

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

We can use convolution to solve problem E.

\begin{aligned} b_i &= \sum_{j = 0}^i \binom{i — j + 1}{k} a_j \\ &= \sum_{j = 0}^i \frac{(i — j + 1)!}{k!(i — j + 1 — k)!} a_j \\ \Longrightarrow \sum_{n \geq 0} b_n x^n &= \frac{1}{k!} \sum_{n \geq 0} \sum_{j = 0}^n \frac{(n — j + 1)!}{(n — j + 1 — k)!} x^{n — j} a_j x^j \end{aligned}

We can take $$$f = \sum_{n \geq 0} a_n x^n$$$ and $$$g = \sum_{n \geq 0} \frac{(n + 1)!}{(n + 1 - k)!} x^n$$$ and $$$\frac{1}{k!}(f * g)$$$ is our desired polynomial. Since $$$n$$$ is huge $$$(n \leq 10^7)$$$, we might want to use fast convolution.

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

What's the hack for D?

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

    Anything with $$$n = 1$$$ that results in a negative answer, for example

    Input:
1 1
1
4

Output:
-1
    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Isn't -1 the expected output for this testcase?

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

        Yes it is, I guess you didn't understand my comment. The original commenter asked what test was used to hack probably 100+ submissions on D and I gave an example. The test isn't a directed hack to their solution (I don't know if their solution got hacked or not), it's just the test that I used to hack multiple solutions. The output I mentioned is the correct output, most incorrect solutions give 0 as the answer.

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

      nvm

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

      Thanks.

      But I still have no idea what was wrong with my case. Maybe, I have some silly mistake (((

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

        UPD:

        O! I've found test case:

        4 7

        1 1 1 1

        1 2 3 4 5 6 7

        Really stupid misprint in my solution

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

Whoever hacked my submission, I hope you have a bad day.

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

Here goes how I solved A to E

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

my submission for B

can someone tell me in which tc does this code fail.

Problem B.

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

    Your approach itself is wrong. You can't greedily choose whether to delete two min elements or one max element, because you don't know about values in entire array so it may be possible that you don't get the optimal answer finally, hence you can't take that decision just based on 2 mins and one max. This brings us to the solution of checking all possible ways to do the operations, but here dp won't be needed as some dependencies are there, like: 1.You will delete 1st two mins always before next two mins 2. You will delete first max always before 2nd max 3. You will always delete k elements

    This brings us to a sliding window protocol solution. At first delete last k elements and find the sum. Then at each iteration, delete two mins and add one max back to the sum and compare with max sum.

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

      I understood that much but still could you give me any tc as i cannot come up with one.

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it 
        Input:
1
8 3
1 1 50 50 50 50 70 101

Correct Output:
200

Your Output:
171
        → Reply
»
19 months ago, # |
  Vote: I like it +62 Vote: I do not like it

Was it intentional to not keep keep negative answers in test cases of D?

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

https://codeforces.net/contest/1832/submission/205606471

can someone tell me the problem with my code for c

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

    What if $$$lst[0]$$$ is $$$0$$$ ?

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

Why doesn't greedy method work for B?

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

I first misunderstood the statement, I thought that the order of operations did not matter( you could do +5 before +3 so basically could do operation j after i and i > j). Is there any way to solve this problem? I thought about it for about an hour but could not come up with anything.

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

    You can solve it using prefix sums and going through all ways.

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

      Could you elaborate? (to be specific, I thought that you could add -1, n , -2 and n — 1 to the same number in the array)

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

The difficulty gap between C and D problems in last 5-6 Div2 Educational rounds is too large imo. It's much more enjoyable to take part in an ordinary Div2 rounds.

Can't say I'll participate in these Educationals anymore.

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

how far is the Purple id ;)

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

Why it is unrated though my rating is still under 2100?

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

    Just be patient, rating hasn't been updated for anybody yet.

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

Editorial please

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

is system testing is proceded?

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

how cound D1 and D2 hacked this much ????

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

    I passed D2, but I got a TLE in D1, which is really frustrating. It really affects my experience.

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

Super strong pretests

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

Very weak pretests for D1 & D2 :( It's not just the negative answers, my submission FST'ed on a tc whose answer is +ve.

PS: I by mistake divided by 2 instead of n at someplace. After changing it, it's AC for D1&2. Frustrating.

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

From almost getting D2 to FSTing on D1, sigh!!

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

rating when

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

    I also want to know

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

      AAAAaaaaaaAAAAAAAAAAaaaaaaaaaAAAAAAAAAAAAaaaaaaaaaaaaaAAAAAAAAAAaaaaaaaaa

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

    It always takes ages after Educational rounds. Might wanna check in like 6 hours or so, unfortunately :(

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

      8 hours now,exactly

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

        Ye it's 8 hours since hacking ended, but we had to wait like 6 hours after that to do the system testing and now we'll wait at least 6 more hours for rating. I agree that it's ridiculously slow — it's almost like someone is manually calculating rating changes in Win95 excel spreadsheet.

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

I've gotten Wa on 44 in D2 because of the corner case n=1.

It's really a nice problem, but I think it'll be better if the corner cases are included in examples or pretests. It's a part of problem for sure, but isn't it a little cruel for us participants?

Actually, in this round, not only me, but also many other participants are truly educated. As for me, I'll check if there exists a corner case before submitting. From this perspective，it's educational enough as an educational round, I think.

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

    For me, I will check the complexity of my code before the end of the competition.

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

    Well corner cases are different for everyone. When I solved D2 (after the contest ended) n=1 wasn't a problem for me. I don't think it is that cruel having this case, as it is quite logical. What IS cruel is NOT including corner cases in the test cases, for example the possibility of the answers to the queries to be negative numbers, which caused so many hacks in D1 and D2. So in my opinion, it is better to have them no matter how annoying they might be for individuals. It is more educational to come up with what is wrong with your solution during the round rather than after, when you are frustrated because of the hack.

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

I solved E in $$$O(n * k^2)$$$ with polynomials. But I saw that a lot of guys solved it with a much simpler idea in $$$O(n * k)$$$. How to do that?

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

    We use the recursion :-

    $$${n \choose r} = {n - 1\choose r-1} + {n - 1\choose r}$$$

    Given:-

    $$$b_n = {n \choose k }a_1 + \dots + {1 \choose k}a_n $$$

    Let us write:-

    $$$b_n = B(n, k)$$$

    Now, observe that (use the {n \choose r} recursion to get this):-

    $$$B(n, r) = B(n-1, r) + B(n-1, r-1) + {1 \choose r}a_1$$$

    This can be solved using DP in O(nk). However, the final solution required some memory optimizations to get accepted.

    My Solution -> 205614318.

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

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

    At this point I am convinced that they're trolling with rating updates on purpose. I think it takes NASA less time to launch a rocket then it takes for Mike and his crew to update ratings.

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

      As Mike said, they can update ratings at any moment. However, they don't do that because they try to find cheaters and remove them

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

    Same, but me waiting for the editorial*

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

When will the editorial be released ??

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

How to solve D?

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

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

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

As a person who needs contribution, please give me some.

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

Candidate master!

Hello, Div.1! (Though it may send me back to expert.)

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

It took me some time to figure out the dp solution to problem E, and it was fun. I made a video editorial if anyone needs help, you can find it here

→ Reply