By vamaddur, history, 3 weeks ago, ,

Tomorrow, November 23, at 7pm UTC (1pm CST), the University of Texas at Austin is hosting an "invitational" (actually open to anyone) programming contest. The contest will last 5 hours and is intended to be similar to a North American ICPC regional contest in terms of difficulty. There will be 10-14 problems, and we encourage you to follow ICPC rules: teams of 3 on one computer, using no online resources.

If you want to participate, you can sign up using the registration form: https://forms.gle/yXE4j5JyKhhQENbD9

The link to contest is: https://utipcf19.kattis.com/

• +33

 » 3 weeks ago, # |   +8 I believe you meant to say 1PM? Do you also want remote teams to sign up on the form?
•  » » 3 weeks ago, # ^ |   0 1PM Central Time (US) = 6PM UTC (I think).
•  » » » 3 weeks ago, # ^ |   0 I think it's 7PM UTC (daylight savings time)
•  » » 3 weeks ago, # ^ |   +13 Yes, please do fill out the form!
 » 3 weeks ago, # | ← Rev. 2 →   0
 » 3 weeks ago, # |   0 Someone solved F using segment tree adding arithmetic progression on range ?, i got TLE with my implementation O(n log n) but with a bad constant, Maybe someone have a more simple solution ?
•  » » 3 weeks ago, # ^ |   +16 It can be solve in linear time, in fact for each number c with k occurrences you can compute the answer for how many intervals have majority x in O(k). The main idea is that you can find some points (using prefix sums) so that if you cut the interval atthose points, no intervals dominated by x can cross them. Once you have found all such points, the intervals left which contain at least 1 occurrence of x, also must have small length.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Solving F using segment tree was the intended solution, some people had nicer solutions which ksun described
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 My idea was the following, for a fixed type of element $x$, construct an array $b$ such that $b_i = +1$ $if$ $a_i = x$, $-1$ otherwise, then accumulate $b$, if a interval $b[l...r]$ is dominated by $x$ then $b_r - b_{l-1} > 0$, so we have an $O(k * n log n)$ solution using fenwick tree or ordered set for count how many $b_{l-1}$ satisfy the condition for a fixed $b_r$, for the $O(n log n)$ solution, before accumulate all the elements of $b$, compress all sub-array of $b[l...r] = -1$ on a single element with value $-(r-l+1)$ then maintain on a segment tree for each position $i$ how many numbers are lower or equal that $i$ so for a element of $b$ (without compress) the answer is some position of the segment tree, if the elements is compressed then the answer is a range (note that none of the prefix sum that ends on the compressed element is candidate), and the update for a element without compress is add $+1$ on some $range[j, +oo]$, if the element is compressed the update is like add $1, 2, 3, ..., w, w, ..., w$ on some $range[j, +oo]$. This is my submission for more detail. I tested it locally and it runs on ~6 seconds with $n=k=10^6$, i know that my segment tree not is too fast, so probably i should need change them :( UPD I got AC improving my segment tree
•  » » » » 3 weeks ago, # ^ |   -12 Yeah your idea sounds pretty much exactly like what i did, I agree that your segtree's constant is probably too large. Sorry, we made the bounds kinda tight to help counter potential cheese solutions.
 » 3 weeks ago, # |   0 Will the problems be posted on open.kattis.com if we want to run the contest virtually?