Why do all residents of Kazakhstan like La Liga?

El Clasico clashes with CF #519, not other way around :(

Leo messi is injured, so he has chance to get a hoodie :))

El clasico has started

FCB stands for something else. ;)

0.044 is not bad percent :P good luck wish you the best

Email is wrong a bit, this is going to be a combined round.

If a red said this would it still be -22 contribution dont be rankist!

Congrats Michael!

He´s polish

What would happen if some concestants share the place and it would be choosen by generator?

Why was seed not taken as max points by winner in this contest? Any reason?

but is it determined?

1. Is it normal, that randgen.cpp can give number less than 20? For example, with seed 1234, it give 17.

2. There is invalid syntax in get_ranklist.py in line 59. My python don't now —

There will be 3 parallel contests, which's score will be the seed?

I'll hack you down!

football is for monkeys :D

Also in F. It is pure gold indeed.

Maybe this strategy will help: https://cs.stackexchange.com/questions/10249/finding-the-size-of-the-smallest-subset-with-gcd-1

it can be observed if the answer exists, then it's no more than 7. For each possible answer, check if it's valid by Mobius inversion.

I built a graph where each vertex is a product of distinct primes and there's an edge from a product to a subset-product whenever there is an input number coprime to the subset-product. How many input numbers are there coprime to x? That can be computed using inclusion-exclusion (you need to compute how many are divisible by each number first).

first the do the basic checks and also remove duplicate primes in each number. For each value in 1 to 300000 count number of numbers which have gcd!=1 with that value(lets call gg[val])(using mobius function this is easy). Now we can construct graph with edges between two numbers(x and y) if x divides y/x and gg[x]!=n.

Answer is shortest distance to a vertex from 1 in this graph +1.

Use dp_x — amount of numbers to get 1 if you took already some numbers with gcd = x.

To calculate dp_x, we need to check for each divisor d_j of x: is there a number a_i such that gcd(x, a_i) = d_j. To do this, we calculate another DP dq_x, a (a is divisor of x)— amount of a_i in the array such that gcd(x, a_i) = a. Calculation of this dp looks like this (suppose w_x is amount of numbers in a_i which have x as a divisor):

for i in rev(divisors[x]): # divisors[x] are in ascending order
  dq[x, i] = w[i]
  for j in divisors[i]:
    if i != j:
      dq[x, j] -= dq[x, i]

It's easy to see that recalculation of all the dq's take no more than (faster in practice)

Of course, we will keep only one dimension of dp_x, a for current x to fit into memory limit.

And, in the end, we solve the original dp_x in the following way: dp_x = min(dp_y) + 1, where exists a_i such that gcd(x, a_i) = y.

Have a variable cur = array[0]. Loop from 1 to n-1. if(cur == a and array[k] = b and array[k+1] == a), then you should swap at k and set cur to b. If cur == b and array[k] == a and array[k+1] == b, then you should swap at k and set cur to a. If you finish and cur == b, then you should swap at n-1.

You can always rearrange the string to make every 'a' stands before all 'b's.

To do this, we will traverse through the string and find substrings (consisting of consecutive characters) that all characters of it are 'a'. Let's denote the substring S[L, R].

It's easy to say we will reverse prefix L - 1 (if it exists) and prefix R.

Total complexity is O(N) with two-pointers. Naive solution in O(N²) is still acceptable with the given constraints.

With regexes. To substitute all a+ or b+ (but not b+ (longest) at the ending of the string) by '0' * length_of_a_match + '1' — Perl code: 45056981. Or, Algo_Rhythm's variant with regexes: 45058519

I've noticed it just now by reading this comment. I was blown away when I saw so many people solved C so fast. Damn!

I did the same :( Btw, how can it be solved for general strings?

Bruh me too xD

You may compare the difference of x[i] and y[i], say d[i] = y[i] - x[i] for every competitor For two competitors i and j, if d[i] <  = d[j] then i should solve the second one.

Binary search on how many competitors have higher d[] then himself and the answer can be calculated using prefix sum.

Pretest 3 for C can be baaaa.

Split the first permutation into largest substrings which appear in all other m - 1 permutations:

1|2 3|4
2 3|4|1
4|1|2 3
1|2 3|4

If the length of the i'th substring is k[i], then the answer is:

long long ans = 0;
for (int i= 0; i < numberOfSubstrings; i++)
  ans += k[i] * (k[i] + 1) / 2;

Just finished my code 2 minutes after the contest. I used rolling hash and binary search. For each number i from 1 to n,find the longest subset obtainable starting with the value i. Complexity O(NMlogN). CMIIW.

My personal ideas: The numbers from 1 to N can be seen as a directed graph, and I'll count the appearance of the pair (i, j), with i and j are the values of 2 consecutive elements on one permutation.

If any pair appears exactly m times, then there will be an edge starting from u to v.

With this given, it's certain that the graph will be a DAG, and there is no vertex having more than one edges pointing at it.

So we can do a simple DFS from all sources to find the answer. With each source, if the total number of traversable vertices from it is x, add x * (x + 1) / 2 to the answer.

UPD: I didn't take the TL seriously and my solution got TLE. Damn!

Total complexity is O(NM * log(NM) + N).

UPD2: Accepted solution (904ms): 45022094

UPD3: Improved solution (171ms) from suggestion of mouse_wireless — complexity reduced to O(NM): 45031805

Oh well, I guess my solution was kinda different...

Create the array ans[] where ans[x] is the amount of ways which start with number x in all permutations. Also, make the array pos[][] where pos[x][k] is the index where number k appears in permutation x. In particular, for num[m][n] (where num[x][y] is the yth number in permutation x), ans[num[m][n]] = 1. Now for any i with n-1 >= i >= 1 (a for loop where i decreases from n-1 to 1), take next = num[m][i+1]. Then, if for some j (1 <= j < m) num[j][pos[j][num[m][i]]+1] != next, we will have ans[num[m][i]] = 1. Otherwise, ans[num[m][i]] = ans[next]+1. Indeed, we know the value of ans[next], since we loop through i in decreasing order.

Therefore, the answer for the problem is the sum of ans[x] for all x with 1 <= x <= n.

min(x_i + y_j, x_j + y_i) = x_i + y_j iff x_i - y_i ≤ x_j - y_j.

For E, sort by x-y values since if x+b < y+a, then x-y < a-b. Then use prefix sums to calulate the sum.

For D, I used hashing too, hope it doesn't give TLE in systests.

min(x[i] + y[j], x[j] + y[i]) = min(y[j] — x[j], y[i] — x[i]) + x[i] + x[j]

a[i] = y[i] — x[i] a[j] = y[j] — x[j]

min(x[i] + y[j], x[j] + y[i]) = min(a[i], a[j]) + x[i] + x[j]

I'm pretty sure it's just you're not using fast I/O. I TLE'd on 9 too and it passed once I fixed that

min(x[i] + y[j], x[j] + y[i]) = min(y[j] — x[j], y[i] — x[i]) + x[i] + x[j]

I rather used the fact that x_i + y_j < x_j + y_i is equivalent to x_i - y_i < x_j - y_j -- and then you can just use variables z_i = x_i - y_i.

My solution was a brute-force check if constructing a valid x is possible for a given k. Got hacked because I initialised x to -1 each time, but x[i] can take value -1 sometimes...

Yep.

This round was much easier than usual cf rounds, A, B, C, D were pure ad-hocs, and E too was easy. I didn't even read E because it was E :( .

This time I can agree actually

Or maybe just another notorious coincidence?

problem F is from polish contest, author is polish

https://szkopul.edu.pl/problemset/problem/4ftrK3Aqy2bpLk32N7wmjdZR/site/?key=statement

+1

Thumbs up for the problem D.

This is the first time it was interesting for me to read the story in a problem. I have never experienced that feeling while reading problem statement. The only artificial smell is that we're asked to find the number of different ways to eliminate ambiguities. At first I thought that the problem would ask us about deciphering who is trying to fool us (from the neighbours) and trying to lead the investigation astray :)