z-function works here

No, I don't. During the contest it just seemed to be the right solution, because I didn't notice the constraints on length of the string (I was solving for 10⁵)

50009667

O(n) solution for div1B without string algorithms. (Ignore everything before function go(l, r))

Nevermind, didn't notice author's solution for bonus problem.

Successfully changed today, this handle was registered in 09.2014. Last year I tried to change, but failed.

47417705 Overkill:

Segment tree with cnt[type][left_mask][right_mask], mask stands for losing and winning move.

Yes, misunderstood the meaning of edge.

You can compute maximal independent set instead which is complement of minimal vertex cover.

Yes

Mine Div1D solution too. Thought 300ms to TL was very tight, but it fails on the test, which is pretest too. I hope for the rejudge :(

Now after some time it passes with 400ms away from TL ... :( 42529738

Same solution, got 100 points 30 second before contest ended.

Squeezed into TL changing cin to scanf, and sort to stablesort...

for second solution:

abcbaac

answer is 2

dp_mask — number of ways to place digits of n (mask < 2^len(n))

39325991

added part with small max(la, lb)

Actually your solution works at least O(n² * m²), because you iterate 2 times over all pairs of intersections. And moreover, it will fail on test 1 1 1 1

Чтобы сдать пришлось использовать 2 оптимизации, вектора присутствуют:

1) генерация делителей из простых

2) 2⁷ вместо 2⁷ * 7

code

vovuh in F we can use another dp with O(a) memory and O(a²) time:

in case we have umbrella in i-th position: dp[i] = min i <= j (dp[j] + (j - i) * w[i])
if we don't: dp[i] = min(dp[i + 1], dp[i])

and when doing convex hull trick on this dp, we can see that slopes are decreasing, so we don't need additional structures to maintain convex hull. so this can be solved in O(a * log(a)) time

link: 38904415

KAN Weird things happening 38741009

d[i][j] = shortest length of string, such that it contains first i symbols of first string as subsequence, and first j symbols of the second string as a subsequence.

dp[i][j] = number of ways to build string with length d[i][j], such that it contains first i symbols of first string as subsequence, and first j symbols of the second string as a subsequence.

transitions:

s[i+1] == t[j+1] => d[i+1][j+1] = min(d[i+1][j+1], d[i][j] + 1)

otherwise

d[i+1][j] = min(d[i+1][j], d[i][j] + 1) and d[i][j+1] = min(d[i][j+1], d[i][j] + 1);

if transition in d is optimal (that means d[i+1][j] = d[i][j] + 1 and others), add ways to dp (dp[i+1][j] += dp[i][j] and others)

What is the 4th test in E?

not necessary to merge smaller to bigger, because every end of the string occurs in that string only, so total complexity O(sum of words sizes)

Build graph with vertexes(index, changed = 0/1), and edges (k_min, k_max), find path of length n.

E appeared with the same approach in International Zhautykov Olympiad 2017

bit 1 -> 4 -> 0(modulo k)

bit 2 -> 6 -> 2(modulo k)

num = 4, divide it by (6%4) -> answer is 2

n % k < k, it represents number of occurences of required number

For each bit store the value modulo k. Get the number, divide it by (n%k).

1kbyjorwqjk

answer can't be greater than |s| + 1

It is not correct answer, it is your output.

we managed to find this solution. for and prime p, try to put 1, and calculate balance on the prefix, if absolute value of balance is more then 20, change value of the last prime, and recalculate balance.

I'm not sure about this soultion.

Let's count all subsequences — 2^n. Now let count all subsequences with their and greater than 0. For all masks save count of numbers, that the mask is their submask. So using inclusion-exclusion principle we can calculate the answer.

UPD: OK

Misunderstood the problem >_<

map <string, vector >

what is D 7th test?

1700 * sqrt(n) maximum distance between 2 primes if they are both not greater than 10^9 is 1700

Here link, where problem was discussed. (Div1 B, almost the same problem, but edge weights could be 1,2,3,...,L)

http://codeforces.com/blog/entry/20559

for each edge calculate how many times we pass from this edge. if edge goes from u to v, it will be cnt[v] * (m — cnt[v]) where m — count of residents. cnt[v] — count of residents in subtree

Hint: 2 ^ i > (2 ^ 0 + 2 ^ 1 + ... + 2 ^ (i — 1))

How to solve C day1 ?

i can. press +

first, calculate LCS, all states by d[n][m]

build dynamic on this states :

dp[i][j] :

1. s[i] == t[j] -> dp[i + 1][j + 1] += dp[i][j]

else

1. d[i][j + 1] + 1 == d[i + 1][j + 1] -> dp[i + 1][j + 1] += dp[i][j + 1]

2. d[i + 1][j] + 1 == d[i + 1][j + 1] -> dp[i + 1][j + 1] += dp[i][j + 1]

that means, if we came from 2 states we need to add both

i used in C another strategy:

i didn't calculate initial stack. let's go from end of the array. for b[i] find previous b[j] == b[i](j = 1...i — 1), that means that after j-th move b[j] on top. than add to ans weights of different elements from j + 1 to i — 1. if there are no j, just add to ans weights of differenet elements from 1 to i — 1

2 1 3 -> 2 3 1 (swap(2nd, 3rd)) -> 1 3 2 (swap(1st, 3rd)) -> 1 2 3 (swap(2nd, 3rd))

if cnt[1] == cnt[2] cout << 0; <- i wrote it in the beginning

ok kill me pls :(

lcm(i, j) = i * j, when gcd(i, j) = 1.

so problem is -> how many pairs (i, j) such that gcd(i, j) = 1.

we can calculate it in min(n, m) with mebius function.

answer[i] = m[i] * f[i], where m[i] — value of mebius function(i), f[i] = function returning answer for i. in this problem it's (M / i) * (N / i)

i got it on contest , but i missed when cout no

for (int it = 0; it < 100; it++)

there are no endless loop, cause only of 100 iterations.