Meanwhile real ch_egor

ch_egor ping

What is wrong with F? (Except a quite long statement)

Let’s imagine this situation. You gave every segment some number 1..k, such there are no intersecting segments with the same number. In this case you can easy maintain dp.

When we try to add new segment, we take some remaining color to match it to this segment (you have mask of free colors). So we came back to previous situation.

You should split 2n-2 items. Two smallest will be start and finish.

It can be solve by easy dp.

dp[i][j] — number of such coloring, if last j colors are equal.

You should look on case when n = 1. It will help to understand whole problem.

The probability that you will fail on both numbers at the same time is extremely low.

Moreover, 1e9 + 11 isn't prime.

You should use more than 1 prime number to hash the number of ways.

You are absolutely right!)

Thanks, you made my day

Let’s look on some correct splitting. What changes then we cut some line? Some next cuts will split set of rectangles in two parts with empty one. All those cuts should be deleted. After deleting correctness doesn’t change.

You can change set into list or 2 stacks and this solution will work in O(n log n).

Let’s optimize dividing. When we are finding cut, we do it in O(number rectangles in one part). Let’s go in 4 directions in one time and cut min part.

Also, when we found cut, we should erase one part and keep correct orders in 4 directions. We can do it using stack or list.

This solution works in O(n log n). (We gave here TL from the original contest, where you can solve this problem with python.)

(Sorry, more details will be in editorial)

You can hack easy version only if you solved hard.

The same. 100000001 doesn't work

100000001 doesn't work

Let’s look on stack of increasing values of dp. Then we count the new value, we need to get the minimum element on the segment, that element should be in the stack, we can go from top and search for it. But this solution is O(m**2). Let’s notice that we can erase elements if we find reachable element earlier. So we can keep in stack only optimums. That gives us O(m).

3 3
<<<
<<=
<<=

Answer:

Yes
1 2 2 
3 3 2

But it was...

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]

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

I gonna die if i would set more ... С = 0.3

Also this test

3 3
2 1 3

Real answer is "YES", but his answer is "NO".

You should use sqrt-blocks.

Here is sample for 17.

[17] [13 14 15 16] [9 10 11 12] [5 6 7 8] [1 2 3 4]

Let's get all sizes of groups of equal numbers (using unordered_map). All sizes <= 1e5, so we can sort (O(n)). Answer is the cyclic shift (in sorted array of number). For all values of cyclic shifts we can calculate answer using sorted array of sizes.

correct answer is 51

Is it ok, that score for problem is not the sum of max score for every group?

The final score for each subtask will be the maximum score of this subtask across all submissions. The score for each task will be sum of scores for its subtasks. (http://ioi2017.org/contest/rules/)

2,2,2,2

2,2,2,1,1

2,2,1,1,1,1

2,1,1,1,1,1,1

1,1,1,1,1,1,1,1

3 in a row

Russian team:

1. Vladimir Romanov voidmax 1 try left
2. Mikhail Anoprenko manoprenko 0 tries left
3. Ramazan Rakhmatullin never_giveup 0 tries left
4. Egor Lifar kiyotaka 3 tries left

So we can use only ones and twos.

"Then we can replace all maximum numbers with twos and the rest we split into ones and weight will be the same."

So [4, 4, 2, 1] equivalent to [2, 2, 1, 1, 1, 1, 1, 1, 1]

q = fastow(b * fastpow(a, MOD-2) % MOD, k)

Z contains only k elements, so you can calculate in complexity O(k)

a·b = 1

b = a^p - 2

1e9 + 9 is the prime number so you can use Fermat's little theorem.

You can calculate first block in complexity O(K + log(A + B). First calculating , so you can calculate all degrees up to .

Thanks :3

Please, wait for editorial, i'm preparing it now.

nope, a = 1 / (p — b) and k = 2, so (b/a) = -1 and (b/a)**k = 1

1e9+6=(5e8+3)*2 (two prime numbers)

I can generate the test, then k devide (p — 1).

Try a = b or a = p — b

Thanks :3

http://mirror.codeforces.com/blog/entry/58959?#comment-425616

http://mirror.codeforces.com/blog/entry/58959?#comment-425616

With 1e9 + 9 I can generate more “smart” tests.

http://mirror.codeforces.com/blog/entry/58959?mobile=false#comment-425677

1e9+9 is prime number

http://mirror.codeforces.com/blog/entry/58959?#comment-425616

a = p — b

fixed

D WA99 <3

B->AC->AAB->AAAC->C

C->AB->AAC->AAAB->B

when B ~ C

A->BB

B->AB

AAA->''

before B we can make A, add 'kill' AAA, so we can make any number of A

so when we take substring we interested in count of B and count of last A

and then where some easy cases (you can look in my code, after system testing)

Top 5 of russian qualification:

1. Romanov Vladimir voidmax
2. Denis Shpakovskij Denisson
3. Daniil Nikolenko qoo2p5
4. Egor Lifar kiyotaka
5. Alexandra Drozdova demon1999

The Russian team:

• Romanov Vladimir voidmax, 2 attempts left, first time

• Denis Shpakovskij Denisson, 1 attempt left, first time

• Egor Lifar kiyotaka, 4 attempts left, first time

• Alexandra Drozdova demon1999, 0 attempts left, 2016 Silver*

f(n) — complexity of sum dfs with n nodes.

m <= 26, sum(s_i, i <= m) = n — 1, f(n) = max(sum(f(s_i)) + m * min(s_i)) if (m = 1) f(n) = 1

let's prove f(n) = n log2 n

if (max(s_i) <= n / 2):

1. sum(f(s_i) < n ((log2 n) — 1)
2. m * min(s_i) <= n
3. f(n) <= n log2 n

else:

1. if m > 2, when we can found f'(n), that using m <= 2 and f'(n) more than f(n)
2. so we need to prove, that (g(n) = a log a + b log b + min(a, b) * 2) g(n) = n log2 n. I didn't prove last step, but i checked it for n <= 1e5 and it is working

for each level O(len(h)), sum(len(h)) = n

So let's prove asymptotic O(26 * n).

2 vertex have merged, so they won't be merge again. So my solution works 26 * O(count of merges).

NBHEXT stoped working, did anyone else have the same problem?

61 84 129 162 170 190 227 239 247 251 272 292 312 344 352 355 363 365 386 415 420 433 442 443 466

"The seed will be the score of the first place in the tomorrow"

So if there are two people with the same ranks, score will be the same.

mp[x] += i+'0';

i can be big (> 256), so your solution incorrect.

| every hour update the page with this blog...

more: http://mirror.codeforces.com/blog/entry/49611

It will show answers below your comment, changing rating and etc

You can, i'm using it on Mac Os with Jar Launcher.

I use stupid solution (n**2)q and it got accepted.

Yes

My really easy solution:

http://pastebin.com/4v3sZvk7

Also today’s DIV1 E was actually the same like this problem http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=714#1. You just needed to add two more cycles.