GP of Dolgoprudny - Codeforces

6 years ago, # |

How to solve C.Array and D.Modular Knapsack?

→ Reply

6 years ago, # ^ |

+18

C: Let M = min(A). If M occurs in A once, then the answer is M. Otherwise, consider the first occurence of M.

Note that, any a_j such that a_j > a_i, j > i are useless. Thus, we can conclude that the "modulo chain" before the first occurence are strictly decreasing. Also, After passing the first occurence, the value X_i will never decrease unless it is M. We will find a set of numbers that can be the result of x_i after passing the first occurence.

Then, we should find all number N such that N can be represented as $\text{[math]}$ ... when a_i > a_j > a_k. This can be done with DP. Sort A and remove duplicates. Let DP[i][j] = (true iff j is possible outcome after passing some subset of modulo chain for length-i prefix). This can be calculated easily in O(n²), and with some bitset labor you can reduce it to O(n² / 64).

D: Let's solve minimization problem instead. It seems that the one with large weights are mostly useless, as it seems they can be replaced with smaller ones. The tests are intentionally broken, so this is enough. Add the item in the order of weights, run the program for 1.45 second and quit. You can easily transform the min. problem solution into max. problem.

→ Reply

dragoon

6 years ago, # ^ |

In C, is it like: say upto i, the bitset is B, then at i+1, you will divide the bits in a[i+1] lengths, and OR them with B to get newB? That yields, n^2log(n)/64, right? Any better way?

→ Reply

6 years ago, # ^ |

Exactly that. And it is N^2/64 + NlogN.

→ Reply

dragoon

6 years ago, # ^ |

How do you get [bit_i, bit_j] quickly?

→ Reply

6 years ago, # ^ |

I implemented my own bitset.

→ Reply

6 years ago, # ^ |

Finally I solved this problem and it was really difficult for me to implement operation get_segment in bitset and what I done is something like sqrt decomposition: shift left pointer until it is on a start of some bucket (in our case bucket is an int and it's size is 32), then shift right pointer until it is on the end of some bucket and then process all buckets between left and right pointers. Processing is just splitting current bucket into two parts — one with size (32 — how_much_we_shifted_left_pointer) (head) and the other one is what is left (tail), and then save these parts in a new bitset in bucket i and i+1 respectively — head part goes to i and tail part goes to i+1 bucket.

My implementation is here. It uses long insted of int, but it doesn't matter.

It may seem overcomplicated, but this is the only proper method I can imagine. Could you share your bitset implementation or/and tell something how it works?

→ Reply

https://ideone.com/XGSZaC

6 years ago, # ^ |

+10

→ Reply

6 years ago, # ^ |

+15

It's so beautiful! Thank you!

→ Reply

zeliboba

6 years ago, # ^ |

Also there is deterministic solution for D with idea of convex hull and stack.

→ Reply

6 years ago, # ^ |

+10

Oh, your reply reminded me a very similar problem. Unfortunately (or fortunately) I didn't remembered this in contest :p

→ Reply

qwerty787788

6 years ago, # |

+45

How to solve B?

→ Reply

Um_nik

6 years ago, # ^ |

+39

+1
How many people who wrote AC solution for B are interested in how to solve it?

→ Reply

rng_58

6 years ago, # ^ |

+20

Let me try. (I'm not very confident, I don't understand suffix automatons very well.)

Let's call a string of length n "row string" if it appears at least once as a row of the secret board. We want to determine all row strings. Then it's easy to recover the entire board in O(n²) more steps.

Suppose that we currently know that s₁, ..., s_k are row strings for sure. We want to find another row string, or conclude that there are no more row strings.

Let's construct a suffix automaton for the string s₁ + 'x' + s₂ + 'x' + ... + s_k. For each state in this automaton, let t be the shortest string that reaches this state. Let's query "t + 'a'" in case the automaton doesn't accept it; if the secret board contains it, we can get a new row string by extending it. Do the same for t + 'b'. If we can't find new row strings this way, we've found everything.

Since we can construct the automaton incrementally, the total number of new states we get is O(n²), and the number of queries is O(n²).

→ Reply

zemen

6 years ago, # ^ |

+10

The solution is to find all different rows of the table one by one and then in n² queries restore it.

If you have found k rows, you need to find any string that is not a substring of any of these k rows. Then it can be expanded to the whole row in at most 2n queries.

Consider a trie of all substrings of already found rows. You can try to go by non-existent transitions of the trie and ask if there is such a string in the whole table, do this in the order of length increase. However, in its simplest form, it will work in cubic number of queries. Here comes the trick to make it 2n² overall — if you already know that some substring of the string you are about to ask doesn't exist, skip this query.

If you consider the trie as a suffix automaton of k strings, you can prove this upper bound. There will be at most 2n² states in the automaton and among all transitions by the same character from each vertex you will ask only about the shortest string, skipping the others.

→ Reply

rsFalse

6 years ago, # |

When the upsolving of this and past div.2 contests will be available?

→ Reply

greencis

6 years ago, # |

How to solve the "hellish" problem G? Is there an article on arXiv or somewhere else about this problem?

→ Reply

zemen

6 years ago, # ^ |

+36

I have some kind of "editorial" for G.

Recall the algorithm for building automaton. Let's calculate expected number of cloned states then add n + 1. Consider adding last character of string s. Let t be the longest suffix which occurs more than once and let a be the character preceding t. Then vertex cloning had happened iff there is character b ≠ a such that it preceds each occurence of t except for the last one.

For string s denote sequence |s|, |π(s)|, |π(π(s))|, ... 0 as chain(s) (here π(t) is longest suffix shorter than t equals to prefix of t). Let's calculate all possible triples (chain(t), chain(at), chain(bt)), where a and b are different characters. Also for each triple we need to know the number of triples of strings (t, at, bt) which corresponds to this triple. Knowing only (chain(t), chain(at), chain(bt)), it's possible to calculate number of strings s such that vertex cloning happened.

→ Reply

aid

6 years ago, # ^ |

← Rev. 2 →

+10

You don't need triples. You need to calculate for each t number of strings that contain it and subtract those in which all occurences of t are preceded by the same character a. Only pairs (chain(t), chain(at)) are needed for that.

→ Reply

6 years ago, # |

+25

Is it really possible to solve problem J in 19 minutes or is that AC in 19 mins some kind of a hoax xd?

→ Reply

rng_58

6 years ago, # ^ |

+13

It took me 30 minutes to solve it, 19 mins doesn't sound crazy.

→ Reply

6 years ago, # ^ |

Btw how to solve it?

→ Reply

rng_58

6 years ago, # ^ |

+51

Suppose that all coefficients of polynomials are in F₂. The key observation: P(x)² = P(x²).

For an integer n and a polynomial Q, let f(n, Q) be the number of nonzero terms in Pⁿ * Q.

In case n is odd, use f(n, Q) = f(n - 1, PQ).
In case n is even, first decompose Q into "even part" and "odd part": Q(x) = R(x²) + xS(x²). Then f(n, Q) = f(n / 2, R) + f(n / 2, S).

This way we reach only O(2^dlogn) states.

→ Reply

olekluka

6 years ago, # ^ |

Did you actually implement this as recursion with memoization? Because it looks like it's rather hard to fit into the memory.

→ Reply

Um_nik

6 years ago, # ^ |

+10

rng_58's solution is cool and I think that I do mostly the same thing, but I came up with that in a very different way.

I will also use that P(x)² = P(x²), so P(x)ⁿ = P(x^{2^a₀})P(x^{2^a₁})... P(x^{2^a_m - 1}). Now let's calculate (imaginary) DP[i][j]: we multiplied first i polynomials and interested in coefficient for x_j (basically DP[i] is a product of i first polynomials). We can see that if j₁ and j₂ have different remainders modulo 2^a_i then they are independent, so our DP is a set of 2^a_i independent DPs, corresponding to different remainders modulo 2^a_i. Each of these DPs have only d interesting states, all other values are zeroes. So we can count the number of DPs with given mask of values in another dp, now real (in the code). We have to make transitions for imaginary DP, they will correspond to transitions in our real DP.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+10

You're crazy, it took me rather something like 2-3 hours xd. But it seems my solution looks significantly more complicated. I didn't even use explicitly the fact that P(x)² = P(x²), I base my solution on fact that $\text{[math]}$ is odd iff i₁, i₂, ..., i_k are submasks of n in binary system.

→ Reply

Claris

6 years ago, # ^ |

+10

J is a well-known problem in China:

Version 1

Version 2

→ Reply

zeliboba

6 years ago, # ^ |

We were afraid that it could be well-known(

→ Reply

6 years ago, # ^ |

OK, "HDU-coach" team name and this question being asked on HDU online judge explains a lot, I suspected that's likely reasonable explanation.

→ Reply

dragoon

6 years ago, # |

+10

How to solve A, E, H?

→ Reply

6 years ago, # ^ |

← Rev. 3 →

H: Note that if k is the largest value of a n-beautiful multiset A, then the elements of A that are smaller than k have to form a k - 1-beautiful multiset. If there are x copies in k, then we get x·k + (k - 1) = n, so k is a proper divisor of n + 1. Conversely, taking such a k and adding x copies of k to a k - 1-beautiful multiset, we always get a n-beautiful multiset. We can hence use dp to compute the number and total size of n-beautiful mutisets as follows

$\text{[math]}$

The number of states used in computing DP[n] is equal to the number of divisors of n + 1.

Edit: Does someone have a good bound on the number of divisors summed over divisors of n to bound the total runtime? (Something better than this comment.)

→ Reply

zemen

6 years ago, # ^ |

+20

Actually, intended solution for H was $\text{[math]}$ with convolution repeated $\text{[math]}$ times, but we failed to set time limit properly.

→ Reply

6 years ago, # ^ |

+10

If number of good pairs of good divisors for maxtests is something like d(n)² / 60 (with d(n) ≈ 60000 then good luck with distinguishing it from $\text{[math]}$ :P

→ Reply

Kostroma

6 years ago, # ^ |

+10

Yes, the number of good pairs is around 10⁷, but I also had to index all the states properly. I wrote solutions with a binary search and a trie to do indexing on dp states, and they both worked very slow comparing to the main solution. My bad I didn't force somebody not so retarded in writing fast solutions to try to fit this into TL.

But anyway, the possible solution would only be to increase constraints to 10¹⁸ (and make bigger TL also). I'd say it's controversial whether it'd really improve the problem.

→ Reply

6 years ago, # ^ |

I agree that indexing is some kind of an issue we should deal with (and I used unordered_map for this on beginning), but it can be easily solved by computing corresponding indices recursively along with other info we compute (I was not sure whether by last sentence in first paragraph you meant that you're retarded cause you didn't notice it or whether because you didn't try hard enough to do some other optimizations)

→ Reply

6 years ago, # ^ |

+13

A: Let's say that a_i dominates a_j if i, j are incompatible and a_i > a_j. For every k, we can color it with the length of the longest dominating chain ending with a_k (so a_k the the largest element in the chain). Note that is is optimal, as every chain forms a clique.

To compute the coloring quickly, we compute for every bitmask m two numbers: The largest color C of a value a_i contained in the mask and the maximum number D of bits in which some such a_i differs from m. If m occurs in a and D ≥ k, then we increment C and set D to 0. From every mask, we can transition to other masks by setting another bit. The total runtime is O(22·2²² + n).

I also had a funny issue where declaring array<pair<int8_t, uint8_t>, 1<<22> exceeded the compiler memory limit for some reason.

→ Reply

6 years ago, # ^ |

E: For every node we'll compute the total cost if the capital was placed there. This can be done efficiently with centroid decomposition.

For a fixed centroid C, we root at C and compute for every vertex v the contribution of towers t not located in the subtree of C containing v. For a fixed tower t, its contribution on a vertex v in a different subtree only depends on the depth (=distance from v to C). Moreover, as a function of this depth, the contribution is piece-wise constant with pieces of length k (and an infinitely long piece for 0), so we can efficiently get the total contribution for every depth by prefix-summing over each residue class mod k separately, then prefix summing over the whole array.

To deal with the whole not-in-its-subtree, we compute the contribution of every subtree (only for depth up to the height of the subtree) and the total contribution for every depth. The total runtime is $\text{[math]}$ , even for k up to n.

→ Reply

solaimanope

6 years ago, # |

Can I be solved in O(nlogn)?

→ Reply

6 years ago, # ^ |

Can you tell the easier (slower?) approach, please? :D

After the contest BledDest told me the $\text{[math]}$ solution and also mentioned that it's about the same as in 911G - Запросы на массовое обновление. I can't believe that's what everybody submitted, looks really advanced to me tbh. :D

Let's maintain the segment tree over the queries (segments). At the beginning every node is the identity 2x2 matrix. The merge is matrix multiplication. Then you process all 2n ends of segments in the ascending order. When reaching the beginning of some segment, update the corresponding node in the segment tree with matrix ((100 — p, p), (p, 100 — p)), the end is back to identity matrix. The answer for the end is the root of the tree.

→ Reply

6 years ago, # ^ |

You can just build a lazy segtree (where you only do updates, no queries) over the positions, where the lazy stores the probability of being repainted. The lazy-merge function is similar to what you get with your matrix multiplication: merge(p₁, p₂) = (1 - p₁)p₂ + p₁(1 - p₂). First compress the l_i and r_i to 0, ..., 2n - 1. For every request, you update [l_i, r_i - 1] with p. Then you push all updates down to the leaves of the segment tree. For every leaf, you add it's value times the length of the corresponding uncompressed segment to the answer. Total runtime is $\text{[math]}$ .

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Ye, it's not the application of ST that seems advanced to me but that presence of ST by itself. Like that path I took was about "do the basic events sort thingy; however, we want to delete elements, that would require matrix division". Then I coded some $\text{[math]}$ (so it would not require division, like recalcing the whole dp with matrix exponentiation on each step) that somehow turned not precise enough, I believe (or that WA was purely of my bad implementation). I can't understand what should have pushed me to think about ST.

→ Reply

solaimanope

6 years ago, # ^ |

My solution is in $\text{[math]}$ . It's unnecessarily complicated. Basically, I have decomposed the segments into $\text{[math]}$ chunks. Then proceeding the events from left to right, when an enter/exit event occurs we have to update it's corresponding chunk in time order of chunk size. By updating, for each chunk we will keep the probability of taking odd segments from this chunk. Each query can be answered in $\text{[math]}$ by going over the values calculated for each chunk.

It was not the intended solution. I had to optimize a lot to ACe it. However, what I was doing in my solution can be done with a segment tree too. But I didn't notice during contest time.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

My solution is the same and the only thing I had to optimize is to replace List<Integer> to int[]. I thought it would be absolutely useless, but it worked =)

This solution doesn't seem complicated as for me. And yes, after the contest I realized that it worked for 0.983s.

→ Reply

6 years ago, # ^ |

+10

I had some wrong ideas at the beginning and wrote more complicated O(pn) solution (p = 101). I basically maintain the count for each p_i, and compute the matrix multiple in O(p) time with appropriate precomputation.

→ Reply

6 years ago, # ^ |

What are those precomputations? It seems, I can't squeeze my $\text{[math]}$ by any means)

→ Reply

6 years ago, # ^ |

WLOG assume 0 ≤ L_i < R_i ≤ 2N. For each interval [i, i + 1] we can have the histogram of each p_i occurence with difference arrays. Let q_{p_i} be such occurence. Then we want to calculate M₀^q₀ × M₁^q₁ × ... when M_i is the state transition matrix for probability i. We can simply precompute those powers in O(pn) time, Now we can calculate the answer in O(p) time.

→ Reply