XX Open Cup GP of Bytedance

5 лет назад, # |

+50

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?

→ Ответить

jtnydv25

5 лет назад, # ^ |

-12

Recursively find smallest suffix.

→ Ответить

egor_bb

5 лет назад, # ^ |

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$$$.

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

jtnydv25

5 лет назад, # ^ |

+21

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.

→ Ответить

zscoder

5 лет назад, # ^ |

Problem I

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

Jami_CSEDU

5 лет назад, # ^ |

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.

→ Ответить

TripleM5da

5 лет назад, # |

← Rev. 2 →

+26

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)$$$.

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

300iq

5 лет назад, # ^ |

+28

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).

→ Ответить

jtnydv25

5 лет назад, # ^ |

+10

The bound is $$$w_{\text{max}} \sqrt{N}$$$, and union bound is pretty loose, so its not so surprising.

→ Ответить

5 лет назад, # ^ |

Which paper are you referring to?

→ Ответить

fleimgruber

5 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

okwedook

5 лет назад, # ^ |

← Rev. 2 →

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.

Code of the function

p = suffix sum of a

void rec(int i, int curr) {
    if (curr > c || ans == c) return;
    chmax(ans, curr);
    if (i == n) return;
    if (curr + p[i] <= ans) return;
    rec(i + 1, curr + a[i]);
    if (curr + p[i + 1] > ans) rec(i + 1, curr);
}

UPD: the tests are weak

→ Ответить

TripleM5da

5 лет назад, # ^ |

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.

→ Ответить

okwedook

5 лет назад, # ^ |

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.

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

+20

Your solution will call rec at least $$$2^{98}$$$ times in this test:

n = 99 + 98
c = 99 * 99
a = [100] * 98 + [99] * 99

→ Ответить

okwedook

5 лет назад, # ^ |

It is indeed. Nice test.

→ Ответить

5 лет назад, # ^ |

+20

What about this case:

n = 9998 + 9999
c = 9999 * 9999
a = [10000] * 9998 + [9999] * 9999

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$$$.

→ Ответить

computerbox

5 лет назад, # |

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) .

→ Ответить

5 лет назад, # ^ |

+21

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

→ Ответить

computerbox

5 лет назад, # ^ |

Thanks mnaeraxr! I understasnd .

→ Ответить

5 лет назад, # |

+10

How so solve D?

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

+50

$$$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.

→ Ответить

5 лет назад, # ^ |

-10

Thank you. Very beautiful idea!

→ Ответить

cerberus97

5 лет назад, # ^ |

+38

How do we prove that for two strings with the same value, there exists a sequence of operations which transforms one to the other?

→ Ответить

Kaban-5

5 лет назад, # ^ |

← Rev. 12 →

+50

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.

→ Ответить

5 лет назад, # ^ |

Holy cow...

→ Ответить

Golovanov399

5 лет назад, # ^ |

+18

Some text is duplicated

→ Ответить

Kaban-5

5 лет назад, # ^ |

← Rev. 2 →

+10

Thanks. Should be fixed now.

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

5 лет назад, # ^ |

How to come up with these specific permutations?

→ Ответить

5 лет назад, # ^ |

-8

We generated all possible permutations and checked for some set of three permutations that fulfill those requirements:

Code

→ Ответить

5 лет назад, # ^ |

← Rev. 4 →

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.

→ Ответить

5 лет назад, # ^ |

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?

→ Ответить

5 лет назад, # ^ |

-8

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.

→ Ответить

5 лет назад, # ^ |

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.

→ Ответить

5 лет назад, # ^ |

-8

No idea ¯\_(ツ)_/¯

→ Ответить

5 лет назад, # ^ |

+10

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):

All $$$i$$$ should be distinct from the identity.
All pairs of $$$i$$$ were different.
$$$1^2 \neq 0$$$ (we already know that $$$1^4 = 0$$$)

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.

→ Ответить

zscoder

5 лет назад, # ^ |

Problem K here has the same idea I guess.

→ Ответить

LoNgLoNgDoUblE

5 лет назад, # |

+11

How to solve J and L?

→ Ответить

computerbox

5 лет назад, # ^ |

+11

LoNgLoNgDoUblE J's solution https://codeforces.me/blog/entry/77187?#comment-619345

→ Ответить

5 лет назад, # |

+161

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.

→ Ответить

ftiasch

5 лет назад, # ^ |

+34

I am sorry. Next time I will put them in the statement with bold fonts.

→ Ответить

5 лет назад, # |

+50

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.

→ Ответить

Benq

4 года назад, # ^ |

← Rev. 2 →

Some small cases (in case this is useful for someone):

Spoiler

1 1 1 -> 0
2 2 1 -> 0
3 3 1 -> 0
4 4 1 -> 0
5 5 1 -> 60
6 6 1 -> 540
7 7 1 -> 6300
8 8 1 -> 80640
9 9 1 -> 1088640
10 10 1 -> 15422400
11 11 1 -> 229521600
12 12 1 -> 592511979
13 13 1 -> 156697187
14 14 1 -> 344914432
15 15 1 -> 359613562
16 16 1 -> 425606191
17 17 1 -> 512123764
18 18 1 -> 616189691
19 19 1 -> 158211109
20 20 1 -> 962944897
21 21 1 -> 513231905
22 22 1 -> 102324521
23 23 1 -> 226769461
24 24 1 -> 566206183
25 25 1 -> 358816403
26 26 1 -> 489196957
27 27 1 -> 876055909
28 28 1 -> 985173136
29 29 1 -> 791893044
30 30 1 -> 690300360
1 2 2 -> 0
2 3 2 -> 0
3 4 2 -> 0
4 5 2 -> 0
5 6 2 -> 0
6 7 2 -> 0
7 8 2 -> 0
8 9 2 -> 0
9 10 2 -> 90720
10 11 2 -> 2721600
11 12 2 -> 69854400
12 13 2 -> 796255993
13 14 2 -> 702655678
14 15 2 -> 496068260
15 16 2 -> 21791734
16 17 2 -> 984532396
17 18 2 -> 382394489
18 19 2 -> 862720752
19 20 2 -> 913611516
20 21 2 -> 759141792
21 22 2 -> 887313313
22 23 2 -> 970432554
23 24 2 -> 456258681
24 25 2 -> 648826809
25 26 2 -> 18288183
26 27 2 -> 685751383
27 28 2 -> 866437147
28 29 2 -> 630027108
29 30 2 -> 760347251
30 31 2 -> 16072278
1 3 3 -> 0
2 4 3 -> 0
3 5 3 -> 0
4 6 3 -> 0
5 7 3 -> 0
6 8 3 -> 0
7 9 3 -> 0
8 10 3 -> 0
9 11 3 -> 0
10 12 3 -> 0
11 13 3 -> 0
12 14 3 -> 0
13 15 3 -> 0
14 16 3 -> 0
15 17 3 -> 377884570
16 18 3 -> 533330007
17 19 3 -> 984432494
18 20 3 -> 667987232
19 21 3 -> 838083387
20 22 3 -> 974454655
21 23 3 -> 591001656
22 24 3 -> 765783512
23 25 3 -> 271763550
24 26 3 -> 612976847
25 27 3 -> 699605662
26 28 3 -> 712402977
27 29 3 -> 896014750
28 30 3 -> 302774408
29 31 3 -> 889714663
30 32 3 -> 374354978
1 4 4 -> 0
2 5 4 -> 0
3 6 4 -> 0
4 7 4 -> 0
5 8 4 -> 0
6 9 4 -> 0
7 10 4 -> 0
8 11 4 -> 0
9 12 4 -> 0
10 13 4 -> 0
11 14 4 -> 0
12 15 4 -> 0
13 16 4 -> 0
14 17 4 -> 0
15 18 4 -> 0
16 19 4 -> 0
17 20 4 -> 0
18 21 4 -> 0
19 22 4 -> 0
20 23 4 -> 0
21 24 4 -> 0
22 25 4 -> 201980476
23 26 4 -> 873305499
24 27 4 -> 710632815
25 28 4 -> 946031135
26 29 4 -> 470486935
27 30 4 -> 298572085
28 31 4 -> 270532941
29 32 4 -> 834786964
30 33 4 -> 232895273

→ Ответить

Savior-of-Cross

5 лет назад, # |

I thought every opencups were gonna be annoounced on un_nik's telegram group :( Missed this one cuz of it.

→ Ответить

5 лет назад, # |

+10

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.

→ Ответить

5 лет назад, # ^ |

+18

It wasn't known to me :) How to solve it?

→ Ответить

5 лет назад, # ^ |

+10

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.

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

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!

→ Ответить

ftiasch

5 лет назад, # ^ |

+10

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.

→ Ответить

5 лет назад, # |

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)

→ Ответить

5 лет назад, # ^ |

I heard that it is from some IMO shortlist.

→ Ответить

5 лет назад, # ^ |

Ah yeah, I forgot to mention that if I'm not mistaken it's from shortlist :D. Should have checked that during the contest...

→ Ответить

300iq

5 лет назад, # ^ |

Yeah, IMO Shortlist 2006, C6

→ Ответить

5 лет назад, # ^ |

Lol, I even have third post in this topic xD. Sadly it sounds pretty obscure xD No wonder it is shorter xD

→ Ответить

mnbvmar

5 лет назад, # |

K, anyone?

→ Ответить

5 лет назад, # ^ |

+38

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.

→ Ответить

5 лет назад, # ^ |

+10

BTW, this problem seems much easier than I, but I haven't read it during contest. :(

→ Ответить

5 лет назад, # ^ |

+18

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.

→ Ответить

5 лет назад, # ^ |

+10

What’s hard otherwise?

→ Ответить

ksun48

5 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

5 лет назад, # ^ |

+10

Hmm, I just putted $$$x=0$$$, and the direction became crystal clear. All member of our team had created problem about this thing ;)

→ Ответить

5 лет назад, # ^ |

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?).

→ Ответить

5 лет назад, # ^ |

+26

I'll be very grateful if aid somehow become my teacher. The pain would be worth.

→ Ответить

Balkan Mathematical Olympiad 2018 p3

5 лет назад, # |

+20

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.

→ Ответить

Nson

5 лет назад, # |

How to solve H?

→ Ответить

300iq

5 лет назад, # ^ |

→ Ответить

scott_wu

5 лет назад, # |

+40

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

→ Ответить

chenjb

5 лет назад, # |

← Rev. 6 →

+18

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.

→ Ответить

nfssdq

5 лет назад, # |

How to solve C?

→ Ответить

chemthan

5 лет назад, # ^ |

C is simple idea with cases work: $$$digitroot(A) \equiv sumdigit(A)$$$ modulo $$$B - 1$$$.

→ Ответить