vamaddur's blog

UT Austin Fall 2019 Invitational Programming Contest
By vamaddur, history, 4 years ago, In English

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/

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1PM Central Time (US) = 6PM UTC (I think).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it's 7PM UTC (daylight savings time)

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Yes, please do fill out the form!

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://www.timeanddate.com/worldclock/fixedtime.html?msg=UT+Austin+Fall+2019+Invitational+Programming+Contest&iso=20191123T13&p1=24&ah=5 for convienience

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -12 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply