[Official] Contest 4 Hints

CodeChef-DSA-learners
, ,
4

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
5

@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
6

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…?

7

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
8

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
9

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

10

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

3 Likes
11

@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
12

@nomansid08 Please mention the submission link to your code.

13

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

14

@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
15

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

19

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

20

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

21

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

22

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

EURON(py)
EURON(py)799×623 29.1 KB

23

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
24

Your solution complexity is roughly O(N^2 + N*Log N), that’s why you are getting TLE.

P.S: Log N factor due to std::multiset.

25

Did you mean O(n * (n + logn)) ?

1 Like
26

Thanks.

1 Like