CIRMERGE - Editorial

editorial
, , ,
64

Please provide an understanding of your approaches and please provide any resources to more extending your explanation, you could help some layman like me

65

You can see them in the 29th commit. :yum:

66

plzz explain me about sum(l,r) i dont know iam newbie here

67

Even I’ve used it, but if you use it at more than 6-places inside the loop, you’ll get TLE . I’ve used mod at only 4-places inside the loop and got AC :slight_smile:

69

It can’t be the sum of array because question requires something different
like for eg given in the problem statement-
10 10 1 (sum of array would be 21 which is not the ans)
but instead we have to iterate it n-1(n=3) times and calculate lowest possible penalty in each iteration by taking adjacent elements like this-
so , in first iteration min possible penalty is 10+1=11
now array is [10,11] here 11 is =merge(10,1)
in second iterations which is last in this case (N-1=3-1=2) penalty is 10+11=21

so, Total penalty is 32 not sum of array(21)

70

can you please give the array at each step

71

8 3 10 20 6
[11, 10, 20, 6]
[10, 20, 17]
[27, 20]
[47]
102

here’s the array by the algorithm i followed

72

I’ve used the same approach, can you spot the mistake in my code?

https://www.codechef.com/viewsolution/25335866

It passes 1st, 2nd and 4th TC.

@bhagirathi08

73

@anonymous1918
8 3 10 20 6
[14 3 10 20] -> 14
[ 14 13 20 ] -> 14 + 13
[27 20] -> 14 + 13 + 27
[47] -> 14 + 13 + 27 + 47 =>101

75

well I used modulo as well :stuck_out_tongue:

1 Like
76

simply because he declared it globally

77

You have a nice knowledge of algos. Good !

2 Likes
78

she herself said she was an icpc silver medalist bro.

1 Like
79

Thanks great. I will learn more and more when people like her be active on discuss.

2 Likes
80

Konsa waala silver? Regionals yaa world finals? Apne yahaa India mai kuch gold/silver nhi milta for regionals😅

81

Why don’t you go there (where loopfree is) XD?

2 Likes
82

you should learn balloon popping problem. This question is very similar to that problem. Here is the link : - LeetCode

83

why modulus is so time consuming

84

I used the greedy approach that you stated will pass the Subtask #2 (with distinct powers of 2).
Can you tell me why this greedy approach gave WA for other Subtasks? For which test case my greedy approach will give WA?

Thanks in advance.

85

I know it only because of experience btw you can refer here - https://stackoverflow.com/questions/27977834/why-is-modulus-operator-slow

1 Like