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/
I believe you meant to say 1PM? Do you also want remote teams to sign up on the form?
1PM Central Time (US) = 6PM UTC (I think).
I think it's 7PM UTC (daylight savings time)
Yes, please do fill out the form!
https://www.timeanddate.com/worldclock/fixedtime.html?msg=UT+Austin+Fall+2019+Invitational+Programming+Contest&iso=20191123T13&p1=24&ah=5 for convienience
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 ?
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.
Solving F using segment tree was the intended solution, some people had nicer solutions which ksun described
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
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.
Will the problems be posted on open.kattis.com if we want to run the contest virtually?