XVIII Open Cup: GP of Korea

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

Auto comment: topic has been updated by ainta (previous revision, new revision, compare).

→ Ответить

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

Is it a closed contest? How to register for it ? My Yandex username password does not seem to work it says "Authorization failed. Please, try again or contact your coordinator"

→ Ответить

300iq

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

What is Grand Prix?

→ Ответить

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

I couldn't make much from that discussion...perhaps you can answer my question...

→ Ответить

Petr

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

+10

It is an onsite contest with multiple sites, called "sectors". You can't get a username/password to participate online, but you could try to organize a sector in your university/community.

→ Ответить

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

Who are the relevant people to contact if I'd like to do this at my university?

→ Ответить

Petr

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

The relevant page is http://opencup.ru/index.cgi?data=oci/rules/sector&menu=index&head=index&class=oci&ncup=oci . It's in Russian, but I hope Google Translate can help, and the email address (new.opencup...) is somewhat clear there.

On Codeforces the coordinator's handle is snarknews, but probably an email is a more reliable way.

→ Ответить

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

Thanks,Petr

→ Ответить

Aidos

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

+16

How to solve L and J?

→ Ответить

rsFalse

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

Div.2 contest ended 40 mins later, hopefully no-one answered during contest time.

→ Ответить

ksun48

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

+30

Problem + solution is more or less equivalent to problem E here: https://agc002.contest.atcoder.jp/tasks/agc002_e.

Surprised that not more teams solved it.

→ Ответить

paulwang

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

Do you mean it's equivalent to problem J of this contest?

→ Ответить

ksun48

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

← Rev. 2 →

+13

Yes. Both of them can be transformed to a game about taking steps up and right in the coordinate plane, and in this problem (like the other one) one can prove that the answer for [L,R] is the same as the answer for [L+1,R-1] as long as the game is at least two turns away from the end.

→ Ответить

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

+18

I'm the author of problem J. I already knew the AGC problem, but I never noticed the equivalence relation. I think it is hard to find the relation between two problems without the key idea([L,R] = [L+1, R-1]).

→ Ответить

ksun48

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

Maybe that's true. For me, once I drew a diagram of state in the 2-dimensional plane, the connection came instantly.

→ Ответить

ko_osaga

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

Key idea what? Isn't it just a_i = N - (maximum j s.t [i, j] is monotone for 1 ≤ i ≤ N?

Well, we have queries, but whatever...

→ Ответить

chenjb

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

Sorry about replying after 2 month. But when I try to upsolve this problem, I cannot figure out why Win[b, e] = Win[b + 1, e - 1] for other cases. Could anyone please teach me? Thank you.

→ Ответить

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

← Rev. 2 →

Solution for J:

Let A[b, e] = a_b, a_b + 1, ..., a_e.

For the initial sequence A[b, e], Win[b, e] = 1 if Alice wins the game. otherwise Win[b, e] = 0.

If A[b, e] is monotone(nonincreasing or nondecreasing), then Win[b, e] = 0. For other cases, Win[b, e] = (!Win[b, e - 1])|(!Win[b + 1, e])

Key idea : Except a few cases, Win[b, e] = Win[b + 1, e - 1]. then we can calculate Win[b, e] easily by its b + e value.

For a sequence S, if there is a contiguous monotone subsequence with length L and there is no contiguous monotone subsequence with length L + 1, we call S is L - monotone.

If A[b, e] is (e - b + 1) - monotone, then Win[b, e] = 0.
If A[b, e] is (e - b) - monotone, then Win[b, e] = 1.

If A[b, e] is (e - b - 1) - monotone

3-a. A[b, e - 2] is monotone or A[b + 2, e] is monontone

without loss of generality, A[b, e - 2] is monotone. Then Win[b, e] = !Win[b + 1, e] = Win[b + 2, e] = !Win[b + 3, e] = .... it continues until Win[i, e] which A[i, e] is monotone. So if we precalculate L(e) := (the minimum value of x that satisfies A[L(e), e] is monotone) for all e, then we can calculate Win[b, e] by the value L(e).

3-b. A[b + 1, e - 1] is monotone

It is easy to show that Win[b, e] = 0

For other cases, it is easy to show that Win[b, e] = Win[b + 1, e - 1].

→ Ответить

SYury

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

+26

I think it's not true that we can calculate Win[b, e] in 3-a only from L(e), it depends on L(e - 1) as well. For example, consider this case:
1 2 3 4 5 5 5 5 5 5 4 5

→ Ответить

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

Yes, I missed it. We can calculate Win[b, e] by the value of L(e - 1) and L(e).

→ Ответить

lzw4896s

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

← Rev. 4 →

Could you explain more about win[b, e] = win[b + 1, e − 1]? I could not understand how the formula in the pdf solution win[b, e] = (!win[b, e − 1]) | (!win[b + 1, e]) = (win[b, e − 2] & win[b + 1, e − 1])|(win[b + 1, e − 1] & win[b + 2, e]) would lead to win[b, e] = win[b + 1, e − 1]. What if win[b, e − 2] = win[b + 2, e] = 0, win[b + 1, e − 1] = 1?

→ Ответить

rsFalse

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

Hint for N (div.2)? Output of test #1 given in example is incorrect answer for judge.

→ Ответить

rsFalse

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

How did you solved it?

→ Ответить

300iq

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

← Rev. 2 →

+16

How to solve B, I?

→ Ответить

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

Was problem I solvable with suffix array or suffix automata was intended? And how to solve F?

→ Ответить

300iq

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

+13

F: dp[mask][root] in O(3ⁿ * n²)

→ Ответить

eddy1021

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

Is there any better solution for F?

Our solution in O(3ⁿ × n²) got TL on the first try. And, finally got an OK with some constant optimization.

→ Ответить

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

intended solution is O(3ⁿ * n).

→ Ответить

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

Could you please describe it?

→ Ответить

.o.

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

+46

dp[mask, root] = min{dp[mask^submask][root] + dp[submask][child] + cost(root, child) × popcount(submask) × (N - popcount(submask))}.

This is O(3ⁿ·n²), as you know -- 3ⁿ for iterating mask and submask, and n² for iterating root and child.

However, min{dp[submask][child] + cost(root, child) × popcount(submask) × (N - popcount(submask))} only depends on submask and child. So precalculate them during the process, and it will reduce the complexity by n.

→ Ответить

snuke

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

My recurrent formula in O(3ⁿ * n):

add root (it costs weight[current root][new root] * popcount(mask) * (n - popcount(mask))
merge two trees have same root (no cost)

→ Ответить

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

Nice!

→ Ответить

adamant

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

+19

I: Build suffix automaton for the whole string. After that you can start feeding string s to the automaton. If you go to the vertex v, this will mean that we added + 1 occurrence for all its suffixes.

Hopefully all such suffixes lie on path via suffix links of vertex v, thus you have to add + 1 on the path from v to the root (noting that any vertex u has multiplicity len[u] - len[link[u]]) and output sum of squares of numbers in all vertices taking into account their multiplicities. It can be done with heavy-light decomposition. Code: code.re/bbW

→ Ответить

_Ash__

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

Can you somehow get rid of the HLD part ? maybe by flating the tree ?

→ Ответить

adamant

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

I don't know. HLD part is very simple here, though, why would you want to get rid of it?

→ Ответить

ko_osaga

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

← Rev. 4 →

I is solvable with suffix array + divide and conquer.

The answer for a single string can be calculated if you know Sum(LCP[i, j]) for all unordered pair i < j. kriii will explain details / proofs in this part. We should solve this problem for every suffix.

One naive strategy is to build a suffix array sfx[], and LCP array lcp[] for a given string, then performing a[min(sfx[i], sfx[j])] += Min(lcp[i+1], lcp[i+2], ..., lcp[j]) for all i < j.

We can solve this by divide and conquer — We will process this for all pairs $\text{[math]}$ . The strategy is to batch process all pairs with same LCP value in "conquer" stage.

We start from m / m+1. If LCP[m] < LCP[m+2], then we increase right end, otherwise we decrease left end. To generalize. If current left end is s, and right end is e, then you know either $\text{[math]}$ or $\text{[math]}$ have same LCP value. (I strongly recommend you to simulate by hand). In the end, we end up having O(nlgn) "slices" to process.

Now, we can process those slices with sweep line, in total O(nlg²ⁿ) time.

→ Ответить

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

Nice explanation, thank you. Did not come to the last step with sweep line though.

→ Ответить

_Ash__

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

Can you elaborate on how can you calculate the answer for a single string with Sum(LCP[i, j]) for all unordered pair i < j ?

→ Ответить

Zool

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

← Rev. 2 →

What is test 53 for A?

→ Ответить

kriii

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

+10

That is the ordinary random case N=99998, L=94633361, R=475442794.

→ Ответить

Danylo99

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

+15

How to solve A and F?

→ Ответить

eddy1021

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

← Rev. 2 →

+28

A: For each point, the possible center of the donut to contain that point is also a donut. After adding each score to the corresponding region, the answer is the one with maximum score. It's equivalent to add the score to a square with length r and subtract the score to a square with length l.

It can be done with sweep line and segment tree in $\text{[math]}$ .

→ Ответить

I_Love_Tina

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

+18

Very nice problems, thank you for preparing them.

→ Ответить