ALT7STR Editorial

editorial
, , , ,
1

PROBLEM LINK:

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

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

DIFFICULTY:

2318

PREREQUISITES:

Strings, Binary Search

PROBLEM:

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.

EXPLANATION:

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.

TIME COMPLEXITY:

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

SOLUTION:

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

2 Likes