masonsbro's blog

By masonsbro, history, 8 months ago, In English,

Next Saturday, May 4, at 6pm UTC, 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.

The problem set was created by myself and arknave.

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

Details will be sent out to everyone who's registered closer to the contest date.

Update: The contest url is utipc19.kattis.com.

Update 2: The solutions are up.

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder: this is tomorrow! Good luck to all participants.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +67 Vote: I do not like it

Maybe you can shift the start so it doesn't collide with CF round?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Unfortunately we won't be able to move our room reservations. To everyone competing in person, see you tomorrow!

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      Oh, I didn't know that there is onsite participation. Maybe you can do parallel contest for online participants and postpone only that one?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Only one hour left, but there is no mail with login and password. Should I worry?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You can register yourself at the Kattis site

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      You mean, I don't need additional registration for this contest. Only for Kattis?

      P.S. Thank you I could log in. The problem was that after even I logged into Kattis using Facebook, on the contest page it asks me to log again and didn't have the button to log-in using Facebook. Now I found the way to do it.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Great contest! Is there going to be an editorial published? We did not solve B,I,L and are curious about the intended solutions.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I will give a few hints.

    B: It's only necessary to know some parities to be able to say if a number is lucky or not.

    I: $$$C = V - E$$$ Where $$$C$$$ is number of components, $$$V$$$ is number of vertex and $$$E$$$ is number of edges, you can pre calculate the value o $$$V$$$ and $$$E$$$ for each number, this doesn't work if there is cycles, but in the problem the graph is a cactus so you can count the number of cycles that you should exclude.

    L: If you can solve the problem for $$$N = 2$$$ you can solve for bigger $$$N$$$, you should think about inclusion-exclusion here.

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Could you elaborate a bit on which parities you mean for B. I am familiar with using the parity of the prefix to determine the number of "even sum substrings" for any string, but am not able to correctly turn this into a recurrence that accounts for all possible strings in the range.

      Thanks!

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My solution to problem I uses an implicit disjoint set for each factor which solves the problem on a general graph as well. I was curious about what the intended solution was since I couldn't think of a solution that used the fact that the graph was a cactus.

»
7 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Really happy to get the first place! :) Our team didn't start well but caught up later.

Here are our solutions for some of the problems:

Problem B — Serious Business

Idea
My Code

Problem I — Cactus Shoppe

Idea
Code

Problem L — Neural Networks

Idea
Code

I am curious about what is the intended solution for Problem I, since my solution is not related to cactus.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Several teams used that solution for I. We didn't think of that! If you want to think about the intended solution, here are some bounds that I think would require it: 2 <= n <= 10^6, 1 <= m <= 10^6, 1 <= value <= 10^6, time limit 2.5s.

    Intended solution
    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      The difference between F log F and F div(F), where div is the maximum number of divisors of any number under F is hard to differentiate here, especially when supporting multiple languages. $$$\log_2(1\,000\,000) \approx 20$$$, and $$$div(1\,000\,000) = 240$$$. I think the time limit would have to be even lower. I think both solutions are nice. :)

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I see. Good observation of the cactus! That's interesting.

      P.S. Thanks for the solution!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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