It's tourist Round.

Why are you getting downvoted?

you are right there.. hattrick done...

how can this normal comment have negative vote?

If I am saying something wrong then feel free to rectify it.

There is no obligation to participate.

This round was the Vk cup final. And all the contestants of this round were GM or above, also they're very well known in CF.

It's highly unlikely that they would leak problems or cheat.

First of all, most of the participants of the final round of this VK cup have written contests for CODEFORCES before. So I think they will respect other contests, if not then the same thing could happen to their contest(by testers or whatever else) and that, of course, is not what an author would want.

What you mentioned is correct, but that round was not based on the final round of another contest, if I'm not wrong it was based on an elimination round.

What you have seen are virtual participants, which are not rated(they joined the contests after it finished).

How do you propose to win using this information?

Download done!

Thought that was gonna be a rick roll lmao

neither, it is for the offical contest.

I think its a lesson for us that we should never_giveup. :p

Congrats never_giveup !!

Amen

Rickroll):

but why

Hi beluga :}

Me too :(

Notice that the insertions put the following restriction on the final sorted array: for some positions $$$k$$$ and $$$k+1$$$ the values strictly differ $$$a_{k} < a_{k+1}$$$. For all other positions, the values might be equal. You have to count the number of such positions because if several insertions happen in the same place, they all contribute to a single restriction. To do so, you can track the current "strict" positions with a treap (it will allow you to increment positions for a suffix).

Given the number of restrictions, let's look at the differences between subsequent elements. Add a 1 to the very beginning of the array and $$$n$$$ at the very end for simplicity. It's easy to see that for positions with restrictions the differences have to be at least 1, for other positions -- at least 0. In total, they should sum up to $$$n-1$$$, as the final element is now $$$n$$$ and the first is $$$1$$$. So, you have to divide $$$n-1-N_{restrictions}$$$ 1-point-differences between $$$n+1$$$ positions. By subtracting $$$N_{restrictions}$$$ we account for the "strict" positions. It is just a binomial coefficient.

Find the minimum number of breaks (let this be $$$x$$$). Now, every swap between A winning and B winning in will increase the number of breaks by 2 (because in the min. number of breaks, either all of A's wins are B's serves or all of B's wins are A's serves). So, we can reach everything in the sequence $$$x, x + 2, ... x + 2k$$$ breaks, where $$$k$$$ is the number of swaps we can make. You need to repeat this for both serving sequences ($$$ABABA$$$ or $$$BABAB$$$).

Fix a K = total number of breaks._ Let K1 = number of breaks for Alice and K2 = number of breaks for Bob. Naturally, we have K1 + K2 = K. Now consider two cases: 1) The total number of games (a.k.a, a + b) is even: we know that the number of games where Alice serves the ball (call it HomeA) should be equal to the number of games where Bob serves the ball (call it HomeB)

HomeA = HomeB
a - k1 + k2 = b - k2 + k1
a - b = 2 x k1 - 2 x k2
k1 - k2 = (a - b) / 2

and you also have k1 + k2 = K, so you could solve these. If k1 or k2 is negative or greater than a and b respectively, then the fixed value of K is invalid. 2) When a + b is odd, you could do the same work but this time, HomeA + j = HomeB where j = {1, -1}

That is how I solved it not sure if there is an easier way to be fair.

Consider a table

             A serve  B serve  Total win
A win        aa       ab       a (given)
B win        ba       bb       b (given)
Total serve  count_a  count_b       

if a+b is even:
   count_a = count_b = (a+b)/2

if a+b is odd: consider two cases
   count_a = (a+b+1)/2, count_b = (a+b-1)/2 
   count_a = (a+b-1)/2, count_b = (a+b+1)/2

• You consider all possible values of aa which is between 0 to count_a inclusive.
• For each possible value of aa, you can fill out the rest of the matrix like how you fill up a Sudoku.
• The assignment is valid if all four entries are non-negative.
• For each valid assignment, add k = ab + ba to the result
• If a+b is odd, you consider the two possible set of values count_a and count_b could have.

At least you solve B.

+1

i did binary search

First of all, you have to find maximum one for every group. While finding maximum our heroes power should be at least:

armor of monster — index of monster.

after this, you should sort values of maximums and start from minimum one. if maximum in this group is bigger than answer increase answer

same.. the problem statement of B was quite confusing to me :(

Mark multiples instead of checking factors. At a position $$$x$$$ for a given multiple $$$k$$$, we want to add $$$ans_{x}$$$ to all possible $$$y$$$ where $$$x = \lfloor \frac{y}{k} \rfloor$$$. This is just the range $$$[x \times k, (x + 1) \times k - 1]$$$. We can mark this range using a difference array by adding $$$ans_{x}$$$ to $$$diff_{x \times k}$$$ and subtracting it from $$$diff_{(x + 1) \times k}$$$.

Now when we arrive at a pos $$$y$$$ we add $$$diff_{y - 1}$$$ to $$$diff_{y}$$$ to get the corresponding value added using multiples. Now we just add this to $$$ans_{y}$$$.

Total complexity is $$$O(1)$$$ per multiple, so $$$O(n logn)$$$ total.

$$$n=4*10^6$$$ was too large for $$$O(n^{3/2})$$$. Soln I wrote gets tle for $$$4*10^5$$$.
Regarding memory constraint, to me, it seems it was to stop precomputations of all factors of numbers using $$$O(nlogn)$$$ sieve.
But still, it was imo a bad attempt since one can just compute all factors on the go using prime factorization.

//spf[n] is one of prime factor of n.
void getAllFactors(vi &fac,lli n){
    fac={1};
    while(n>1){
        const lli p=spf[n];
        vi cur={1};
        while(n%p==0){
            n/=p;
            cur.pb(cur.back()*p);
        }
        vi nf;
        for(auto x:fac)
            for(auto y:cur)
                nf.pb(x*y);
        nf.swap(fac);
    }
}

Yes, that's what I did.

To calculate x, you can go backwards through the swaps, keeping track of the remaining indices with a BIT.

B was a slightly more difficult than normal, but D was miles easier than usual. You get something — you lose something. :P

the distance between the max value and the entrance of the cave matters, you can't just sort by max value

add spoilers to your code as well

Just implement it. (max number of iterations <= n * 2)

I will never play tennis for sure after this

C was easier than B

I see a few submissions like that, they will be fixed after system testing is done.

video solution for Div2 C, I'll upload my solution for Div2 D as well soon.

Update — Video solution for Div2 D

pretests were strong i guess

You can't lock simplified version until u solved not simplified, can you?

Hey,it so happened that my solution to problem C matches quite a lot with the one by another user. However, the code I submitted and the solution idea were completely mine and I hadn't taken help of even any online source (let alone copying someone's solution.) Also, regarding the ide part,I use codechef ide to code my solutions and those can only be viewed by signing in to my codechef account,so there was no leakage of code from my side atleast. Also,my solution was pretty basic and short ,so there is a high chance that it matches with someone else's code. The message I received said that if I have a conclusive evidence that the coincidence could have occured due to using some code published online before the contest,I can post those details as a comment to this post...but since, I hadn't used any online source to write my code, I have no idea how to prove my honesty except for the fact that the solution was too basic. I can also completely explain my solution if required. Also,due to this my rating was rolled back and this hurts even more since this was my best contest till now and I had crossed 1800 for the first time but now,I feel that I have been deprived of those rating points despite no fault of mine. So, I humbly request you to consider my participation in this contest valid and grant me the delta I deserved.

It seems that you've removed some of the cheaters.But why haven't the ratings updated again yet?

My Video Solution for D

Yes, I upsolved Div2 D1 problem using lazy segment tree implementation from the atcoder library:

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>

using namespace std;
using namespace atcoder;

int n, m;

// Lazy segment tree, which supports "sum of elements modulo m" queries
// and "add constant to a range of elements" updates.

struct S { int sum; int n; }; // 'sum' of 'n' elements
struct F { int c; };          // f(x) = x + c

S op(S x, S y)          { return S{(x.sum + y.sum) % m, x.n + y.n}; };
S e()                   { return S{0, 0}; };
S mapping(F f, S s)     { return S{(int)(((long long)f.c * s.n + s.sum) % m), s.n}; };
F composition(F f, F g) { return F{(g.c + f.c) % m}; };
F id()                  { return F{0}; };

int main()
{
  cin >> n >> m;
  vector<S> arr(n + 1, S{0, 1});
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(arr);

  seg.set(1, S{1, 1}); // arr[1] = 1
  for (int x = 1; x <= n; x++) {
    int ans = (seg.prod(1, x).sum + seg.get(x).sum) % m;
    seg.set(x, S{ans, 1}); // arr[x] = ans
    for (int z = 2; x * z <= n; z++)
      seg.apply(x * z, min((x + 1) * z, n + 1), F{ans});
  }

  cout << seg.get(n).sum << endl; // arr[n]
}

The lazysegtree header file can be copy/pasted into the source code. It's fast enough for D1 126922899, but fails with TLE on D2 126922883. I need to check the editorial to see if anything can be improved or it's a dead end.

Never use the "=" sign in comparator functions Reason

Actually it can influence.

A C++ comparator should return false when elements are equal, otherwise you can get a number of different verdicts (RE, TLE, WA and sometimes even MLE). (should be a.second > b.second, not a.second >= b.second)

I haven't recieved any reply from codeforces yet...maybe i didn't post my clarification where I was supposed to...can someone help? Do I have to post it as a seperate blog post or something?

All the problems are available in the problemset section, the problems from Div. 1 are just a bit further down the list.