ALT7STR Editorial


Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Ashish Kumar
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra




Strings, Binary Search


Chef likes to spend his summer vacation playing with string S. But he only likes the characters a and b to be part of his string.

Initially the string S is empty and Chef will build the string into his favourite alternate pattern in the following way.

  • Add a once to string S.

  • Add b twice to string S.

  • Add a thrice to string S.

  • and so on infinitely.

Now Chef will crop this infinitely large string to a length N and calculate the beauty of the string S.

The beauty of a string S is the sum of values of all substrings of S and the value of string S is the number of times the character changes from a to b or vice versa in the string.

Can you help Chef find the beauty of his string S of length N.
Since this calculated number can be large, output it modulo 1000000007.


We can see if we take the first two characters then there would be 1 change and number of substrings that includes the first two characters are N-1.
Now we move on to the 2nd change that occurs at 3_{rd} position for first 4 characters of the string and number of substrings that includes this change would be 3 \times (N-3).
Similarly the number of substrings that includes the 3_{rd} change would be 6 \times (N-6).
So basically our answer would be something like:

ans = 1 \times (N-1) + 3 \times (N-3)......k \times (N-k) \\ \; = N \times (1 + 3 + .....+ k) - (1^2 + 3^2....+k^2)

We can easily calculate k using binary search and pre-calculate the sum of the series to get out final answer.


O(log(N)), for each test case.


Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution