Lewin's blog

Invitation to NAIPC 2018 / Grand Prix of America
By Lewin, history, 7 years ago, In English

NAIPC is coming up on March 24th (start time here). More information about the contest can be found on this page. More information on how to register can be found on this page. You can register in teams of up to 3. This contest will be on Kattis.

Several hours later, it will be available as an open cup round as the Grand Prix of America (start time here). Please only participate in one of them, and don't discuss problems here until after the open cup round has ended.

The deadline to register for the contest on Kattis is March 21st. You will need an ICPC account to register (you can see instructions in the link above on how to create one if needed).

You can see some past years' problems here: 2017, 2016

UPD 1: The deadline to register your team is soon.

UPD 2: Contests are over

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

G seems to be a problem related to matroid intersection.

How to solve it?

Edit : I figure out how to solve it after reading the author's solution.

Spoiler
→ Reply
»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

How to solve B and J ?

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

I: I had to optimize my O(NM) solution (and still it takes 1.8s). Is there something faster?

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

    You can speed up to N+M**2 if you can multiply polynomial by constant in O(1).

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

    I wasted 90min in problem I and still cannot solve :(

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

    Here is O(NM) solition, which doesn't seems too optimized for me, and works for 0.5s

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

C ?

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

    Do operations in reverse. Then i-th operation xors segment of length i.

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

      How to solve after that ?

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

        Do the bitmask dp. dpi, msk is 1 iff after i operations we can get the mask msk. The answer is not more than n, so it works in O(2nn2).

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

As I see, author solution on F is O(n+m). Problem can be solved in O(log^3) (or probably, log^2). The idea is follwing. We can find a number of points below passing through point (x, y) in O(logn) time. This can be done by Euclid-like approach.

We want to find a first direction (i.e irreducibly p, q), such that number of point below p/q is less then number we need. To do that, we can go down by Stern–Brocot tree

Formally, that means that we have (p1/q1 which is lower bound for our direction, and p2/q2 to upper bound). Initially, 0/1 and 1/0 are them. If (p1+p2)/(q1+q2) is too far, p1/q1 is answer, because there is no numbers between them. If not, we can change one of bounds to it. Although we have linear number of steps, we have O(logn) number of "turns", that is positions, where we change different bound with previous one. Number of steps before next turn, can be found using binary search. If do so, O(log^2) times of solving "points under line" problem needed.

solution

Code here is a bit messy, because i was rewring linear searches of turns to binary on last minutes, but solves problem in 9ms.

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

    Instead of Stern-Brocot tree, we binary searched on doubles, and used chain fraction to find the closest p/q with q<=n. This is log**2 I think.

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

    If you use normal binary searches, the runtime is Θ(log3). If you use exponential search instead, the runtime drops to Θ(log2). (Exponential search runs in where t is the number steps you end up taking.)

    During the contest I just improved the constant of the linear searches by trying steps of 1000 first.

    → Reply