TLE on TEST-4 codeforces

#1

First pls give a hint

https://codeforces.com/contest/1520/problem/D

#2

hello @prerak_semwal

hint -> simplify the given expression i.e bring all i terms one side and all j terms other side and then try to make some observation

#3

check now pls
Also is this approach of rearranging quite recurring in these contests ?

#4

…

yeah u can enounter such type of expression in contests.

improve ur logic, its still O(n^2)

#5

@aman212yadav

check now pls … there will be comparatively less iterations w.r.t to whole program right (as now there are just 2 loops in whole program) ?

#6

its still O(N^2)

try to solve in O(N)

REFER THIS =>LINK

#7

@aman212yadav
What is map ?

Also can you please tell how you found this link for solutions ?

#8

…

pls read c++ stl

on codeforces they attach editorial of all the questions after the contest , so u can check solution from editorial section

#9

@aman212yadav
so map is only way to do in desired complexity

#10

we can do it with sorting as well.

#11

@aman212yadav
I saw on codeforces it displayed a tag of “hashing” problem…I haven’t reached on hashing in course so can I leave this problem (if this will be taught in future in course) ?

#12

yeah u can leave it for now. after studying hashing u will find this too easy

#13

@aman212yadav
small query -> is map related to hashing ?

#14

yeah …

#15

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.