You are given an $$$N$$$x$$$N$$$ grid and $$$K$$$ people. Put all people in the grid such that the minimum manhattan distance between any two is maximized. What's the best solution for this problem? Is it NP?

Hello, all! Can you share some problems which we try to optimize the answer? Last two years we had such tasks in IOI, so it would be nice if you share some other problems you know!

Thanks in advance!

Hello, all! I am thinking about the following problem:

Given a tree with N vertices and some constant D. You are to find maximum number of vertices you can color if distance between any two colored vertices should be at least D.

How to solve this problem better than $$$O(N^2)$$$? I think for $$$O(N^2)$$$ we can use greedy approach; choose the farthest available vertex from the root.

Any helps are appreciated.

Hello, all! I need your help for this problem. Basically, we have n vectors originated in (0, 0) and we are to find a subset of these vectors such that length of their sum is maximum.

How to solve knapsack problem efficiently if we are given the count of items (i.e. we can buy i'th item cnt_i times)? I'm looking for something like O(n·C) or O(n·C·log(cnt)) (you got the idea) where C is the capacity of the knapsack. Any ideas are appreciated.

Hello. I read the tutorial of the problem Roman Digits but can't understand it. My thought is we need to count different k such that there exist a, b, c, d with the following conditions:

(i)a + 5b + 10c + 50d = k

(ii)a + b + c + d = n

If we replace a from (ii) we get 4b + 9c + 49d = k - n. Can't continue.

Any helps are appreciated.

Hello Codeforces. I'm interested in this problem, and I actually came up with this. It seems standard, but unfortunately, I couldn't get any results from the internet. So the statement follows:

We have a cycle of numbers (1, 2, 3, ..., n) arranged like . Also, we need to do queries reversing a part of the cycle. For example, if the cycle is , and if query is the (3, 1) (reverse path from 3 to 1), the new cycle will be: . After all these queries, we need to print the new cycle. Note that we don't have any "ask" queries. Constraints are about 10⁵.

Thanks in advance.