Count pairs of positive integers such that
- ;
- .
Answer test cases.
,
If is "large", then is larger, and is even larger. So you expect to be small. Let's do some calculations.
Let (note that ). Then, . It follows that , so . So you only need to iterate over at most values of . The rest is relatively easy.
people numbered are standing in a row. Person wears color . Answer (offline) queries of the format below.
- You are given integers and . Considering only people , how many pairs of people wearing the same color can be formed at most?
, ,
If you use Mo's Algorithm, the problem is reduced to "after answering a query , find a way to answer queries and fast (i.e., move one of the endpoints by position).
The answer only depends on the number of colors which appear an odd number of times. Every time you visit a segment , you should store:
Moving one of the endpoints by position just changes the number of appearances of a single color, so you are done.
You are given a tree, where each node has a color . Calculate the sum of over all pairs () such that and have the same color.
,
First, solve the subtask " (all nodes have the same color)".
- If you cannot solve this subtask, you cannot solve the full problem.
- If you can solve this subtask, it might be useful to solve the full problem!
In general, even if the problem does not have subtasks, try to invent them on your own.
Now, solve the subtask "each color appears exactly times".
Let's consider each color separately, and suppose it appears times. The naive solution iterates over all pairs of that color, which is very slow if is big. But there is an alternative solution for a single color. Just choose which solution to use according to the value of .
Let's calculate the sum of over all pairs such that .
Suppose the color appears times. The first solution requires , and the second solution requires . You should choose the faster solution, so the complexity becomes . But what's the total complexity?
If the complexity for a single color was , you would get in total. However, you get a "slowdown" factor of . But this is still fast enough ( in total)!
Try to solve the problem in if you really want! There are several solutions.
This is an interactive problem.
There is a hidden binary array whose elements are zeros and ones. There are rounds. In the -th round:
- The interactor asks you to find the -th zero from the left ( may change between rounds, and you know the new value of only at the beginning of the round).
- You can choose some subarrays and ask . However, you can ask at most queries in total.
- You have to print the position of the -th zero, then is set to and a new round starts.
, ,
If you don't know anything about the array, you need queries to pass a single round (with a binary search). If you already know the entire array, of course you can pass a round without asking any additional query. Can you do something in the middle?
First, divide the array into blocks of size and ask the sum of all these blocks. (You have just considered the "edge cases" and , but maybe some other value of works better.)
Then, for each round, you can already find which of these blocks contains the -th zero! So the binary search requires queries instead of .
The total number of queries you ask is at most . There are several values of which make you ask less than queries (for example, works).
is not necessarily , it depends on the problem!
In this case, if you want the "optimal" value of , you have to minimize .