pllk's blog

NCPC 2018 open contest
By pllk, history, 6 years ago, In English

The Nordic Collegiate Programming Contest (NCPC) 2018 will be held tomorrow. It is the subregional ICPC contest for Denmark, Estonia, Finland, Iceland, Norway, and Sweden.

There will also be an open contest in which anyone can participate. The open contest will begin at the same time as the official contest, Saturday October 6 UTC 9:00, and its duration is five hours.

Welcome! You can also discuss the problems here after the contest.

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

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

I did A for most of the contest and never realized that the sum of weights is at most 1e8 :/

I also asked my friends from other teams, and they hadn't noticed it either. Would have been nice if the problem statement didn't hide it like that (usually it's okay to just quickly look at the constraints)

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

    FUCK

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

    This problem (from 2017 Vietnam National Round) put the trick of hiding constrant to increase difficulty to a brand new level. It is as easy as Div2-B once you understand the statement properly, and yet not even a single team solved that problem in the contest.

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

How to solve F and G?

We had a solution for F which didn't pass: Choose a pair of corners and consider a line passing through them. Then for rectangles intersecting with the line, do some 2 pointers to check maximum number of rectangles within distance l.

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

    G: click

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

    It is possible that the optimal line segment only passes through one corner.

    Btw, I also don't know the solution of F.

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

How to solve K? I thought of a DP on tree solution but it is O(NK^2)

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

    The amount of ways to colour the tree with at most z colours is z * (z - 1)(n - 1). This could also be calculated with a O(N) dp. Then you can just use inclusion-exclusion to calculate the answer, giving time complexity O(Klog(n)) or O(KN) with the dp.

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

How to solve problem J ?

I have come up with some observations:

(1): We can easily calculate the number of 0s x and the number of 1s y from a and d.

(2): It is possible to construct a string if and only if x*y = b+c.

(3): When we swap 01 to 10, the number of 01 decreases by 1 and the number of 10 increase by 1.

I am not really sure if (2) or (3) is correct.

My algorithm is to start with a string that starts with x 0s and ends with y 1s, and then move the 0 until we get the desired b and c, but it did not pass the third test :(.

UPD: I got Accepted. Some corner cases that you need to consider:

  • When a=0, the number of 0 can be 0 or 1.

  • The result need to be non-empty.

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

The editorial is published.

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

Now in Gym.

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

Can somebody give me a hint on D? I have read the editorial.

Spoiler

My question is: how should I guess $$${j}$$$?

Thanks!

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

    Try all possible j?

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

      I just don't understand how should I check all possible j in $$${O(1)}$$$ time

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

        Why O(1)? The constraints are low.

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

    You just iterate over all possible values and take the best one. This will give a time of $$$k^2$$$ for that part, as suggested by the colour coding.

    → Reply