I think it is not allowed in order to make the problemset reusable.

Oh, awesome! I knew that such decomposition exists but could not construct one explicitly!

If anybody is interested, such decomposition is called tree-partition, it is connected with the standard treewidth: https://arxiv.org/abs/math/0602507.

Well, I think it is not really well-known in this community so it'd be nice to spread such ideas this way. I would better give the problem without making it implementation disaster.

I've written a short paragraph about it in the end. The key idea is that in this problem you can shuffle the array arbitrary and the expected number of queries inside blocks is very low (I think it is line O(1)). That is the reason .

The problem itself (if you take out the binary circuits) is well-known communication complexity problem (I've hoped that it is only moderately known in the competitive programming community). I wanted to give a problem based on it for a long time and before the championship I thought that I can do it. Unfortunately the way I initially planned failed and there were only two days before the championship so I've decided to do everything in the straightforward way.

I've cursed this idea, the problem and myself many times when I implemented the solution for about 4 hours and then debugged it for another 3 (it is so awfully unpleasant to debug a circuit inside communication protocol).

I've hoped that the participants will come up with something easier to implement than me and that since they code much faster they will make it :) Apparently it was way too tedious.

I am sorry that I've spoiled a nice problem with this gargantuan implementation, but there are a lot nice ideas in communication complexity and probably better ways to wrap it as an ACM problem.

B: Separate the array into blocks of length . Compute the operation on all prefixes and suffixes of the blocks. After that build a new array b of length where .

One can build a data structure with initial operations such that the data structure could compute in 1 operation for any . I denote this number as and respectively .

Assume for now that we have a data structure like this. How to solve the initial problem? In order to find the answer for the query x₁, ..., x_k you can compute .

where is the smallest number such that and r' is the biggest number  ≤ r such that . and a(r', r) are a suffix and a prefix of a block. Therefore, given the described data structure it is easy to solve the problem.

The needed structure can be constructed as follows: divide the array A in two halves and compute the operation on the suffixes of the first half and on the prefixes of the second one. With that we can compute if in one operation. The next step is to recursively construct the structure for the both halves of the array. The depth of recursion is therefore the complexity is .

The only part we did not cover is how to deal with the situation when we need to answer a query and both and r are in the same block. How can we deal with it? We can randomly shuffle the array. After that one can compute the expected number of queries for the same block and convince themselves that it is o(n).

B, very briefly. Let's delete all vertices such that one of the sinks is unreachable from them.

1. Notice that for every vertex x of a correct machine the set of edges on any path from the source to x contains the same set of edges. It follows from the fact that any path from the source to the 1-sink have to contain all the edges (can you see why?).

2. Moreover, for every vertex x of a correct machine and for every pair of paths from the source to x and for every vertex of G the parity of the sum of the values of the edges is the same on both paths. The argument is similar to (1).

3. One can verify (1) and (2) using hashing.

4. if (1) and (2) hold then f(x) = 1 implies .

5. The only possibility for an error is x such that f(x) = 0 but .

6. The case (5) happens if and only if there is a vertex of the machine x labeled with an edge e such that e is not a bridge in the graph G - e'₀ - e'₁ - ... - e'_k where e'₁, ..., e'_k are the edges on a path from the source to x.

7. (6) could be verified using disjoint set union with rollbacks.

Let's consider some pair of vertices (u, v). Optimal path could be written as a sequence of vertices u = a₀, a₁, ..., a_p = v. Obviously the edge a₀ → a₁ belongs to some clique A and edge a₁ → a_p belongs to some clique B. The crucial observation is that if we fix the cliques A and B we are able to find the path between u and v without looking at the individual vertices but only at the cliques. Every edge in the path between u and v belongs to one or several cliques. Let's call a pair of cliques C₁ and C₂ connected if there exists vertex x belongs to both C₁ and C₂. The path between u and v could be decribed as a sequence of cliques A = A₁, A₂, ..., A_p - 1 = B where A_i connected with A_i + 1. It's obvious that with given vertices of the path we can easily find the indices of the cliques. On the other hand given the indices of the cliques we can by definition choose a common vertex for every consecutive pair of cliques and add the starting and the ending vertices.

Let's consider a graph G where each vertex corresponds to a clique and there is a directed edge i → j with the weight a_j (weight of clique number j) if i and j are connected. Then for every pair (u, v) such that (S(k) is the set of vertices of clique k). dist(u, v) ≤ dist_G(i, j) + a_i where dist_G is the distance between the cliques i and j in G. dist_G could be found in O(k³) with Floyd-Warshall algorithm. G itself could be constructed by definition in O(n·k²).

Then all what we have to do is for every pair of cliques (i, j) find the number of vertices such that the optimal path for these pairs corresponds to the path between i and j in G. Let's process pairs of cliques in the increasing order of a_i + dist_G(i, j) and at each step find the number of pairs (u, v) such that ; and (u, v) was not considered at previous steps. Then if this number is denoted a x we should increase the answer by x·(a_i + dist_G(i, j)) because for these pairs there is no better path. Let's enumerate . For every clique i we will maintain set of cliques D(i) such that . Denote cliques where u belongs as i₁, i₂, ..., i_p. Pair (u, v) should be counted at this step iff and . Assuming that for every possible set of cliques {c₁, ..., c_p} we calculated α({c₁, ..., c_p}) the number of vertices w such that the intended number of vertices u could be found as .

So, only thing we should do is to calculate α for each of 2^k sets of cliques. First of all we can find β(I) the number of vertices belongs to cliques from set I and doesn't belong to any other cliques. Then . Even if we calculate alpha in straightforward way enumerating all the subsets of one can proof that we will have time complexity O(3^k) and it was enough to get accepted.

But there is a way to calculate α in O(2^k·k). It's easier to calculate α'(I), the number of vertices . Let's use dynamic programming: dp[mask][j] (where mask is the string of k zeroes and ones) is the number of vertices w such that for i < j and for i ≥ j . dp[mask][k] = β(mask). For j < k dp[mask][j] = dp[mask][j + 1] + x where x = 0 if mask[j] = 0 and x = dp[mask'][j] (where and mask'[j] = 0) otherwise.

For every vertex denote M(v) as a string of zeroes and ones such that . Then first summand in dp corresponds to vertices with M(v)[j] = mask[j] and the second summand corresponds to vertices with M(v)[j] ≠ mask[j] (if mask[j] = 0 we should not calculate it). Finally it's pretty clear that α'(S) = dp[S][k].

This is it, now we have a solution with time complexity O(2^kk2 + n).

Thank you! My solution is literally the same. This problem appeared in my research practice, the system described in the statement is called linear-splitting trees and the whole tree can be used as a proof of unsatisfiability of a boolean formula. This formula (for pigeonhole principle) is a good example of hard formula for many proof systems and it was natural to find upper bounds for depth of a proof for this formula.

And it turned out that optimal approach for the prover here is that natural, I was amased myself when I found the solution. I'm so glad that you and two other teams solved it! I don't think many participants made it through the statement but I don't think it's possible to make it significantly clearer.

What was your approach for G by the way?

The main idea is to generate grey table with white rectangle [i, n] × [1, i]. Given table satisfies this condition for i = 1. Then you can increase i by one in the following way. Using black pair you can generate tables which look like follows

...B
WWW.
WWW.
WWW.

Then using column swapper you can get

.B..
W.WW
W.WW.
W.WW

Add initial rectangle

WWW.
WWW.
WWW.
WWW.

to all these shifts and you got

....
WWWW
WWWW
WWWW

Eventually you will get 1 × (n) white rectangle and applying this approach to it you will obtain grey table.

It's possible to actually solve the problem in O(ans·n³). Instead of looking for increasing chain for each choice of the next edge in the matching one should run one dfs and find all increasing chains at once.

Yeah, sounds good for me. That's a very nice solution!

I don't think that is correct because you are calculating the function after you've fixed everything, but your memoisation doesn't corresponds to the actual information you need to calculate the function (which is actually the whole arrangement), that's why you may choose wrong arrangement with the same characteristics (n and k) because you are picking up some arrangement, calculate the function for it and then you don't calculate anything for different arrangements with the same characteristics. What you should do is to calculate the function step by step (with gap contributions I described) when you are deciding to pick or not to pick the element. That is very important because you will be able to know which state is better.

Wow, I haven't thought about such greedy. I've tried to find counterexample for this but haven't succeed. The main assumption you make is that except one or two integers in the center we should arrange integers symmetrically. If that's true, everything is correct. But I don't know how to prove it either. Could anybody prove of disprove this?

To be honest, that solution is a bit overkill for the problem and I thought that the problem will be harder.

I'd like to explain another way to come up with practically the same dp. Let's sort the numbers and look at each gap between consecutive numbers. The length of the gap a_i + 1 - a_i will be caclulated in the final answer with coefficient A·B + C·D where A is the number of Li's integers among {1, ..., i}, B is the number of Lu's integers among {i + 1, ..., n}; C is the number of Lu's integers among {1, ..., i} and D is the number of Li's integers among {i + 1, ..., n}. It's clear that C = i - A, D = (n - i) - B.

Then if we have dp state (i, j): we have arranged the first i integers and j of them we have given to Li. Then it's easy to find A, B, C and D for the gap between i and i + 1. Then the function we calc with our dp is contribution of gaps before element i to the final answer.

I think it could be more interesting if rounds had two hard problems instead of one. There will be more freedom to vary strategy and choice of problems to solve.

Also the scoreboard on hackerrank is a bit boring, I'd like to see scores for all problems not only sum.

First of all if X = 0 we should sort projects by a[i] / b[i] and in each half that order is the best possible.

Let's fix B sum of b[i] in the second half. Then dp[i][j][k] — the best possible amount of money with j projects in the second half, b[s₁] + b[s₂] + ... + b[s_t] = k where s₁, s₂, ...s_k is the set of projects in the second half. Then if we put i-th project to the first half we should increase answer by a[i]·(B + b[0] + ... + b[i]) and something similar if we put i-th project to the second half. Then the answer with fixed value of B is dp[n][n / 2][B].

500 div1: https://www.e-olymp.com/ru/problems/5468

D is also could be solved with divide-and-conquer. The first step is to reduce problem to 0-1 bfs (we can always decrease our skills for free and can cast one spell to change the skills from (a,b) to (c,d)). If we add all edges there will be O(n²) 0-edges, but it's possible to add additional vertices in such way that we will only need 0-edges and path in our new graph will correspond to path in old graph with same length.

So, how to add new vertices in that way? Let's separate all initial vertices into two halves such that all vertices in the first half is on the left from vertices in the second path. There will be vertical line divides all vertices in that way. Denote it's x-coordinate as x₀. We have to add vertices with coordinates (x₀, y₀), (x₀, y₁), ..., (x₀, y_k) where y₀, ..., y_k are all y-coordinates of the whole set of vertices. (y₀ < y₁ < ... < y_k). For the vertex (x, y) such that x ≤ x₀ we should add edge from (x₀, y) and if x ≥ x₀ it would be edge from (x, y) to (x₀, y). Also we should add edges from (x₀, y_i) to (x₀, y_i - 1) for every possible i.

That's it, then we should find shortest path in that 0-1 graph.

Guys, four standard problems and strange challenge with optimising <1% of score. That's not how I like to spend my Saturday evening. I think there was lack of hard algorithmic problem with interesting subtasks. Also I think it's a good idea to write about subtasks scores in statements.

What what intended solution for the challenge problem?

I had exactly that greedy approach. I've tried to improve it with something like annealing but it didn't give me any points on official testcases. Also I've tried some of modifications you described but my first attempt was the best one. I'm wondering what is authors solution.

I have result "attempted" and all testcases are accepted. What does that mean?

My English is one big shame, yep. In that sentence I meant that if (a, b) is maximal lit interval and spotlights i, j lies in (a, b) and i ≤ k ≤ j, then interval lit by k is subset of (a, b). I missed the word "maximal". Is it obvious now?

So, if you want to block (2, 2) and (3, 3), you have to block (2, 3) and (3, 2).

You have classical formula . So, all you have to know is factorials of integers from 1 to 2·10⁵. Then modulo mod (if mod is prime), so C_n^k = n!·(k!(n - k)!)^mod - 2 modulo mod. So, you should calculate a! and (a!)^mod - 2 for a from 1 to 2·10⁵ and then find binomial coefficients in O(1).

I think it's not, but I don't understand what arrays row and col means.

Why did you used H₂? H₂ itself fails test

abab
cdcd

But I can't see how to make H₁ fail. It didn't work without H₂?

UPD: I like your approach :)

That is nice! It's even easier to implement than our approach.

Because 10^10 operation is a little more than codeforces invokers can perform in 2s.

Let answer is 2^a₂·3^a₃·... (Notice that we should consider only primes  ≤ 10⁴) So we have to find a_p for each p. Let α is maximal number such that p^α ≤ n (linear multipliers will never be divided by bigger powers of p). Let's fix x modulo p^α. Now for every multiplier (x - a) we can calc maximal r such that p^r divides (x - a) for current x. Then we should find minimal sum of r-s among all possible values of x modulo p^α. That approach is O(n³).

But it is easy to see that p^r divides (x - a) only if x = a modulo p^r. So, we can enumerate r and find d[r][i] — sum of powers (from the problem) of multipliers divisible by p^r with x = i. And finaly for every f(k) = d[0][k / p^α - 1] + ... + d[α - 1][k]}. Min of f(k) is a_p.

It's easy to register second account.

I think, that's correct solution. Why it's wrong?

There is accepted solution with time. 5429539

Oh, yes, I got it. I've fixed explanations.

Do you have any arguments? Is my calculation of probabillity wrong?

On your test my solution works with probabillity 1.

It's

Upd. Oh, yep, it's a crap.

Upd2. Oh, no, it's really . Show why it's wrong, if it is.

I think you should look at example (divisors of 216)

1   - 216
2   - 108
3   - 72
4   - 54
6   - 36
8   - 27
9   - 24
12  - 18

You can see, that considered set is in the first column. 3, 6, 9, 12 are divisible by 3 and 2, 4, 6, 8, 12 is divisible by 2. So, it's beautiful set. Has it become more clear?

Yes, you are right, I will write this item carefully.

You approach for problem b div1 is similar to mine. It's not complicated, what are you talking about? What about div2 b, you are right I will add that to post.

Oh, you are right, I'd been thought that it is n^2*k till sunday.

Mmm. My solution constructs correct set with k' ≥ k elements. It's possible to prove, that we can obtain correct set for any k. But then I use statistic to prove, that I can obtain correct set with exactly k elements. I will write about it in editorial.

Thank you =)

Standard. Score distribution is not defined at the moment

How to solve 950? All people who submitted it have bugs?

dp[i] — number of bad pairs in set with (2^i) numbers

dp[i] = (s[i] = 1)·(2²ⁱ) + 2·dp[i - 1]

It's O(ans), isn't it?

I'm sorry, that was not in English. And now my English is not good.

d1. dp[mask] — — maximal answer for permutation of letters in mask answer is final position of pointer in greedy algorithm of collecting letters from string. if dp[mask] <= n, all is OK.

d2 is interesting for me too.

That's problem 'cover graph with minimal number of paths', doesn't it?

UPD: acyclic graph

Independent set is not NP problem for biparite graph. You can prove that answer always is V — |maximal matching|. I'm not ready to prove this fact now.

I think, it will appear tomorrow. We have editoral in russian, but we haven't translated it yet.

I'm sorry, I didn't noticed that. My fail.

I'm lucky today. I think it's impossible to catch all bugs using 8 tests.

Yes, and in my test I have overflow too.

Weak tests in problem AERODROM My solution fails test:

30 1000
1 1 1 1 ... 1 1 1

but passes systests. Have anybody the same bug?

Thank you, I see.

Where?

Look, we have some full graph. We add one vertex with q edges starting form it. Is it clear, that we added C_q² triangles to our graph? It it's not, you may check it with pen and paper. Number of vertexes in full part of our graph is p and C_p³ ≤ k. p is maximal possible value such that C_p³ ≤ k. Therefore k ≤ C_p + 1³ and k - C_p³ ≤ (C_p + 1³ - C_p³. k - C_p³ ≤ C_p². Ok? We add new vertex with q edges. We will add C_q² triangles to our graph and q is maximal. Therefore k - C_p³ - C_q² ≤ C_q¹ = q. We have x = C_p³ + C_q² triangles in out graph and difference with k is no more than q ≤ p ≤ 85. If we will repeat adding vertex five or six time difference between k and number of triangles will become zero.

I thought that problems is not so hard. About ten people solved C, but there were many pitfalls in it. One guy solved E, but he had some bugs too.

it's published

|D(0)| = 1, |D(1)| = 2, |D(2)| = 3, |D(3)| = 5, |D(4)| = 8, |D(5)| = 13, |D(6)| = 21

1 -> 14 -> 13

Yes, you are right. Thank you.

Vertex |D(n-1)| + 1 is cutpoint. Because of this, if min(a,b) <= |D(n-1)| + 1 and max(a,b) >= |D(n-1)| + 1, path will contain |D(n-1)| + 1. We should solve same problem for pair (a, |D(n-1)|) (a, 1) (b, |D(n-1)|+1) and graphs with orders k-1, k-1 and k-2 respectively.

5 1000
1 10000000000000000
1 9999999999999999
2 9999999999999999
3 9999999999999999
4 9999999999999999

ответ:

20
20 
21
21
21

Will be announsed in a few minutes before the start of the contest.

все довольно просто же. сначала прибавим к ответу все треугольники. потом, для каждого ребра Элис вычтем из ответа n-2. Потом для каждой вершины прибавим к ответу C(cnt, 2). Можно убедиться, что его мы не посчитали ни одного разноцветного цикла, а все одноцветные посчитали ровно 1 раз.

i have a dream

Look, every column except <> and <> (we don't use it) add 1 to some h(s_i, s_j) because there are two different letters in every such column. For example, if we add column <> to the answer h(s₀, s₃) will increase by one (h(s₁, s₃) and h(s₂, s₃) will increase too). Therefore number of every type of columns doesn't exceed h(s_i, s_j) if letter i differs with letter j in this column. We obtain that number of every type of columns doesn't exceed some h(s_i, s_j). Then number of every column doesn't exceed maximum of h(s_i, s_j).

We have six linear equations with seven variables. Number of variables greater than number of equations. Because of this we have one free variable. In other words we can represent every variable except for free as f(x) where x is free variable.

For example there are one free variable in this system of linear equations:

• x + y = 5
• x + z = 6

x, y and z can be free because we can represent any two variables as f(a) where a is free variable. Is it clear?

There are two cells (x₁, y₁) and (x₂, y₂) satisfying these conditions:

• (x₁ ≠ x₂ or y₁ ≠ y₂)
• 
• .

Your solution have right complexity, yes. But it's so slow because of using vector as parameter in recoursive function. Test 3 is not maximal test. Optimise your solution, remove vectors, long longs etc. And it will pass the tests.

It's solvable, yes. We have system of linear equations and limitations (all values must be non-negative). In that case you can use simplex-mathod and Homori method. I can't tell you more because i'm not sure how it works. But it's so hard for me, and it's not beautiful in my opinion.

Two cheaters were deleted from the standings. And places wasn't updated. I'm not sure, but it looks like truth.

It's hard for me to write it, but you can see editoral for the first 3 div2 problems. Today I hope, you will see editoral of all div2 problems.

Thank you =)

Now you can only register as real contesant. There is no way to register out of competition.

How to solve problem C?