XX Open Cup GP of Bytedance

5 years ago, # |

+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?

→ Reply

jtnydv25

5 years ago, # ^ |

-12

Recursively find smallest suffix.

→ Reply

egor_bb

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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.

→ Reply

jtnydv25

5 years ago, # ^ |

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

→ Reply

zscoder

5 years ago, # ^ |

Problem I

→ Reply

5 years ago, # ^ |

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.

→ Reply

Jami_CSEDU

5 years ago, # ^ |

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.

→ Reply

TripleM5da

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

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.

→ Reply

300iq

5 years ago, # ^ |

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

→ Reply

jtnydv25

5 years ago, # ^ |

+10

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

→ Reply

5 years ago, # ^ |

Which paper are you referring to?

→ Reply

fleimgruber

5 years ago, # ^ |

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

→ Reply

okwedook

5 years ago, # ^ |

← 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

→ Reply

TripleM5da

5 years ago, # ^ |

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.

→ Reply

okwedook

5 years ago, # ^ |

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.

→ Reply

5 years ago, # ^ |

← 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

→ Reply

okwedook

5 years ago, # ^ |

It is indeed. Nice test.

→ Reply

5 years ago, # ^ |

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

→ Reply

computerbox

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

+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

→ Reply

computerbox

5 years ago, # ^ |

Thanks mnaeraxr! I understasnd .

→ Reply

5 years ago, # |

+10

How so solve D?

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

-10

Thank you. Very beautiful idea!

→ Reply

cerberus97

5 years ago, # ^ |

+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?

→ Reply

Kaban-5

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

Holy cow...

→ Reply

Golovanov399

5 years ago, # ^ |

+18

Some text is duplicated

→ Reply

Kaban-5

5 years ago, # ^ |

← Rev. 2 →

+10

Thanks. Should be fixed now.

→ Reply

5 years ago, # ^ |

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.

→ Reply

5 years ago, # ^ |

How to come up with these specific permutations?

→ Reply

5 years ago, # ^ |

-8

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

Code

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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?

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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.

→ Reply

5 years ago, # ^ |

-8

No idea ¯\_(ツ)_/¯

→ Reply

5 years ago, # ^ |

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

→ Reply

zscoder

5 years ago, # ^ |

Problem K here has the same idea I guess.

→ Reply

LoNgLoNgDoUblE

5 years ago, # |

+11

How to solve J and L?

→ Reply

computerbox

5 years ago, # ^ |

+11

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

→ Reply

5 years ago, # |

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

→ Reply

ftiasch

5 years ago, # ^ |

+34

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

→ Reply

5 years ago, # |

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

→ Reply

Benq

5 years ago, # ^ |

← 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

→ Reply

Savior-of-Cross

5 years ago, # |

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

→ Reply

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

+18

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

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Why can I swap two paths?

Edit: There is another explanation in https://mirror.codeforces.com/blog/entry/77187?#comment-619429, combining with yours I guess I have the whole picture now. Thanks for the explanation!

→ Reply

ftiasch

5 years ago, # ^ |

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

→ Reply

5 years ago, # |

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)

→ Reply

5 years ago, # ^ |

I heard that it is from some IMO shortlist.

→ Reply

5 years ago, # ^ |

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

→ Reply

300iq

5 years ago, # ^ |

Yeah, IMO Shortlist 2006, C6

→ Reply

5 years ago, # ^ |

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

→ Reply

mnbvmar

5 years ago, # |

K, anyone?

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

+10

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

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

+10

What’s hard otherwise?

→ Reply

ksun48

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

+10

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

→ Reply

5 years ago, # ^ |

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://mirror.codeforces.com/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?).

→ Reply

5 years ago, # ^ |

+26

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

→ Reply

Balkan Mathematical Olympiad 2018 p3

5 years ago, # |

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

→ Reply

Nson

5 years ago, # |

How to solve H?

→ Reply

300iq

5 years ago, # ^ |

→ Reply

scott_wu

5 years ago, # |

+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

→ Reply

chenjb

5 years ago, # |

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

→ Reply

nfssdq

5 years ago, # |

How to solve C?

→ Reply

chemthan

5 years ago, # ^ |

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

→ Reply