ir5's blog

Kyoto University Programming Contest 2016
By ir5, history, 8 years ago, In English

Hi,

I would like to invite you to Kyoto University Programming Contest (KUPC), which will be held on 2 Oct. (4:00 — 9:00 GMT). Problem writers consist of several students in Kyoto University. The contest will be held on AtCoder.

Contest Link

The contest duration is 5 hours, and there will be 11 problems. KUPC has been held every year for about 5 years in Japan, but this is the first time to provide English problem statements.

I participated in the test round of this contest. The first a few problems are easy, so I'm sure everyone can enjoy the contest. On the other hand, a few problems from the last are probably interesting and though enough for high rated coders. We hope lots of people will compete in our contest. Good luck and have fun.

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

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

As far as I know, KUPC has been one of the most intetesting contests in Japan. I believe this year's KUPC will be even more enjoyable. So I highly recommend you to participate in the contest :)))) Don't miss it!

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

Is it rated? I can't find anything in the blog or the contest link.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Will there be editorials?

If not, how to solve anything starting from Problem E. :)

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Wondering how to solve problem E

I thought that for goats close enough(|dx| ≤ 2 and |dy| ≤ 2), the optimal solution would be the convex hull of surrounding points of these goats. And convex hull shall be caculated respectively for goat flocks (am I right using flock?) far away. But it was wrong. This solution even passed less data points than another solution calculating convex hull for all goats.

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

    Ok after reading someone's code, I think I get the idea (not sure if it's complete) :

    Construct a flow graph where the outer layer of the grid (i.e. the area around the grid, outside the grid) is the source, and the Xs are sinks. Let the empty squares has capacity 1 and the Xs has capacity ∞. Also, there is an edge from a square to an adjacent square with capacity ∞. Now, the maximum flow of this graph is the answer.

    I think this is true because otherwise there would be an augmenting path from the source to sink, so the sheeps can escape.

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

      Yeah, it's the Max-flow Min-cut theorem

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

      Another construction of flow graph I learned from other's code is like this:

      There's a source src and a sink dst.

      For every cell in the input, there's two vertices, say, ui and vi, where i is the id of the cell, H * W at most. (You can imagine they are two copies of layer of the input)

      For every 'X', there are two edges: One connecting src and ui with capacity inf. Another connecting ui and vi with capacity inf.

      For every '.', there is an edge connecting ui and vi with capacity 1.

      For every cell that is on the border of the input, there is an edge connecting vi and dst with capacity inf.

      For every cell whose id is i, there are edges connecting its neighbours back from vi to uj with capacity inf, where j is the id of its neighbours.

      But I still can't understand why minimum cut(or maximum flow) is the answer. Though there is some intuition, I can not convince myself about this...

      → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Any ideas on how to solve G? I couldn't figure out how to use the second condition.

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

    The condition is confusing, but the solution isn't: just take all distinct substrings of length L (for the best L).

    To prove this, note that the second condition on strings of equal length is just "the strings are different", and if there is any smaller substring in the set, you don't lose anything by adding characters to the beginning or end of it, as you're only making it harder for the second condition to be violated.

    → Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I see people with short solutions for H. What is the correct idea to solve the problem?

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I might be missing something really obvious but I can't come up with a proof for the solution to C. Can somebody kindly help me out? The solution I 'guessed' was to just use Y=127 every time.

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

    The parity of the number of times each bit is set in the final set of numbers is fixed.

    This means that any solution that has more bits set in a position than your solution has at least 2 more bits set in that position, which is impossible since in your solution at most one bit is not set in each position (the one from the number which is not 127).

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

      That's awesome, thanks a lot!

      → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

FYI The editorial is out (in Japanese though) : link

It would be nice if someone could explain editorials for HIJK (got stuck halfway using Google Translate)

→ Reply