Belarusian National Olympiad <3

Belarusian National Olympiad <3

Please more contests at this time

Notice the unusual time

The graph is opposite!

Почему у вас на картах бубны чёрные?! Почему на карту если с разных сторон посмотреть, то там или шестёрка, или девятка? Вы их в киосках заряжаете, что ли?

One more raid on cheaters?

what's that image in the post about?

Rating change in the image seems terrible :dead:

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

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

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

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

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

Hope to get CM this time

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

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

Эта картинка идеальна...

OMG 750 A and unusual time round!

Hoping to have a balanced round !

College viva or codeforces contest ＞﹏＜

The rating graph in the meme is opposite!

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!!

Score distribution is really interesting.

Now it's not a joke

Unusual time but hope for a positive delta rating.

omg 3 version E round

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

Expect three versions of E and hopefully increase ratings.

Go to Pupil bruhh

Wishing everyone the best possible work!

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

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

will E3 >3000 ?

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 (?).

Good luck & Have fun!

hope to be Expert:D

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

Hardforces :(

ahhh

What do those Belarusian students eat?

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

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

How to solve B? Can anyone help.

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

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

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)

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

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

Amazing contest, E problem is really cool!

Hardest C I've ever seen :(

I spend more than a hour to solve it.

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

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

Loved problem D! very educational problem

Mathforces

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;
}

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

WA on pretest 4 for 4 times on problem 4

OMG

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

Debug long time for C. In the end, I found that there may be overflow in my solution, but I have no time to change. :)

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

Wonderful round with interesting problems

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.

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.

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.

199684592 any idea why it gives Run Time ?

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

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

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.

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

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

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 ...

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

Nice round.

What about the cheater raid this time?

![ ]()

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 = =

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

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

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

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

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

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

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.com/submissions/SamyakSinghania

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

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

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 :)

Nice balance of round

Any predictions of E1,E2,E3 rating?

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

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