CIRADD - Editorial

PROBLEM LINK: Div-3 Contest

Author: Bhagya , Rishika
Tester: Rishika
Editorialist: Bhagya

DIFFICULTY:

EASY

PREREQUISITES:

Strings and Arrays

PROBLEM:

Circular Addition

QUICK EXPLANATION:

The first line of each test file contains a integer N.

The next line contains N space separated integers which represent the elements of the cyclic array.

The third line contains a integer Q representing the number of operations that will be applied to the array.

Finally, Q lines follow, each one containing an integer X .

EXPLANATION:

Krish is a very smart kid who recently started learning computer programming. His mentor gave him a cyclic array A having N numbers, and he has to perform Q operations on this array. In each operation the coach would provide him with a number X. After each operation, every element of the cyclic array would be replaced by the sum of itself and the element lying X positions behind it in the cyclic array. All these replacements take place simultaneously. For example, if the cyclic array was [a, b, c, d], then after the operation with X = 1, the new array would be [a+d, b+a, c+b, d+c]. He needs to output the sum of the elements of the final array modulus 10^9+7. He made a program for it but it’s not very efficient. You know he is a beginner, so he wants you to make an efficient program for this task because he doesn’t want to disappoint his coach.

Constraints

1 <= N <= 100000
1 <= Ai<= 10^9
0 <= Q <= 1000000
0 <= X < N

SOLUTIONS:

import java.util.*;
public class Main {
    public static void main(String args[]) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        int a[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
 
        int temp[] = new int[n];
        for(int i=0; i<n; i++)
            temp[i] = a[i];
 
        int q = sc.nextInt();
        while(q-- > 0)
        {
            int x = sc.nextInt();
            x = x % a.length;
 
            for(int i=0; i<n; i++)
            {
                int r = i - x;
                if(r < 0)
                    r = n + r;
 
                a[i] += temp[r];
            }
 
            for(int i=0; i<n; i++)
                temp[i] = a[i];
        }
 
        int sum = 0;
        for(int i=0; i<n; i++)
            sum += a[i];
 
        System.out.println(sum % ((int)Math.pow(10, 9) + 7));
    }
}

Is there a bug in CC? I see no people took part in this contest. If that’s true, than I feel very bad for the team that put the contest together. :frowning:

No it’s not a bug…

Actually we have organized this contest as an experiment for our Chapter community and there was also very much shortage in publicizing our contest…

That’s unfortunate. Hope to see you propose another contest and that one goes better! :slight_smile:

I’m wondering though, is there a way to upsolve this contest? I can’t submit problems.