Блог пользователя vamaddur

Автор vamaddur, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I believe you meant to say 1PM? Do you also want remote teams to sign up on the form?

»
5 лет назад, # |
  Проголосовать: нравится 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 ?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Solving F using segment tree was the intended solution, some people had nicer solutions which ksun described

    • »
      »
      »
      5 лет назад, # ^ |
      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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will the problems be posted on open.kattis.com if we want to run the contest virtually?