SQRSUBMA June Lunchtime How to resolve TLE?

help
,
1

Approach: [Official] June Lunchtime 2020 - Post-contest discussion - Live stream session - YouTube

It is correct for 50 points but TLE for 100 points.

Can anybody tell why is it TLE?

Problem Link: CodeChef: Practical coding for everyone

My Submission: CodeChef: Practical coding for everyone

Ideone Link: ZtKgZ6 - Online C++0x Compiler & Debugging Tool - Ideone.com

Update: AC Submission 100 Points

2

Don’t use maps use a frequency array instead

3

Have You Tried unordered_map instead of map?

4

@zephxr Yes.
Unordered Map Submission
Still TLE

5

I think array can work instead of map and once try printf scanf instead cin cout.

6

@zephxr No help either from scanf printf

7

@cubefreak777 If X=10^6 then side length can be 10^5 as 10^5 is factor of X. And if all array elements are 10^6 . Then sum would be 10^6*10^5=10^11. This value won’t fit in freq array.

8

You only have to consider sums that are less than X , so you can have a frequency array of size 1e6

1 Like
9

Have you tried using array?

10

@zephxr @cubefreak777 Yes I tried
But why was any kind of map giving me TLE?
AC Submission 100 Points

1 Like
11

Map takes O(Logn) time in worst case
Unordered map takes O(1) time in best case and O(n) Time in Worst case
Array takes O(1) time in worst case.

1 Like