Problem: 1360H - Binary Median

I just wanted to share a solution to this problem that I couldn't catch in the editorial or the comments!

Observation 1:
We start with $$$2^m$$$ numbers and remove n of them. Therefore, our new set consists of ($$$2^m-n$$$) numbers. The median of this set of numbers is the number such that there are exactly $$$\lfloor (2^m-n-1)/2 \rfloor$$$ numbers less than it.

To find this number, we can binary search for the left most number in the range $$$[ 0 , 2^m-1 ]$$$ such that there at least $$$\lfloor (2^m-n-1)/2 \rfloor$$$ numbers less than it.

How do we check if a number "mid" has at least $$$\lfloor (2^m-n-1)/2 \rfloor$$$ numbers less than it?

Another binary search! => We can binary search on the set of removed numbers to find the index of the right most one such that it is $$$<= "mid"$$$. Then the numbers less than mid are simply $$$ mid - index$$$ !

My Submission for reference: 220757973

Thanks for reading!

Let me know if I have made any mistakes or you have any questions!

Problem: 1859D - Andrey and Escape from Capygrad

As I went through the editorial ( video and text ), I saw that they were a bit complicated, and that there was an easier way ( with possibly the same idea ) to solve this problem.

Observation 1 ( as mentioned in both editorials ): It is never beneficial to teleport left. Therefore, each segment (l , r , a , b) can be re written and uniquely defined as (l , b , a , b).

Observation 2 ( also as mentioned in both editorials ): It is always optimal to teleport to b. Therefore, each segment can be re written as (l , b).

Final Observation: If any two segments (l , b) overlap, then we can travel between them ( combine them into one larger segment ).

Solution: Store all segments as (l , b) and combine them ( via sorting on left value ). Now when given a query, we just need to find whether it lies in any segment. If so, then we print the right end of that segment. Else we print the query itself! This can be done via binary search.

My Submission for reference : 219396665

Thanks!

Given an array of numbers (size n , ( 1<= n <= 1e6 ) ), answer q queries ( 1 <= q <= 1e5 ) of the type: How many numbers in the range [l,r] are within the range [l,r].

If it helps, an additional constraint is that half the array will be -1, and for any value $$$a_i$$$ such that $$$a_i != -1$$$ , $$$a_i > i$$$

I am not sure how to efficiently answer such queries.
This comes from trying to solve this problem :380C - Sereja and Brackets :)

Submission: 215289964
Problem: 1487E - Cheap Dinner

Here is my logic and "analysis" of the Time Complexity of this solution. Please do let me know where I am going wrong!

I am not sure how to proceed on speeding this up. ( or if I should give up and look at the editorial :) )

Here is the problem: 1793D - Московские гориллы
and my submission: 210771147

After taking a peek at the editorial, it looks like pretty much the same thing they are saying so I am not sure what I am missing at the moment.

A quick summary of my logic:

Hello! I have been trying to find the cause of RTE in this submission: 208940837 and have unfortunately been highly unsuccessful in doing so, hence this plea for help.

Here is my logic behind the program:

Note that each of the "queries" form a directed graph that has max indeg across all nodes as 1.

Any cycles made in this graph mean that is impossible -> 0.

Now, if some value a is more used than another value b, then it is obvious that at minimum #a's used is at least 1 more than #b's used.

This holds for longer paths -> a>b>c>d -> at minimum we use 3 a , 2 b , 1 c , 0 d

After we find coins that must be used using the above idea, since we must maintain any inequality a > b, if we use a coin of type b, we must use a coin of type a as well, so we can merge these two values together into a+b, and repeat doing so for longer paths -> a>b>c>d -> a+b , a+b+c , a+b+c+d

After collecting all possible coin values, it is a simple dp knapsack problem.

I am not sure if my logic is completely wrong and hence the RTE or what I am missing.

Please do let me know!

For Problem B, would the maximum $$$a_{i}$$$|$$$a_{j}$$$ = 2n-1 -> so f(n-1 , n) = n^2-n-k-2nk?

How would you solve f(i,n) > f(n-1,n) in that case?

Problem: 1554B - Cobb
Editorial : https://mirror.codeforces.com/blog/entry/93321

Is there a way to see problems that we have solved in mashups on their actual page?

If not, I think this would be a great feature!

Thanks!

Here is my submission : 207504363

and my thinking:

The answer to each query $$$a_{ij}$$$ is the size of the unique elements in row i and column j plus the absolute value of the difference between the index of $$$a_{ij}$$$ in its column and row

Do let me know what I am missing!

Thank you in advance.