Could someone explain “Rupsa and the game” in a clear way.I didn`t get the way they explained
In such cases, you can refer to problems editorial which has a quick explanation of the problem.
Its NOT a beginner problem, its a easy-medium (more inclined to medium in my opinion) .
Explanation of problem-
Lets say you have an array [1,2,3,4]. Then you can make sequence as-
Sequence starts from 1. Meaning, position of 1 is fixed.
Next element can be added to its left or right.
Score is product of the newly added element and its neighbour.
A possible sequence is formed like-
1
2 can be added to left or right. Lets add at right for this example
1 2
Score=2
Next element 3 can be added left to 1 or right to 2. Lets add next to 1.
3 1 2
Score=score+3=5
4 can be added next to 3 or 2. Lets add next to 2
3 1 2 4
Score=score+8=13
You have to find sum of all possible scores by all possible sequences modulo the given number
1 Like
can you explain me the 2nd testcase ?
This, is one of the most frequent Q I get a mail of @nissan7 haha. Here you go-
Ok, its like this-
In array [1,2,1] , we first fix 1.
Configuration-
1*
2 can be added either to its right or left. Lets add it to right here-
1* 2
Score=0 +2x1=2
Now 1 can be added to right of 2 or left of 1. Lets add 1 to right of 2-
1* 2 1
Score =2+ 1x2=4
But we have to find score of ALL configurations possible. So we try a new configuration now-
Lets try another configuration-
1*
We can add 2 on its right.
1* 2
Score= 4+2=6.
We dont want identical configuration, so in "1* 2", lets add 1 to left now-
1 1* 2
TOTAL/SUM-of-ALL-scores Score = 4+(1x1+2)=7 [score in "()" is total score of new configuration]
Had 2 been added on left of 1 initially-
2 1*
Score=9
Adding 1 to left of 2 will give configuration-
1 2 1*
(The 1* is the 1 which is rooted/marked. The configuration 1* 2 1 and 1 2 1* are not identical!! Meaning, all elements to left or root != all elements to right. You might get confused as they are mirror images, but problem setter wants us to think them as "not identical" )
Score now = 11
Shifting 1 to right of 1* will give another configuration-
2 1* 1
Score = 11 +(2x1+1x1)=14.
Hope this makes the Q clear.
Also, its NOT beginner level Q. Its a medium level Q, and needs you to be acquainted with soem mathematical algos like fast exponentiation etc. Its wrongly placed in beginners (you can see problem tags statign that its "easy-medium". Accuracy suggests that its more on medium side). I recommend you to skip it if you are just beginning.:)
2 Likes
it should be better if you share the question link
1 Like