HolkinPV's blog

By HolkinPV, 8 years ago, translation,

413A - Data Recovery

Count min and max values in given array of length m. If the min value is less then given min or the max value is greater the given max the answer is Incorrect.

Count value 0 ≤ need ≤ 2, which equals to minimal number of elements which should be added in given array so that the min value will become min and the max value will become max. Then answer is Correct if n - m ≥ need. Otherwise answer is Incorrect.

413B - Spyke Chatting

Process all queries and count some values: for each employee we will count number of messages which weer sent by this employee and for each chat we will count number of messages which were sent to this chat. Then the answer for some employee equals to sum of messages sent to all chats in which he participates minus all messages sent by him to some chats.

413C - Jeopardy!

Firstly choose all not auction questions and answer on them. So we have only auctions. Sort them in non-decreasing order. Consider each size of suffix of auctions and answer them on their initial price and try to answer other questions by multiplying by 2.

It could be explained in this way: less than the cost value, the less you need to multiply your balance by 2. Also more than the cost value more profitable to take it for initial value.

413D - 2048

Consider some state in your game. Note that, we should maintain the maximum suffix if values in descending order. Also, we will maintain only first k - 1 powers of two and keep in mind if have already k-th power of two or greater. In fact in violation of this order we can not use these numbers because values could only increase.

So, we will count dynamic dp[i][mask][j], where i — size of considered elements, mask — mask of first k - 1 powers of two in descending order, j — do we have already the k-th power of two or greater (0 or 1). There are two possible transitions by 2 or 4. If the current element equals to 0 make both transitions.

413E - Maze 2D

We will consider queries one by one. Firstly check if the one cell of the query is reachable from the second. Find all connected components. If the cells are in different connected components, the answer is -1.

Otherwise assume that both cells are situated in columns with exactly one obstacle. To find the answer for such cells we should count the length of the path between these columns using array of partial sums.

To count this array consider all columns from left to right and store the last type of column with exactly one obstacle (down obstacle or up obstacle). If in column j the type changes set in the cell j of the array value 1, otherwise set value 0. In this case of query the length of the path between cells equals to sum of absolute differences between column indexes and counted partial sum between these columns.

If the column with the left cell has no obstacles find the nearest column with exactly one obstacle to the right. If the column with the right cell has no obstacles find the nearest column with exactly one obstacle to the left. So we get the situation considered above. Be careful if there is no columns with exactly one obstacle between given cells.

• +23

 » 2 years ago, # |   0 Can someone please help me out in Problem D? What to store in $mask$? How to update it?
 » 2 years ago, # | ← Rev. 2 →   0 What actually mask is refering in this dp state? What actually we have to store or refer through mask?
 » 14 months ago, # | ← Rev. 2 →   0 Can somebody please explain to me Problem C? I am not getting the problem statement. Also why are we multiplying the result by 2?