Hmm.. Am I the only one not appearing in the scoreboard?!?

# | User | Rating |
---|---|---|

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | wxhtxdy | 3329 |

4 | V--o_o--V | 3309 |

5 | Petr | 3297 |

6 | mnbvmar | 3255 |

7 | LHiC | 3250 |

8 | TLE | 3186 |

9 | Vn_nV | 3182 |

10 | dotorya | 3165 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 195 |

2 | Errichto | 181 |

3 | neal | 159 |

4 | Ashishgup | 157 |

4 | PikMike | 157 |

6 | Petr | 156 |

7 | majk | 154 |

8 | rng_58 | 153 |

8 | Um_nik | 153 |

10 | Vovuh | 152 |

Hmm.. Am I the only one not appearing in the scoreboard?!?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2019 20:09:27 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Same here... Are only people that participated at the MIPT camp shown on the scoreboard?

We see a bug in Yandex.Contest standings generator that won't allow us to properly generate standing for contests with large number of registeder users (aounr 6000 for opencup rounds because of sector system). We're investigating the issue, will do our best to fix it by the next opencup round. I am very sorry for the trouble.

This bug is at least several months old =)

not exactly, contest log generation for previous opencup round took around 5 minutes and allowed teams to appear on official opencup standings (though it is definitely far from good)

The important thing on B:

You SHOULD NOT output the answer like

! 2 2

11

00

The "correct" answer is:

!

11

00

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

C: Let

M=min(A). IfMoccurs inAonce, then the answer isM. Otherwise, consider the first occurence ofM.Note that, any

a_{j}such thata_{j}>a_{i},j>iare useless. Thus, we can conclude that the "modulo chain" before the first occurence are strictly decreasing. Also, After passing the first occurence, the valueX_{i}will never decrease unless it isM. We will find a set of numbers that can be the result ofx_{i}after passing the first occurence.Then, we should find all number

Nsuch thatNcan be represented as ... whena_{i}>a_{j}>a_{k}. This can be done with DP. SortAand remove duplicates. LetDP[i][j] = (true iffjis possible outcome after passing some subset of modulo chain for length-iprefix). This can be calculated easily inO(n^{2}), and with some bitset labor you can reduce it toO(n^{2}/ 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.

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?

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

How do you get [bit_i, bit_j] quickly?

I implemented my own bitset.

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?

https://ideone.com/XGSZaC

It's so beautiful! Thank you!

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

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

How to solve B?

+1

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

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 inO(n^{2}) more steps.Suppose that we currently know that

s_{1}, ...,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_{1}+ 'x' +s_{2}+ 'x' + ... +s_{k}. For each state in this automaton, lettbe 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^{2}), and the number of queries isO(n^{2}).The solution is to find all different rows of the table one by one and then in

n^{2}queries restore it.If you have found

krows, you need to find any string that is not a substring of any of thesekrows. Then it can be expanded to the whole row in at most 2nqueries.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 2

n^{2}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

kstrings, you can prove this upper bound. There will be at most 2n^{2}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.When the upsolving of this and past div.2 contests will be available?

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

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 strings. Lettbe the longest suffix which occurs more than once and letabe the character precedingt. Then vertex cloning had happened iff there is characterb≠asuch that it preceds each occurence oftexcept for the last one.For string

sdenote sequence |s|, |π(s)|, |π(π(s))|, ... 0 aschain(s) (here π(t) is longest suffix shorter thantequals to prefix oft). Let's calculate all possible triples (chain(t),chain(at),chain(bt)), whereaandbare 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 stringsssuch that vertex cloning happened.You don't need triples. You need to calculate for each

tnumber of strings that contain it and subtract those in which all occurences oftare preceded by the same charactera. Only pairs (chain(t),chain(at)) are needed for that.Is it really possible to solve problem J in 19 minutes or is that AC in 19 mins some kind of a hoax xd?

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

Btw how to solve it?

Suppose that all coefficients of polynomials are in

F_{2}. The key observation:P(x)^{2}=P(x^{2}).For an integer

nand a polynomialQ, letf(n,Q) be the number of nonzero terms inP^{n}*Q.In case

nis odd, usef(n,Q) =f(n- 1,PQ).In case

nis even, first decomposeQinto "even part" and "odd part":Q(x) =R(x^{2}) +xS(x^{2}). Thenf(n,Q) =f(n/ 2,R) +f(n/ 2,S).This way we reach only

O(2^{d}logn) states.Did you actually implement this as recursion with memoization? Because it looks like it's rather hard to fit into the memory.

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)^{2}=P(x^{2}), soP(x)^{n}=P(x^{2a0})P(x^{2a1})...P(x^{2am - 1}). Now let's calculate (imaginary) DP[i][j]: we multiplied firstipolynomials and interested in coefficient forx_{j}(basically DP[i] is a product ofifirst polynomials). We can see that ifj_{1}andj_{2}have different remainders modulo 2^{ai}then they are independent, so our DP is a set of 2^{ai}independent DPs, corresponding to different remainders modulo 2^{ai}. Each of these DPs have onlydinteresting 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.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)^{2}=P(x^{2}), I base my solution on fact that is odd iffi_{1},i_{2}, ...,i_{k}are submasks of n in binary system.J is a well-known problem in China:

Version 1

Version 2

We were afraid that it could be well-known(

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

How to solve A, E, H?

H: Note that if

kis the largest value of an-beautiful multisetA, then the elements ofAthat are smaller thankhave to form ak- 1-beautiful multiset. If there arexcopies ink, then we getx·k+ (k- 1) =n, sokis a proper divisor ofn+ 1. Conversely, taking such akand addingxcopies ofkto ak- 1-beautiful multiset, we always get an-beautiful multiset. We can hence use dp to compute the number and total size ofn-beautiful mutisets as followsThe number of states used in computing

DP[n] is equal to the number of divisors ofn+ 1.Edit: Does someone have a good bound on the number of divisors summed over divisors of

nto bound the total runtime? (Something better than this comment.)Actually, intended solution for H was with convolution repeated times, but we failed to set time limit properly.

If number of good pairs of good divisors for maxtests is something like

d(n)^{2}/ 60 (withd(n) ≈ 60000 then good luck with distinguishing it from :PYes, the number of good pairs is around 10

^{7}, 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

^{18}(and make bigger TL also). I'd say it's controversial whether it'd really improve the problem.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)

A: Let's say that

a_{i}dominatesa_{j}ifi,jare incompatible anda_{i}>a_{j}. For everyk, we can color it with the length of the longest dominating chain ending witha_{k}(soa_{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

mtwo numbers: The largest colorCof a valuea_{i}contained in the mask and the maximum numberDof bits in which some sucha_{i}differs fromm. Ifmoccurs inaandD≥k, then we incrementCand setDto 0. From every mask, we can transition to other masks by setting another bit. The total runtime isO(22·2^{22}+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.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 atCand compute for every vertexvthe contribution of towerstnot located in the subtree ofCcontainingv. For a fixed towert, its contribution on a vertexvin a different subtree only depends on the depth (=distance fromvtoC). Moreover, as a function of this depth, the contribution is piece-wise constant with pieces of lengthk(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 modkseparately, 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 , even for

kup ton.Can I be solved in O(nlogn)?

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

After the contest BledDest told me the solution and also mentioned that it's about the same as in 911G - Mass Change Queries. 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.

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_{1},p_{2}) = (1 -p_{1})p_{2}+p_{1}(1 -p_{2}). First compress thel_{i}andr_{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 .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 (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.

My solution is in . It's unnecessarily complicated. Basically, I have decomposed the segments into 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 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.

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.

I had some wrong ideas at the beginning and wrote more complicated

O(pn) solution (p= 101). I basically maintain the count for eachp_{i}, and compute the matrix multiple inO(p) time with appropriate precomputation.What are those precomputations? It seems, I can't squeeze my by any means)

WLOG assume 0 ≤

L_{i}<R_{i}≤ 2N. For each interval [i,i+ 1] we can have the histogram of eachp_{i}occurence with difference arrays. Letq_{pi}be such occurence. Then we want to calculateM_{0}^{q0}×M_{1}^{q1}× ... whenM_{i}is the state transition matrix for probabilityi. We can simply precompute those powers inO(pn) time, Now we can calculate the answer inO(p) time.Oh, I thought about the difficulty of storing all of them and never even cosidered multiplying them right away. Nice approach, thanks)

This is probably the fastest to code solution.

I tried to implement the same idea after the contest, but got WA. Probably because I did multiplication/division instead of log addition/subtraction which cost a lot of precision error. How did you know that you need to do the calculations in logarithmic scale at first?

It's a common practice actually, without logarithms it's possible to construct a test in which at first the product becomes very small (of order 2

^{ - n}), and after that it becomes close to 1 again, but the precision is lost in the first phase.