[Official] Contest 4 Hints

Hints for Contest 4 problems:

The idea and motivation behind these hints are that you should only open them up after spending a decent amount of trying to solve the problem yourself. Also, open the hints in sequential order.

Example: Try the problem for 40 mins, then open hint 1. Then using hint 1 only, try the problem for another 20-30 minutes. If still unable to make much progress only, then open hint 2 and so on.

The benefit of knowing a partial solution rather than the complete solution is that you can work out the later stages of the problem yourself, thus improving your problem-solving skills.

TLDR; use the hints cautiously, if you start relying on them too much, it can hamper with your learning process.

1.Stacks

Hint 1

Binary search on data structure (containing all the top disk radii) to find the smallest top disk radius which the current disc can be placed on top of.

Hint 2

In total, you’ll have three operations you want to handle: adding a new disc, binary searching for a disc and removing a disc.

Hint 3

Simulate the process, using the multiset. Be careful not to use a set because of duplicates being removed.

2.EURON

Hint 1

Consider the answer for some array to be the sum of the number of violations within the left half of the array, the number of violations within the right half of the array, and the number of violations that cross the halfway point in the array.

Hint 2

For every element in the left half of the array, there is some number of elements in the right half of the array smaller than it. Each such pair will create one violation.

HInt 3

For every element in the left half of the array, binary search for the latest position in the right half which is \le it, and add the number of positions to the answer crossing the midpoint.

HInt 4

Combine answers to the left half, right half, and across the midpoint cases to solve the problem.

3.QHOUSE

Hint 1

The bottom of the square is on the x-axis and the diagram is symmetrical across the y-axis.

Hint 2

Binary search for the x-coordinate of the bottom-right corner of the square.

Hint 3

Let the answer to your binary search be X.

Since it’s a square, the base is of side 2X.
The triangle base must also be on the line y=2X

Hint 4

Binary search for the rightmost point on the base of the triangle. Let the answer to this be R.
Similarly, binary search for the top point of the triangle. Let the answer to this be T.

Hint 5

You’ve got the dimensions, combine them to find the area:
2X * 2X + 2Y * (T - 2X) / 2

4.LOWSUM

Hint 1

Consider the alternative problem, “Given an integer X, find the number of pairs (i, j) such that A[i] + B[j] ≤ X.”

Hint 2

How can you use this modified problem to solve the original problem?

If you binary searched over X for the minimum X such that the answer was ≥ Q, this minimum X would be the answer to a query Q.

Hint 3

How can you solve this modified problem?

Sort both arrays A and array B.

Hint 4

For each integer Y in array A, all integers ≤ X - Y in array B will create a valid pair. You can binary search for the number of valid pairs in B. This will take O(NlogN) time.

Hint 5

Can we solve previous hint in O(N) time using two-pointers?

5.ASHIGIFT

Hint 1

Use a similar technique to the previous problem (LOWSUM).

Hint 2

Reach the end starting with some number of soldiers X.

Hint 3

Notice that if you can reach the end starting with X soldiers, you must be able to reach the end with X+1 soldiers as well.

Hint 4

Binary search for X!

6.STRSUB

Hint 1

Use that fact that is a substring is valid then all the substring formed are formed by this also valid.

Hint 2

For each i from 1 to N, we can find the j such that S[i, j] is valid and S[i, j+1] is not and denote this as ans[i].

Hint 3

For each query of type (l, r), we can find a value cnt for which ans[cnt] \le r.
Answer = sum of ans[i] from 1 to cnt - sum of ans[i] from 1 to (l-1) + (R-k)*(R+1) - (R*(R+1)/2 - L*(L-1)/2).

Hint 4

Use prefix sum to produce the sum of first terms of ans array. Find the cnt value using binary search.

7.ACM14KP1

Hint 1

Sort the points by x-coordinate and divide the points into two half and find the answer for each half.

Hint 2

The answer of the first half is ans_1 and the second half is ans_2 then answer of the combination of two half is max(ans_1, ans_2, answer produced by points such that one lie in the first half and the second in second half).

Hint 3

For each point p_i in the first part, we are only looking for the points p_j in the second half such that p_i.y - min(ans_1, ans_2) < p_j.y < p_i.y.

To know more about the above hint please refer to this:
https://cp-algorithms.com/geometry/nearest_points.html

Hint 4

Suppose ans_1 and ans_2 denote the minimum perimeter for the first and the second half and current_ans (without merge) is min(ans_1, ans_2).

Now, we need to check those that can form by merging these two half.

Hint 5

Tringle whose maximum length side is less then current_ans/2 can contribute to the final answer.

8.TRANSACT

Hint 1

Let the answer be denoted by X and let the maximum transaction between any pair of friends be denoted by Y. Note that as X increases, Y either remains the same or also increases. That is, f(X) = Y is a monotonically increasing function. Therefore, we can perform a binary search on the function.

Hint 2

Now, we have to write a function g(x) that returns true or false depending on whether it’s possible for all friends to have >= x coins.

Hint 3

In order to write g(x), a key observation is that in a sorted list of coins, friend i would only take coins from a friend with index > i. Therefore, for each prefix of friends, we can check if the remaining suffix can transfer the required coins to the prefix without breaking the condition. This function should be in O(N).

2 Likes

plz make a video on this contest because the problem are difficult and many people are not able to solve as you can see the submissions

1 Like

@rishup_nitdgp
How is this code getting AC ? Problem: EURON
As far as I know, it is O(n*n) , list.insert(index, value) is O(n)

from bisect import bisect_right
n = int(input())
k = []
ans = 0
for i in map(int,input().split()):
    x = bisect_right(k,i)
    ans += len(k)-x
    k.insert(x,i)
print(ans)

submitted link
Are the test-cases weak, or am I missing something ?

Problem: LOWSUM
How are codes like this getting passed ?
use the following code as test generator, and it gives different answer than given by official solution
MoreOver, Time limit seem to be too strict to allow the solution hinted by you to pass in languages like python submitted code

test = 1
k = 20000
q = 1
A = [i for i in range(1, k+1)]
B = [1 for i in range(1, k+1)]

print(test)
print(k, q)
print(*A)
print(*B)
print(600)
2 Likes

Here is my approcah for the LOWSUM problem exactly as mentioned in the hints.
Still it gives a TLE…
https://www.codechef.com/viewsolution/33145523

Any suggestions to optimise it…?

The multiset solution/hint for STACKS doesn’t work. It gives TLE. My hint: try with vector itself.
Edit: My bad, the multiset solution does work. Thanks @rishup_nitdgp !

2 Likes

Problem EURON
I have used pbds data structure for this problem, but it is giving WA.
Can anyone check my code for error.

void solve()
{
int n;
cin>>n;
int a[n];
rep(i,n)
{
cin>>a[i];
}
ordered_set o_set;
ll ans = 0;
rep(i,n)
{
o_set.insert(a[i]);
ans += (o_set.size()-1-o_set.order_of_key(a[i]));
}
cout<<ans<<’\n’;
}

1 Like

@srij_kh I added one more hint under the problem. This will help you.

@harshraj22 Thanks for pointing out. I think the test data is weak for both the problems. Also added a hint in LOWSUM.

3 Likes

@stardust_123 I went through your code and I find that you are using std:: upper on multiset which cause TLE. Actually the worst-case time complexity of std:: upper or similar is O(N) in case of ordered containers. II is better to use set:: upper which gives O(log N) worst-case complexity.

P.S: Upper Bound on set/multiset

2 Likes

@nomansid08 Please mention the submission link to your code.

@rishup_nitdgp Here is link of my code. It is working fine on sample test cases.
Online Compiler and IDE - GeeksforGeeks

@rishup_nitdgp I see. Thanks for the info ! I am gaining a lot of insight and knowledge from this DSA learning series ! I thank you and other volunteers for doing this !

1 Like

@rishup_nitdgp My code with Time complexity O(n*(n+logn)) is still accepted in 1sec.

As I replied to @harshraj22. Test cases are weak for the problem.

@rishup_nitdgp Why is my solution for EURON giving TLE, even when its time complexity is O(nlogn), pls check it here

Worst case time complexity for std::distance function is O(N). For more information, visit here.

then how is @harshraj22 answer in python, having the same complexity as mine, gets accepted even in 1.22 sec of runtime ??

I would like to say a few things:

  1. Rishup already pointed out, test cases are weak. Given the constraints, a O(n2) solution should not pass.
  2. The Python3 Solution is not mine.
  3. Python has different time multiplier (which might have given edge over cpp solution)
  4. Finally, the constants, they are ignored while calculating time complexity, but still play a major role. Read here

I know, it is strange for the same complexity to be accepted in one language and rejected in another, but maybe you should focus on improving the complexity from O(n2)

1 Like