Could not find any post for today's open cup. Let's discuss the problems here. How to solve F and G?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 10:45:45 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
For the second time in recent opencups, I wasted half of the contest trying to solve a problem with 100 OKs without any success. How to solve I?
Recursively find smallest suffix.
Sort suffixes of the string (suffix array), iterate them in increasing order. The answer for suffix starting at position $$$i$$$ is $$$j-i$$$, where $$$j$$$ is the minimum position encountered so far that is larger than $$$i$$$.
But how to find the smallest suffix on segment? We when we cut the string in two halves the order of suffixes in the right half may change.
The recursive segments are formed such that the order of suffixes is the same as in whole string.
Proof: Let $$$s_k\ldots s_r$$$ be the smallest suffix of $$$[l, r]$$$. Now in $$$[l, k - 1]$$$, consider two positions $$$i$$$ and $$$j$$$, with $$$i < j$$$. If the comparision of suffixes at $$$i$$$ and $$$j$$$ ends before index $$$k$$$, clearly they follow the same order as in the whole string. Else, the suffix starting at $$$j$$$ must be smaller (as required) as the suffix starting at $$$k$$$ is the smallest. In the right half, nothing has changed so the order is preserved there as well.
Problem I
Is it well-known? Neither of us knew Lyndon word decomposition and it took 2hour to come up with the cool stack-based solution that is much harder than intended. On the other hand I don't think it's reasonable to believe 100 teams knew it.
Curious to know your solution. We solved it using just suffix array and set. For any suffix_starting_at_i, we tried to find the smallest suffix_starting_at_j, where j > i and suffix_starting_at_j < suffix_starting_at_i. for ith suffix ans should be j — i.
F:
if $$$sum(Arr) \leq C$$$ it's trivial else:
it can be easily proved that the answer is at least $$$C - max(Arr)$$$ consider the following greedy algorithm iterate over the array decreasingly if $$$Arr[i] \leq Cur_C$$$ then $$$Cur_C := Cur_C - Arr[i]$$$, it's easy to prove that at the end $$$Cur_C$$$ will be less than all elements not used in the array.
Now let's call the elements used set $$$L$$$ and the elements not used set $$$R$$$. I want to add $$$i - j$$$ to $$$Cur_C$$$ such that $$$Cur_C + i - j \leq C$$$ and $$$i-j$$$ is maximum and $$$i$$$ is the sum of a subset of $$$L$$$ and $$$j$$$ is the sum of subset of $$$R$$$.
you can just consider all sums less than a certain $$$X$$$ for both sets that $$$X$$$ for me was $$$10^5$$$ but I think it should work if it's equal $$$2 * (C-Cur_C)$$$.
Well I think the correct bound is somewhere near $$$N \times C^{0.5}$$$ (consider standard deviation). I'm surprised that $$$10^5$$$ passes, but anyway with bitset I think you can do as much as 5000000.
The intended solution is some fancy 1998 paper. It is inspiring though.
No, I think the correct bound for his solution is much worse. I think some tests where this value is $$$O(nW)$$$ may be constructed (but I am too lazy to think about them).
The bound is $$$w_{\text{max}} \sqrt{N}$$$, and union bound is pretty loose, so its not so surprising.
Which paper are you referring to?
Probably this one: Linear Time Algorithms for Knapsack Problems with Bounded Weights. The paper derives an $$$O(n \max(a_i))$$$ algorithm for the subset sum problem. Luckily I read that paper some time ago, so we used this approach during the contest.
I solved F purely using cutoffs.
At first I have sorted $$$a$$$ in non-increasing order. Using a recursive function solve(prefix, sum) I try to add the element if it makes sense (with the current answer) and not using it after.
I can't prove it works fast, but the runtime is just 7ms (absolutely nothing). Maybe the tests were weak.
p = suffix sum of a
UPD: the tests are weak
I guess I have a really really high upper bound first of all it's obvious like my solution that the answer will become at least $$$N - max(Arr)$$$ in $$$N$$$ operations then each $$$N$$$ operations either the answer will increase or the recursion will terminate so you will make at most $$$ N ^ 2 $$$ operations this is a really really high upper bound thou as I don't take into account other factors.
I guess it's not that easy. When I call the function, I make a "promise" that the answer will increase, which is not true all the time.
Your solution will call
recat least $$$2^{98}$$$ times in this test:It is indeed. Nice test.
What about this case:
Your solution will greedily take all $$$10000$$$, but the only optimal solution is taking all $$$9999$$$, so on the second step you need to run a knapsack up to $$$9999 \cdot 9999$$$ ~ $$$1e8$$$.
How to solve Problem Q(Easy Puzzle) ? And the problem J(Program Optimization) can solved with Cartesian tree ? Because my solution for J with segment tree gived TLE ,because we have a constant when two position updates and it will be 2*log2(n) .
J: Since the input is a permutation it can be solved in O(n + q). Mex from an interval is the minimum element outside this interval (Add $$$n$$$ to the beginning of the array). So you can keep the the minimum among prefix and suffix.
Update can be done in O(1) since you should only update consecutive elements (at most two values from the prefix and suffix change).
Query can be answered in O(1) checking both prefix and suffix outside the interval.
Code
Thanks mnaeraxr! I understasnd .
How so solve D?
$$$p_0 = (1, 2, 0, 3)$$$
$$$p_1 = (3, 0, 1, 2)$$$
$$$p_2 = (0, 1, 3, 2)$$$
The value of substring $$$s_l, ... , s_r$$$ is the product of permutations $$$p_{s_l} \cdots p_{s_r}$$$. You can calculate number of substrings with value $$$q$$$ for each $$$q$$$ with a simple dp with $$$24n$$$ states. Then for each query $$$t$$$ you calculate value of $$$t$$$ and print answer for this permutation.
Thank you. Very beautiful idea!
How do we prove that for two strings with the same value, there exists a sequence of operations which transforms one to the other?
UPD Fixed the duplicated text problem and incorrect motiavation for equality $$$(stst^2)^3 = e$$$.
After some reductions ($$$1$$$ is expresisble through $$$0$$$ and $$$2$$$), we arrive on the following group presentation: $$$\langle s^2 = e, t^3 = e, (st)^4 = e \rangle$$$.
Then, consider a reduced word over $$$s$$$ and $$$t$$$ in the sense that it does not contain $$$s^2$$$ and $$$t^3$$$ substrings. It looks like $$$t^p \cdot (st^{a_1}) \cdot (st^{a_2}) \cdot \ldots \cdot (st^{a_b}) \cdot s^q$$$, where $$$b$$$ is the number of $$$st^{a_i}$$$ "blocks" ($$$b$$$ may be equal to zero), and $$$1 \leqslant a_i \leqslant 2$$$ for all $$$i$$$ from $$$1$$$ to $$$b$$$. The vallue $$$p$$$ corresponds to the prefix of $$$t$$$'s before any block, hence $$$0 \leqslant p \leqslant 2$$$, and, similarly, $$$0 \leqslant q \leqslant 1$$$.
Suppose that there are two consequitive blocks with $$$a$$$'s equal to $$$1$$$. Then, we can use the equality $$$(st)^2 = (t^2 s)^2$$$ (follows from $$$(st)^4 = e$$$) and make the number of blocks smaller by "merging" the $$$t$$$'s at the beginning to the end of the previous block or the starting prefix of $$$t$$$'s and merging $$$s$$$ on the end to the beginning of the next block or the ending suffix of $$$s$$$'s (said merges can trigger numerous collapses because of $$$s^2$$$ and $$$t^3$$$ substrings, but then the number of blocks will decrease even more). Similarly, if there are two consequtive blocks with $$$a$$$'s equal to $$$2$$$, then we can use the equality $$$(st^2)^2 = (ts)^2$$$ (follows from $$$(ts)^4 = s (st)^4 s = ss = e$$$) and make the number of blocks smaller again.
Hence, in the shortest possible word for any given element of the group, blocks $$$st$$$ and $$$st^2$$$ in the middle alternate. How many blocks can there be? Let's notice (see the end of the comment for how to come up with such equalities) that $$$(stst^2)^3 = ((t^2s)^3 (st^2))^3 = ((t^2s)^2 t)^3 = (t^{-1} (st^2 s) t)^3 = t^2 (st^2s)^3 t = e$$$, because $$$(st^2s)^3 = (st^2s) \cdot (st^2s) \cdot (st^2s) = st^6s = ss = e$$$. Similarly, $$$(st^2st)^3 = e$$$ (here we just used that $$$(ab)^n = e \Rightarrow (ba)^n = (a^{-1} ab a)^n = a^{-1} (ab)^n a = a^{-1} a = e$$$).
Hence, if there are at least $$$3$$$ blocks, we can replace them with no more than $$$2$$$ blocks by applying $$$(stst^2)^3 = e$$$. For example, $$$stst^2st = (stst^2st)^{-1} = t^2stst^2s$$$ and there are only two blocks after dealing with $$$t^2$$$ to the left and $$$s$$$ to the right.
Hence, there are only $$$3$$$ possibilities for $$$p$$$, $$$2$$$ possibilities for $$$q$$$ and $$$5$$$ possibilities for middle blocks: $$$a = \varnothing, a = (1), a = (2), a = (1, 2), a = (2, 1)$$$. Therefore the resulting group has size at most $$$30$$$. But we know already that $$$S_4$$$ with $$$24$$$ elements is good enough, hence the group is indeeed $$$S_4$$$ (because otherwise it contains $$$S_4$$$ as a proper subgroup and would therefore have at least $$$48$$$ elements).
If you are wondering why we ended up with $$$30$$$ elements instead of $$$24$$$: that's because the elements with $$$a = (1, 2)$$$ and $$$a = (2, 1)$$$ are actually equal. For example, $$$t^2 (st^2 st) = (st st^2)$$$, because both are $$$e$$$ when multiplied by $$$tst^2s$$$ from the right: the right-hand side for trivial reasons and the left-hand side because $$$(t^2s)^4 = e$$$.
This whole argument may look like magic (especially $$$(stst^2)^3 = e$$$ part), but recall that we already have an educated guess of how the resulting group will look like! If we assume that it is indeed $$$S_4$$$, with $$$s$$$ being a transposition and $$$t$$$ being a $$$3$$$-cycle, then $$$stst^2$$$ is a (different) $$$3$$$-cycle. Hence, $$$(stst^2)^3$$$ should be equal to $$$e$$$ (if it is not, our guess is not correct). Hence, we can instantly judge which equalities are worth trying to prove and which are not.
Holy cow...
Some text is duplicated
Thanks. Should be fixed now.
To explain number of accepts, I think this was well known for some people. I think this is very tricky and very hard to come up with, but very similar problem already appeared a few years ago.
How to come up with these specific permutations?
We generated all possible permutations and checked for some set of three permutations that fulfill those requirements:
Code
Just pen and paper and trial and error with a bit of insight. 22 should be identity, so its permutation should be some number of swaps. 000=012=id, so 0 should be some number of 3-cycles. And $$$1=0^{-1}2^{-1}$$$. That already greatly reduces a search space to just a few cases that you can try after assuming that they act on a small set, 4 should be a good guess (where you basically have two cases — that there is 1 swap in 2 and that there are 2 swaps). I used 5, but now I see that all my permutations fix fourth element xD.
It is clear that if for two words I get different permutations then they are not equivalent, but I don't know why if they give the same permutation then they are equivalent.
Or you mean the opposite? When they are same you know they are equivalent. But if they are not, how do you prove that they are not equivalent? Or in other way, how do you know that two different permutations are not equivalent?
I am pretty sure I didn't mean the opposite. Changing characters according to rules doesn't change the permutation, so equivalent words -> equal permutations.
Yes. I think we both said the same thing from different perspective.
Two equivalent words would generate same permutation. But how does one know that two non equivalent words won't generate same permutation.
No idea ¯\_(ツ)_/¯
Other than what you mention, thinking in hindsight about this problem, there are several gaps on my reasoning.
To use Cayley Theorem we need to prove before finding elements, that group generated by $$$0$$$, $$$1$$$ and $$$2$$$ is finite (otherwise chances are that no subgroup of permutations exists).
I just looked for 3 permutations that satisfy constraints given in the problem, but I needed to add some requirements that looked somehow artificial (but were necessary):
Otherwise, I'd easily hit a "solution" where all elements are $$$0$$$ (the identity).
How can I justify that those additional constraints are actually required for this to work.
Problem K here has the same idea I guess.
How to solve J and L?
LoNgLoNgDoUblE J's solution https://codeforces.me/blog/entry/77187?#comment-619345
We spend a lot of time on J and 90% of that time was before realizing that elements of array are in fact distinct. It is a very bad practice to put such crucial information in input section only. Please write it either before this section or make it bold or at least use a word "permutation" which is easier to spot.
I am sorry. Next time I will put them in the statement with bold fonts.
Graphs in problem E could be remembered from an incredibly painful problem It's no wonder that in that case its authors decided to give ABSOLUTELY TRASH SAMPLES and it is very hard to get answers for some meaningful cases in bruteforced way, so participants were basically left to submit their answers blindly in a problem where there are a ton of weird formulas and corner cases.
Some small cases (in case this is useful for someone):
I thought every opencups were gonna be annoounced on un_nik's telegram group :( Missed this one cuz of it.
G is extremely well known. Appeared in WF 2006 and Croatian OI 2012. But here it has weights, so when changing your code remember to correctly plug in the number.
It wasn't known to me :) How to solve it?
You can do something similar to bitonic path, so instead of going back and forth just find two paths.
Preprocess with Floyd Warshall. Let $$$DP[x][y]$$$ = (minimum distance to make forward path end at $$$x$$$, and backward path starts at $$$y$$$). You move either end of path ($$$DP[x][z], DP[z][y]$$$), or you swap two paths ($$$DP[y][x]$$$). This represents all possible paths (sorry I don't remember why, but I guess it's not too hard to prove). Anyway, in this state graph, you can use Dijkstra to find the shortest path to the desired state.
Why can I swap two paths?
Edit: There is another explanation in https://codeforces.me/blog/entry/77187?#comment-619429, combining with yours I guess I have the whole picture now. Thanks for the explanation!
It seems that I have missed the problems you have mentioned perfectly -- In my OI career, I almost have upsolved all COCI problems, until 2010, while the 2006 task is too old for me. :( Little shame to bring such classical problem back to the table.
I am a teaching assistant in an "Introduction to Combinatorics" course on my university and something like a month ago when I was preparing a class about matchings and flows I gave my students a mathematical version of today's problem A, where you need to prove that such tiling is possible if and only if there is no triangle pointed upwards with side k such that there are more than k unit forbidden triangles in it. Too bad mine solution was rather not constructive, through Hall's condition, so we didn't manage to get it accepted today (however Radewoosh already upsolved it with some naive heuristics searching for matching).
If anybody wants to read my proof of that fact, you can find it on the last page here: https://www.mimuw.edu.pl/~nayar/wdk_2020/wdk_2020_cwiczenia_6_rozwiazania.pdf (and exact statement here: https://www.mimuw.edu.pl/~nayar/wdk_2020/wdk_2020_cwiczenia_6_zadania.pdf)
I heard that it is from some IMO shortlist.
Ah yeah, I forgot to mention that if I'm not mistaken it's from shortlist :D. Should have checked that during the contest...
Yeah, IMO Shortlist 2006, C6
Lol, I even have third post in this topic xD. Sadly it sounds pretty obscure xD No wonder it is shorter xD
K, anyone?
K is yet another boring tree dp problem. If $$$x = 0$$$ this is just counting matchings in the tree. Let's generalize for nonzero $$$x$$$.
First of all, let's subtract $$$x$$$ from all $$$d_i, a_i, b_i$$$. Now we have an edge of weight $$$x$$$ between any two vertices, including loops.
Now let's cover the tree with cycles (of length 1 or 2) and paths without using edges of weight $$$x$$$. After that we need to merge some paths so that they all become cycles, using edges of weight $$$x$$$. If we have $$$k$$$ paths we will multiply current value by $$$\pm x^k$$$. The sign depends on how we connect paths, so we need to count the number of ways to get both signs. It's easy to see that if $$$k \geq 2$$$, then those numbers are equal and we don't add anything to the answer. So we actually need to cover the tree by at most one path and some cycles. This is easily done with dp with a few cases.
BTW, this problem seems much easier than I, but I haven't read it during contest. :(
It again amazes me how you absolutely discard whole insight specific to some problem to sum it up as "another boring tree dp". It's not the freaking tree dp where the hardness lies.
What’s hard otherwise?
Well to me it's not obvious you should do this... for example, why should it be easily solvable if you put complete graph of edges between all vertices. Who will tell me it's going to cancel for k >= 2? Plus, there are other ways of computing a determinant, such as doing some row/column operations.
Hmm, I just putted $$$x=0$$$, and the direction became crystal clear. All member of our team had created problem about this thing ;)
Well, each one of us thought about this problem for some nontrivial time and we got no idea. Only after competition I got an idea that terms for $$$k \ge 2$$$ cancel out and felt pretty proud for observing this and then solution followed rather quickly. There are tons of ways you can approach problems with determinants (operations on rows to make it prettier, doing Laplace expansion, using some little known formulas e.g. even this looks fairly relevant: https://codeforces.me/blog/entry/74131, etc. etc. etc.). And, as stupid as it sounds, I didn't realize that case $$$x=0$$$ can be thought about as cycle covers on a tree since I imagined it as matchings in a bipartite graph... (it is sometime the better way, but definitely not here though and that was not the hard part)
I think that people who can't properly judge where the difficulty lies in various problems will have troubles in becoming good teachers (since how do you focus on explaining the hard part if you don't know what the hard part is?).
I'll be very grateful if aid somehow become my teacher. The pain would be worth.
G:
If I draw path from s to t I want to wonder how path from t to s may look like. What I've drawn is kind of a general shape of it (some horizontal blue segments may consist of one vertex). I want to go from $$$s$$$ and kind of simultaneously build two paths, one black and one blue.
On the beginning I use Floyd-Warshall what allows me to make bigger jumps (that's surprisingly important). I want to have $$$dp[a][b]$$$ which means the lowest cost such that I already built some partial solution which contains path from $$$s$$$ to $$$a$$$ and from $$$b$$$ to $$$s$$$. I want to have two types of transitions. Look at four colored vertices (in red, green and yellow) and call them $$$a, b, c, d$$$ from left. I want to have transition from red pair $$$(a, b)$$$ to green pair $$$(a, c)$$$ and it has cost $$$dis[b][c]$$$. I want to have a transition from green pair $$$(a, c)$$$ to yellow pair $$$(c, d)$$$ with cost $$$dis[c][d] + dis[d][a] - p_a$$$. Some special case if that blue horizontal segment is one vertex may be needed. I compute these dp values in Dijkstra fashion.
How to solve H?
Balkan Mathematical Olympiad 2018 p3
Problem B can actually be done in $$$O(N^2)$$$ with more usage of the structure of the problem:
Consider a balanced string with $$$a$$$ $$$1$$$s and $$$b$$$ $$$0$$$s ($$$a+b=n$$$). Now, call the "score" of a substring the sum of the values of each of its characters, where each $$$1$$$ has value $$$b$$$ and each $$$0$$$ has value $$$-a$$$.
The total score of the string is $$$0$$$, so the substrings of any length $$$L$$$ also have an average score of $$$0$$$. Furthermore, two substrings of length $$$L$$$ are within $$$1$$$ of each other iff their score is within $$$b-(-a)=n$$$. (Note that all substrings of length $$$L$$$ have the same remainder mod $$$n$$$).
This implies that a string is balanced iff every substring has a score strictly between $$$-n$$$ and $$$n$$$. Therefore, the scores of all prefixes must lie within an interval of size $$$n-1$$$. Note that for a given interval, the string we produce is uniquely determined (as there is only one feasible value for each prefix).
Now, consider all strings that are produced as the interval ranges from $$$[0, n-1]$$$ (the lex max balanced string) to $$$[-(n-1), 0]$$$ (the lex min balanced string). If a prefix initially has score $$$K$$$, then when we change the interval from $$$[K-n+1, K]$$$ to $$$[K-n, K-1]$$$, we must change the prefix so that its score becomes $$$K-1$$$, without changing any neighboring prefix scores. This is achieved by switching $$$10$$$ to $$$01$$$ at the location of the prefix.
Finally, we can compute the number of solutions for strings with $$$a$$$ $$$1$$$s in $$$O(N)$$$ by maintaining the number of mis-matched characters as we sweep from the highest to lowest interval. Each prefix is updated only once, so only $$$2N$$$ characters are updated total.
Code
Let me share some comments about this contest: I did it at the last day on MW-ByteDance Camp as an informal team (Not my opencup team and it won't be rated for me though..).
Totally agree with Swistakk about that E: I immediately remembered that problem in Gp of China last year when I saw this one. I even thought it may come from the same author... But anyway, we decided to ignore it during the contest since I haven't upsolved that Gp of China problem up to now...
As for I, I had no idea about why ByteDance Camp's participants could solve it so fast and it seemed like a problem that everyone know should about it...I don't...But I know it is at least about Lyndon Words. Then I went to google Lyndon Array...That's why I could solve it in the first 30mins...Definitely not a right way to solve any contest, but...I really don't want to be trapped in it...Link
I was trying to play tricks in F well before another guy found a post in stackoverflow about it...wtf...But I do like the way to solve it...When there is a way to solve some problems which seem NP-Hard, it is really funny. Here are two links Link1 and Link2
For many other problems, sorry I knew nothing about MO. Maybe it is time to try solving great number of MO problems as what rpeng had told me...
Anyway, many thanks to the author and it is a very educational contest.
How to solve C?
C is simple idea with cases work: $$$digitroot(A) \equiv sumdigit(A)$$$ modulo $$$B - 1$$$.
I give up with E. It's close to impossible getting it accepted with current samples xd. It's passing a lot of various tests that me and Marek were able to generate answers to, but still WA on second test (not that it surprises me). Can anybody give me his correct code? maroonrk or ftiasch maybe?
EDIT: Uh, got AC, last bug was some overflow xd (i.e. lack of %P). But how is it possible to solve it during contest? Ideologically it is not that hard... But getting all the formulas and corner cases right is a tremendous effort.
I feel it's just a luck. I tried several approaches for counting and canceling, and, though all of them required some casework, one of them looked tractable and I was able to implement it somehow.