Wind_Eagle's blog

Codeforces Round #861 (Div. 2)
By Wind_Eagle, 20 months ago, translation, In English

350-20230320195909

Hello, Codeforces!

I am very glad to invite you to the Codeforces Round #861 (Div. 2), which will take place in Mar/29/2023 12:05 (Moscow time). This round will be rated for the participants with rating lower than 2100.

My sincere thanks to:

You will have 2 hours and 30 minutes for solving 6 tasks, one of which will be divided into easy and hard verions. The round is based on the problems from the Belarusian National Olympiad. We kindly ask all Belarusian students who participated in this olympiad, to refrain from taking part in this round and discussing the problems publicly before the round ends.

I hope you will enjoy the round!

Round testers (will be available later): Ormlis, 4qqqq, nnv-nick, olya.masaeva, Makcum888.

Preliminary score distribution: 750-1000-1500-2000-2500-3250.

UPD: the round was rebalanced. You will have 2 hours for solving 5 tasks, one of which will be divided into easy, medium and hard verions.

Score distribution: 750-1000-1500-1750-(1750+1000+750).

Editorial: https://codeforces.me/blog/entry/114523

Winners:

Div. 1 + Div. 2:

1) BurnedChicken

2) maspy

3) happylmb

Div. 2:

1) happylmb

2) Cherished

3) 2021_yes

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

Comments Comments (199)
| Write comment?
»
20 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Belarusian National Olympiad <3

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

    Why not Div. 1 / Div. 2? Is the final stage of Belorussian National Olympiad so easy?

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

Please more contests at this time

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

    Please no more contests at this time.

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

      We have to set this round at such time because original olympiad ends in 12:00 SET.

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

    If you are in Italy, the usual time is not even bad for you. Please be considerate for the poor people who have this one at 5AM :)

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

    I agree, it's 5PM for me, really good

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

    For me who live in Korea, Both contests are good 09:05 UTC -> 18:05 GMT+9 14:35 UTC -> 23:35 GMT+9

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

    It's 17:05 CST (UTF+8). Great for Chinese users.

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

Notice the unusual time

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

One more raid on cheaters?

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

what's that image in the post about?

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

    There is a meme in russian community. If you wanna check it, you can google it like "случай в казино".

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

    It's a hint for one of the questions ;)

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

    The rating of people that didn't participate in the Belarusian National Olympiad

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

I don't know why but the meme is so relatable to my current situation :)

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

Rating change in the image seems terrible :dead:

Something SUS!

Anyways!
- Notice the unusual time everyone!
- Hopefully everyone gets +ve delta (make the image state false).
- Hoping for a balanced round :)

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

The length of the contest in the post differs from that shown in the contests tab

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

Last time I managed to upsolve A1-D. I hope I can perform well today too and become specialist again!

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

Is it 2.00 hours contest or 2 hours 30 minutes contest?different contest duration were given in blog and contests section

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

For those who don't know https://www.youtube.com/watch?v=3dYRN1rtncA

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

Hope to get CM this time

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

could the timings be shifted to the normal timings, not a conducive time to conduct contests

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

Does the picture imply that this round will be the next big milestone in my downward trend in rating?

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

OMG 750 A and unusual time round!

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

    I think my new dp predicts my future rating graph

    Best of luck everyone!!

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

Hoping to have a balanced round !

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

College viva or codeforces contest ＞﹏＜

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

The rating graph in the meme is opposite!

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

Hello Wind_Eagle,

I just found a typo in the blog where you say "divided into easy and hard verions." Although it is a minuscule one (of course, we are humans) but it would be nice to be corrected. BTW, I love your rounds and hope that this round would be fun for everyone too <3.

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

TT first time finally to participate in a CF round this early hahaha. I stayed up late in the dorm till midnight most of the times. Good luck guys!!

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

Score distribution is really interesting.

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

Now it's not a joke

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

Unusual time but hope for a positive delta rating.

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

omg 3 version E round

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

Am I the only one who noticed that master is above international master on the graph?

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

Expect three versions of E and hopefully increase ratings.

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

Go to Pupil bruhh

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

Wishing everyone the best possible work!

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

This is my first contest on codeforces, can someone give some tips to do good on codeforces.

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

    Just do your best. Don't give up during the contest (This is what I used to do). No problem is hard and if others can do it then you can do it too.

    Best of luck =)

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

      Thank You :)

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

      well!! , i suck :(

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

        Hey! don't be sad, this was a tough contest indeed for everyone. I and every other cper started like this. This is the time when you should learn from your mistakes to avoid them in future, not to be sad. We are with you. Just practice as much as you can.

        (BTW, I would recommend you to solve easier problems first then move on to the harder ones. As I stated before, you should not skip problems until you have given it your best.)

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

The rating graph seems like a warning to me. Anyway, I'm still gonna appear for it.

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

will E3 >3000 ?

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

He said: The round is based on the problems from the Belarusian National Olympiad. We can ask the Belarusian students who participated in this Olympiad or find the solution in anywhere. So, I think this contest should be unrated because everyone can search the problem in Google (?).

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

    No, they happen in the same time.

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

Good luck & Have fun!

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

hope to be Expert:D

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

The Hardest problems in Div. 2 I've ever seen.

Hardforces :(

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

    Belarusian students had no problems with solving C. Half of the students successfully solved this task.

    I couldn't imagine this task will be so hard.

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

      I think it is not hard in general, it is just hard to come up with a solution fast in my opinion.

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

      Which problems did belarusian students get on a contest from the Round?

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

ahhh

160858923d467feaaa9de5c134246a22

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

What do those Belarusian students eat?

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

This contest was held at 4 am for my timezone, I tried using segment tree for A and fenwick tree for B before I came to my senses xD

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

Test case 4 of Problem C irritated me in the whole contest

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

How to solve B? Can anyone help.

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

    Hint: I solved it by sorting each column and using prefix sums

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

      Ohh ok just now i just sorted it and got the ans. But why won't it work if i don't sort it?

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

        Think about the case like:

        4

        6

        2

        We can't discern between the 6 and 2 because they give the expected value of 8. So we need to take the sum of all numbers higher than the value ahead of it and also the sum of all numbers lower than the value ahead of it. We can solve this problem by sorting so that there are no lower numbers in front of it.

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

How to solve c? I can only think of digit dp Here is the wrong submission

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

    There are two cases depending on the lengths of the numbers: 1. if the lengths aren't equal, you can spam 9s. 2. if the lengths are equal, find the common prefix(you can't change that part no matter what) and brute force the next two digits. You're answer will be something like common_part + x + spamming y's until you fill the length of the number. There won't be much candidates for the answer so you can check all of them.

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

      Can you tell me why you have considered 2 digits, not 3 or 4?

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

        Dunno, just observed it. If I have to give a concrete reason, probably because two digits are enough to set a min/max digit for a number. Even if we choose three digits — x < y < z — that would be useless, because we can just choose x = y.

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

          I understand that we only need two digits for min/max. But do you have any reason why we don't need more than 2 digits for the purpose of the number being in between l and r?

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

      I combined not equal length part of your solution and for euqal i applied digit dp. It Worked now, but still dont know why dp didnt worked for non equal length.

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

      Thanks

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

    You can break the problem col wise. Observe the pattern.

    Hint1: Try to find contributions of each element to the ans.

    Hint2: the solution involves sorting.

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

    You can use a greedy approach. You first try to create number with luckiness = 0, then 1, 2... To find number with luckiness = k, you can try out all intervals [i, i + k] where 0 <= i <= 9 — k You stop as soon as you find one

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

    if l and r have different length, the answer is '9' * len(l). Else let i be the first position where l[i] != r[i] (I'm thinking of l and r as strings). We can bruteforce the digit on i-th position (l[i] <= d1 <= r[i]), and then fill the suffix with a single digit d. Then we just compare the numbers. Let our number be m. If l <= m && r <= m, we update the answer

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

      thanks , i liked this approach

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

      thanks a lot sir . could u please tell why this approach works

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

        I don't really know why, just feels like it should work

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

    Although all the greedy solutions explained here are probably correct, I will explain how to solve it using digit dp.

    dp[n][mx][mn][t] -> largest number consisting of max n digits, having max digit mx, min digit mn, and tight t. After you compute the dp till r, you look for the number with minimum difference mx — mn, that also is bigger than l. The implementation is pretty tedious though.

    Code

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

      Hey , i also coded digit dp, my states were [idx][small][big][put][max][min], can u tell if i did something wrong there?

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

    My solution uses digit DP approach: https://codeforces.me/contest/1808/submission/199670890

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

Maybe we can consider this round as Div1.5...2 hard 4 me.

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

was b is a copy from this:

https://www.geeksforgeeks.org/sum-absolute-differences-pairs-given-array/ i know here we compute the abs on a matrix but isn't it just a little different? ( since we can consider every column just an array)

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

My $$$O(4 \cdot k^2 \log n)$$$ solution is giving me TLE on E3 :((

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

Would be nice if this round lasted for 3 hours instead of just 2

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

    Agree! Or at least 2.5 hours as originally planned.

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

Amazing contest, E problem is really cool!

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

Hardest C I've ever seen :(

I spend more than a hour to solve it.

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

This round motivated me to solve more problems ;)
How to do A? i tried and i'm getting tle.

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

    Just run a loop from l to min(l+101,r) and check each in range :D

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

      Can you please explain why the loop is till min(l+101,r)?

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

        because it's guaranteed that you can get a number with final two digits '90'

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

      Another approach for A link

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

Got 10 wrong answers on D,really keen to know what went wrong.

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

Loved problem D! very educational problem

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

Mathforces

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

Here is my code of problem B, but it got wrong in the pretest3. How can I modify it? Thanks:)

#include <bits/stdc++.h>
using namespace std;
vector<int> vec[(int)3e5+5];
#define ll long long
int main(){
    int _;
    cin>>_;
    while(_--){
        int n, m;
        cin>>n>>m;
        ll ans=0;
        for(int i=0;i<n;i++){
            vec[i].clear();
            for(int j=0, tmp;j<m;j++) cin>>tmp, vec[i].push_back(tmp);
        }
        if(n==1) {cout<<"0\n";continue;}
        if(n==2) {
            for(int i=0;i<n;i++) ans+=abs(vec[i][0]-vec[i][1]);
            cout<<ans<<'\n';
            continue;
        }
        for(int i=0;i<m;i++){
            vector<int> tmp;
            for(int j=0;j<n;j++) tmp.push_back(vec[j][i]);
            stable_sort(tmp.begin(), tmp.end());
            if(n==3) ans+=tmp[0]*(-2)+tmp[2]*2;
            else {
                ll X = -(n-1);
                for(int j=0;j<n;j++) ans+=tmp[j]*X, X+=2;
                //ans+=tmp[0]*(-(n-1))+tmp[1]*(-(n-3))+tmp[n-2]*(n-3)+tmp[n-1]*(n-1);
            }
        }
        cout<<ans<<'\n';

    }
    cout<<endl;
}
→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, there is something wrong in your if (n == 2). Then, maybe your solution ans+=tmp[j]*X, X+=2; is wrong.

    You can remove the unnecessary special judgement, and reverse the vector dimension for convenience. As you did, you can sort and then let sum be the prefix sum and when get the answer for $$$j^{th}$$$ person, just ans += v[i][j] * j - sum.

    Sorry for my poor English. :)

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

    Maybe my code can help.199651953

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

Problem 1808D - Petya, Petya, Petr, and Palindromes can be solved in $$$O\left(n \cdot k\right)$$$ on GCC with auto-vectorization in $$$795$$$ ms. You can compare left half of segment with reversed right half of segment. AC submission from contest

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

    How did this got AC? This should TLE!

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

      Deleted

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

        Damn bro, from where can I learn all of this. By this way, we can solve many problems with larger time complexities too right.

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

WA on pretest 4 for 4 times on problem 4

OMG

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

Problem C , 123 lines get WA on test#2 ^_^

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

Nice registration count. Haven't seen anything like this before.

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

Wonderful round with interesting problems

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

In A, why is the correct answer for the test case l=r=6 equal to 6? The largest digit of 6 and the smallest digit of 6 is equal to 6, so the answer should be 6-6 =0. Same goes for all numbers m such that 1<=m <= 9.

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

    because you asked to output the luckiest number, not the amount of luck

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

      Thanks!

      My brain completely bricked. I had if r<=9: return 0 in my code the entire time and I didnt even consider that to be an issue.

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

    Output the number,not its luckiness.

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

Could someone shed some light on how rating delta is calculated when the first problem is harder than usual? For participants who couldn't solve first problem, they are not considered to be in the contest, and this reduces the total number of effective participants.

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

Solved A-D. Unusual time and unusual difficulty.

A: For any 100 consecutive numbers, there must be a number end with "09" and it will reach the maximum luckiness (9). So we can let r=min(r,l+99) and solve by brute force.

B: For 1<=j<=m, consider the contribution of the j-th number on each card. We can sort all n j-th numbers, and the contribution of i-th number is ((i-1)-(n-i))*c[i].

C: Let t be the number we find, and assume L<t<R (we can do this by let L=L-1, R=R+1), then there must be a number d that d satisfies floor(L/10^d)<floor(t/10^d)<floor(R/10^d), but d+1 doesn't. Then we know that floor(L/10^(d+1))==floor(t/10^(d+1)) or floor(t/10^(d+1))==floor(R/10^(d+1)). First assume floor(L/10^(d+1))==floor(t/10^(d+1)), then if we know d, we can know (d+1)-th, (d+2)-th, ... 19th digits of t, and we can try for every possible d-th digits and check if floor(t/10^d)<floor(R/10^d). If so, we can assign (0~d-1)-th digits of t to the d-th digit (which means, the (0-d)-th digits of t are the same), and let it be a candidate answer. Similar for assuming floor(t/10^(d+1))==floor(R/10^(d+1)). Therefore, by considering all possible value of d and d-th digit of t, we can get at most 2*19*10 candidate answers, and we just need to check them to get the final answer.

D: Denote r=(k-1)/2. We need to count pairs of (i, j) such that:

  • i<j and j<=i+2*r and (j-i)%2==0.

  • a[i]!=a[j].

  • let mid=(i+j)/2, then 1<=mid-r<=mid+r<=n.

We can change the 2nd condition to a[i]==a[j] and subtract it from (n-k+1)*r. We store the positions of occurences of each number into different buckets (we need to store odd and even positions separately), and for each j we find the number of valid i by binary search.

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

    how binary search in D is applicable ..plz explain.

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

      using upper_bound(all(v),R)-lower_bound(all(v),L) to find the count of numbers in range [L, R] in a sorted vector v.

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

    I use quite the same idea as yours for problem D but got wrong answer. Any idea why?

    199778993

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

199684592 any idea why it gives Run Time ?

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

    stoll instead of stoi ?

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

      Yes, this stupid silly mistake cost me penalty

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

In problem C, many solutions are giving wrong output on the test case 1 1000000000000000000 1000000000000000000 such corner test cases should have been there.

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

A=B<<<<<<<<C=D

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

what is intended complexity of E2?

I assume it is k^3 * logn, because limits seems to dictate that, yet my solution of k^3 logn had to be optimized several times before fitting in TL with a pragma, and finally getting uphacked :(

If intended was k^3 logn, you could have relaxed the limits quite a bit, i think.

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

Can someone help debug this solution of D- 199696312 ,there is something wrong with implementation and i can't figure it out.

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

How to solve D ? Can anyone please explain in simpler way ?

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

    Consider all the possible pairs of (i, j) that may be different which would result in a +1 in the answer, minus the pairs such that a[i] = a[j] and you will get the pairs that a[i] != a[j], you can calculate the a[i] = a[j] part using a vector and binary search, and the total number is the same as (n — k + 1) * (k / 2)

    Here is my code, maybe looking at it is a lot more simple R199691512

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

Nice round! though D is a bit too similar to ABC290E

But I wrote a useless line of code but it resulted in an RE in final tests in D :( droped from ~100 too ~200 in rank, so sad ...

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

Another C solution, in $$$O(t \cdot 2^{10} \cdot 18)$$$

Let's implement function next_mask(x, mask) ($$$mask$$$ is the mask of the digits from $$$0$$$ to $$$9$$$) which return smallest integer $$$y$$$ such that $$$y \geq x$$$ and all digits of $$$y$$$ are in $$$mask$$$

It can be implemented by bruteforcing prefix of $$$x$$$ that will be same in $$$y$$$ and then putting smallest digits from $$$mask$$$ in the remaining suffix but you need to be careful with corner cases.

So for actual solution we just bruteforce all $$$masks$$$ and check whether next_mask(l, mask) is not bigger than $$$r$$$ and relaxing answer. Code: 199692880

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

    Instead of iterating through all of the masks you can just iterate through the pairs of minimum and maximum set bits in the mask and then build the answer.

    I did something similar, but instead of constructing the answer I did digit dp. Code: 199704153.

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

Nice round.

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

What about the cheater raid this time?

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

![ ](ruban)

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

First I appreciate all the time and efforts for all the contributors to this round for the interesting problems.

There was just a little bit of confusion to me since E1/2/3 was nothing more than an inclusion-exclusion + binomial theorem. To me it just didn't fit 3s of TL and only range <= 2000 for parameter k, which made me thinking of some other complicated algo till near the end of contest.

I'm just curious that were the constraints set so by design or by carelessness?

(I meant no offence to anyone that made this round possible, I'll apologize if I did so unknowingly = =

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

    For E2 we have two solutions for $$$O(k^2 + \log(n))$$$ and it is easy to optimize this solution to $$$O(k + \log(n))$$$. It make no sense if we setted constrains for $$$O(k + \log(n))$$$. That's why we set $$$k \leq 2000$$$

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

      please see this 199700596

      it is based on similar technique to derive the closed form of answer, and it runs in $$$O(\log k + \log n)$$$, I guess

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

        We know about this solution :)

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

      So what's the solution can pass for k<=100 but can't pass for k<=2000? I can only come up with O(k+log(n)) solution.

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

        Well, there's $$$O(k^3 \log n)$$$ (or $$$O(k^2 \log k \log n)$$$ with fft). For each total sum (k options) find the number of sequences with this particular sum that are bad. And subtract it from $$$k ^ {(n-1)} $$$ (amount of sequences with any fixed sum).

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

[deleted because of mistaking a powerful person for someone else]

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

    I am glad to be mentioned.

    I am struggling for this problem for a very long time. Then I realized that, an integer with the suffix that all number are same will never make the answer worse.

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

Maybe change the allowed runtime in problem D to 1 second? a lot of wrong solutions are passing: https://codeforces.me/contest/1808/submission/199698146

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

    It's really hard to hack.

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

    Better to increase limitation for $$$N$$$ and $$$K$$$ to $$$300000$$$, because changing TL is linear function, but changing of limitations is quadratic function.

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

Thanks to this round which make me be CM finally :)

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

seems that there exists $$$O(k)$$$ and $$$O(\log n)$$$ solutions for E......

$$$O(k)$$$ solution: https://codeforces.me/contest/1808/submission/199658264

$$$O(\log n)$$$ solution: https://codeforces.me/contest/1808/submission/199673882

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

In problem D, I was trying an approach similar to https://atcoder.jp/contests/abc290/tasks/abc290_e with some modifications but I cannot understand what's going wrong. Can someone explain? https://codeforces.me/submissions/SamyakSinghania

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

Thank you for Problem C. Refreshed my digit dp practice.

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

Nice Round! I think the problems were great, if you find yourself stuck on A,B and C then maybe these tutorial videos could help you out — Problem A, Problem B, Problem C video tutorial

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

Really nice contest. I personally liked the problems a lot. A little different than the normal div2 rounds. I loved it. Duration could have been more.

It's good to know that I am not the only one who used segment tree for problem A :)

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

    I used sparse table for problem A

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

Nice balance of round

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

Any predictions of E1,E2,E3 rating?

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

weird E xd

if (n == 1) { cout << '1'; return; } if (k % 2) cout << (poww(k, n) — poww(k — 1, n) — poww(-1, n) * (gcdd(n — 2, k) — 1) + m) % m; else k /= 2,cout << 1ll * poww(2, n — 1) * ((poww(k, n) — poww(k — 1, n) — poww(-1, n) * (gcdd((n — 2) % k, k) — 1) + m) % m) % m;

(poww means pow and gcdd means gcd) luckily didn't participate today or collapsed maybe lol

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

Why are the constraints on E3 so low? IMO, anyone who can get a solution that's $$$O(k^2\log n)$$$ should also be able to get the $$$O(\log n + \log k)$$$ one...

(not to say that E3 isn't difficult as is, it took me at least an hour of work after contest to solve it, haha)

Fast: 199736258 Slow: 199729972

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

Problem C:

if l and r not same number of digits, fill l with 9 and return.

if same number of digits, first find max common prefix. After that, brute force the next digit d, which is the first digit that l and r differs.

  1. if we choose digits_l[d] < digits[d] < digits_r[d], then obviously just greedily fill the rest with digits[d].

  2. if digits_l[d] == digits[d], then if we know the max_digit, we greedily fill everything after d with max_digit.

  3. if digits_r[d] == digits[d], similarly, fill everything after d with min_digit.

Thus, just brute forcing the next two digits is enough.

Edit: Formatting

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

Can anyone help me debug why my Digit DP solution is not working?

My Solution

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

Here's how to solve problem E in $$$O(\log n+\log k)$$$:

First, handle the special cases with $$$\min(n,k)\le 2$$$. Now assume this is not the case.

In a lucky number, call a digit "special" if it is equal to the remainder when the sum of all other digits is divided by $$$k$$$. Then, we will enumerate all lucky numbers by the location of their first special digit.

Suppose $$$k$$$ is odd. If the first special digit is not the last digit, say it is $$$a_i$$$ in the number $$$\overline{a_1 a_2\ldots a_n}$$$ then there are $$$k-1$$$ ways to choose each of $$$a_1$$$ through $$$a_{i-1}$$$, $$$k$$$ ways to choose each of $$$a_i$$$ through $$$a_{n-1}$$$, and then the value of $$$a_n$$$ is uniquely determined to force $$$a_i$$$ to be special. The sum of the number of lucky numbers with first special digit at index $$$i$$$ over all $$$i$$$ between $$$1$$$ and $$$n-1$$$ is $$$k^{n-1}+k^{n-2}(k-1)+k^{n-3}(k-1)^2+\ldots+k(k-1)^{n-2}=\frac{k^n-(k-1)^n}{k-(k-1)}-(k-1)^{n-1}$$$.

To count the number of lucky numbers whose first special digit is $$$a_n$$$, notice that if the first $$$n-1$$$ digits do not contain $$$a_n$$$, we can decrease each of the first $$$n-1$$$ digits by $$$a_n$$$, so that the first $$$n-1$$$ digits don't contain 0 and sum to $$$(2-n)a_n$$$ (all operations are mod $$$k$$$, of course). Using the roots of unity filter on the polynomial $$$(x+x^2+\ldots +x^{k-1})^{n-1}$$$ (or alternatively just using small cases to guess a pattern), we can compute that for each possible value of $$$a_n$$$, if $$$(2-n)a_n$$$ is a multiple of $$$k$$$, then there are $$$\frac{(k-1)^{n-1}+(k-1)(-1)^{n-1}}{k}$$$ lucky numbers whose first special digit is $$$a_n$$$, and otherwise $$$\frac{(k-1)^{n-1}-(-1)^{n-1}}{k}$$$ lucky numbers whose first special digit is $$$a_n$$$. There are $$$\gcd(n-2,k)$$$ possible values of $$$a_n$$$ that fall into the first case, and others fall into the second case, so we can add them to $$$\frac{k^n-(k-1)^n}{k-(k-1)}-(k-1)^{n-1}$$$ to get the answer.

The k even case is similar, only that now if $$$a_i$$$ is the first special digit, then $$$a_i+\frac{k}{2}$$$ also cannot appear before $$$a_i$$$. We get that there are $$$\frac{k^n-(k-2)^n}{k-(k-2)}-(k-2)^{n-1}$$$ lucky numbers whose first special digit is not $$$a_n$$$. Using the roots of unity filter again on $$$(x+x^2+\ldots+x^{\frac{k}{2}-1}+x^{\frac{k}{2}+1}+\ldots+x^k)^{n-1}$$$, we know that if $$$(2-n)a_n$$$ is equal to $$$0$$$ or $$$\frac{k}{2}$$$, then there are $$$\frac{(\frac{k}{2}-1)(-2)^{n-1}+(k-2)^{n-1}}{k}$$$ lucky numbers whose first special digit is $$$a_n$$$, otherwise there are $$$\frac{(k-2)^{n-1}-(-2)^{n-1}}{k}$$$ lucky numbers whose first special digit is $$$a_n$$$, and the first case covers $$$2\gcd(n-2,\frac{k}{2})$$$ values of $$$a_n$$$.

My submission which actually runs in $$$O(\log m+\log k)$$$ using Fermat's Little Theorem: https://codeforces.me/contest/1808/submission/199734771

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

    Is this solution worth rating 2800? I think that the problem is overrated..

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

Finally reached pupil after 39 contests.

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

How to solve E2/E3?

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

Why is this solution accepted in problem C?

I'm not sure about the time complexity of the solution, but it was not hacked. Could anyone hack it or explain why it's correct?

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

Editorial when?

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

Can anyone explain the idea to solve C, I did see a lot of solutions but none of them really helped to get to the intuition.

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

    The task C can be solved without DP. The key idea is constructing an answer number, trying to use the same value as at the previous index.

    Submission: https://codeforces.me/contest/1808/submission/200894232

    Let's cover edge cases first.

    1) if l == r, return l.
2) if l.ToString().Length < r.ToString.Length, return 999..999 of size of l.
    l =  123456
  ans =  999999
    r = 1234567

    Considering l and r, as arrays of integers in range [0..9]: we have l and r of the same size and at some index i, where r[i] > l[i].

    The value in the answer (array ans) at index i should be in range [l[i]..r[i]].

    So let's go over all possible values for ans[i] and for each of them check all the possible endings, constructed using a single digit.

           v
l = 1236**
     ...
    123699
    123700
     ...
r = 1237**
       ^
       i

    Can be implemented like that:

    for (var ansI = l[i]; ansI <= r[i]; ansI++)
{
    for (var end = 0; end <= 9; end++)
    {
        ans[i] = ansI;
        for (var idx = i + 1; idx < ans.Length; idx++) ans[idx] = end;
        // check that ans has lower luckiness, save it if it is the case.
    }
}
    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you prove the part where size of L == R?

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

        When I thought about proving the solution, I found an even simpler solution. I will update my previous post. If you visually imagine all possible answers and L and R as lines on the same graph you can find it obvious.

          ^
  |-------------- a4: 123577 - X
  |============== R : 123574 ========
  |-------------- a3: 123566 - ?
  |                    ...
  |-------------- a3: 123500 - ?
  |-------------- a2: 123499 - ?
  |                    ...
  |-------------- a1: 123477 - ?
  |============== L : 123469 ========
  |-------------- a0: 123466 - X
--+---------------------------------->
  |
        → Reply
»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Wait somehow C is 1900 and D is 2100. Feels like D is actually much easier.

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

A good contest!

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

Wind_Eagle Why not make $$$N$$$ $$$K$$$ larger, like $$$300 000$$$ in $$$D$$$?

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

    Wanted to allow n * sqrt(n) pass. Didn't notice that nk with avx can get AC.

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

      Can you kindly tell how can we do this avx thing. (By the comment it seems like some runtime optimization trick but I am not sure)

      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
        #pragma gcc target("avx")

        This line allows compiler to use avx assembly instructions. These instructions use vectorization and can do monotonous tasks faster, for example, do this code four times faster:

        for (int i = 0; i < n; i++) {
  b[i] += a[i];
}
        → Reply
»
20 months ago, # |
  Vote: I like it -23 Vote: I do not like it

I was just warned by the Codeforces system because my Problem C code is the same as someone else's. It's obvious that the reason is that I live-streamed the contest and some viewers copied my code. I want to ask if there is any way to avoid being plagiarized if I have to live-stream, or is live-streaming on Codeforces completely prohibited? But I always see some Grandmasters live-streaming on Codeforces.

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

    Live streaming is a flagrant violation of the rules. You can publish a screencast AFTER the end of a round.

    → Reply