SQRSUBMA - Editorial

editorial
, , , , ,
49

for the given example

that sum would be calculated as ((2 + 3 + 5) + (2 + 3 + 5)) * 3 = 60.

my submission.

50

You are using a map. Use a frequency array. The TL was strict to weed out the map solutions

1 Like
51

Glad to help you :slight_smile:

53

Try using unordered mapā€¦they might give AC

54

I tried that in the contest, using custom hash function. It didnā€™t work.

55

Did you try inserting only sums that are less than x? That significantly reduces the map size, and hence reduces collision probability.

1 Like
56

Yeah, did not try that. It might have worked. The next thought actually that came to me was of array so went with that as it was surely decreasing the complexity.

1 Like
57

Haha, yes. Even I jumped to an array after I got TLE. Anyways, I just wanted to know if doing what I suggested could avoid TLE.

Yesterday in codeforces Div 3, I used unordered_map which gave TLE. I switched to a regular map and it passed in 200 ms. So is it always good to just use map for everything?

58

Did you use unordered map with custom hash??? and also which question ??

59

Problem D. And no custom Hash.
The problem actually does not require a map, or a frequency table. One could just store the reminders, sort it, and count the occurrences as we pass. However, I first used a frequency array (yep, did not see the constraint for k), and I got MLE. So the next instinct was to use an unordered_map, which gave TLE :slightly_smiling_face:.

60

My advice would be to always use custom hash with unordered maps. Even if your solution passes pretests, in uphacking phase someone can hack your solution. The problem D can actually be done in O(1) extra space so you donā€™t need anything.

1 Like
61

Yes :P. I should add it to my snippets. Thanks!

62

I used map and it passed in Problem D (Div.3)!

63

Yess! Thatā€™s what I finally did, but two penalties for using array (MLE) and unordered_map (TLE).

1 Like
64

Ohā€¦!

1 Like
65

Can anyone please help me find error in my code :slight_smile:
https://www.codechef.com/viewsolution/34894482
@ganesh_6 , @udayan14

66

You are using a map. It will give TLE with map . Use frequency arrays. Look at my solution above for reference.

1 Like
67

your optimisation is similar to setterā€™s code can you please give quick explanation

68

Use prefix sum to quickly calculate sums in sliding windows. Use a frequency array and set it to zero initially. For each possible value of square side, first fill the frequrncy array, then instead of iterating over the frequency array to count, we iterate over the array A( See the addition to output variable in the second for loop, thereā€™s no multiplication in there). Finally, we only set those elements to 0 in the frequency array which are modified. We donā€™t each element to 0 (as most elements are already 0). Doing these optimizations will help you get AC. Ask if you need any more clarification.

1 Like
69

map in c++ sort the elements according to keys in ascending order. This will cost log(n) in the worst case. Try using an array for storing the frequencies of elements. Refer editorial. You will get a better insights. Your logic is right. The only thing is that use freq array or unordered_map

1 Like