FCF3P1 - Editorial

PROBLEM LINK:

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Niket Agarwal

Editorialist: Pritish Priyatosh Nayak

DIFFICULTY:

Simple

PREREQUISITES:

Prefix Sums , Observation.

PROBLEM:

Problem-statement

Subham has come to a circular race track to practice for hurdle race.
The race track is divided into N sections as you can see in the pic below:

In each of the sections, he has placed some hurdles. The i^{th} section has hurdles of height h_i.

He starts at section 1 and he runs in direction of increasing index (i.e from index i to index (i+1)) until he reaches N^{th} index, then he chages direction and starts running in direction of decreasing index until he reaches 1^{st} index and then changes direction again and so on.
(Each time he crosses the last or first index, he changes the direction he’s running in and heads back.)

Each time he runs past a section having hurdles with height h_i , he burns h_i calories. He has decided to run until he has crossed K sections.

Tell him how many calories he burns after running through K sections modulo 10^9+7.

EXPLANATION:

Easy version editorial link : FCF3P2 - Editorial

Unlike the easy version , here the path is a bit different. Subham first runs from postion 1 to N then comes back from N to 1 and so on.

So basically, his journey is like:

h_1,h_2,h_3,h_4,......,h_{n-1},h_n, h_n,h_{n-1},......,h_4,h_3,h_2,h_1,h_1,h_2,...,h_{n-1},h_{n},h_n,h_n,h_{n-1},......

Now observe that, this new problem is no different from the easy version. In the easier version, the whole array of N was repeating (aka. periodic) but here something else is periodic. Yes, the array + reverse of the array is periodic. So if we make a new array of size 2*N such that new_array= old_array + reverse(old_array) , then we can simply apply the technique used in the easy version of this problem.

See setter solution for more details on implementation.

Note: Tester solution uses a different approach that uses the fact that parity of floor(K/N) can tell us whether it will be return journey (N to 1) or forward journey (1 to N) in the last run where Subham doesn’t cover the whole array.

SOLUTIONS:

Setter's/Editorialist's Solution
            #include<bits/stdc++.h>
        using namespace std;
        int main()
        {
           ios_base::sync_with_stdio(false);cin.tie(NULL);
           #ifdef Zoro
           freopen("/home/pritish/Competitive/in", "r", stdin);
           freopen("/home/pritish/Competitive/out", "w", stdout);
           #endif  
         
           int t;
           cin>>t; 
         
           long long sumn=0;
           while(t--)
           {
              long long n,k;
              cin>>n>>k;
         
              long long a[2*n];
              for (int i = 0; i < n; ++i)
              {
                 cin>>a[i];
     
              }
              for(int i = n-1,j=n;i>=0;i--,j++)
              {
                 a[j]=a[i];
              }
         
         
              long long pref[2*n];
              const long long mod=1e9+7;
              pref[0]=a[0];
              for (int i = 1; i < 2*n; ++i)
              {
                 pref[i]=(pref[i-1]+a[i])%mod;
              }
         
              long long full_turns=k/(2*n),prefix=k%(2*n);
              full_turns%=mod;
              prefix%=mod;
              long long ans=(pref[2*n-1]*full_turns)%mod; 
              if(prefix)ans=(ans+pref[prefix-1])%mod;
              
              cout<<ans<<'\n';
           }
         
           cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
           return 0;
        }  
Tester's Solution
    import java.util.*;import java.io.*;import java.math.*;
    public class Main
    {
        public static void process()throws IOException
        {
            int n=ni();
            int k=ni();
            long[]A=nal(n);
            long pref[]=new long[n+1];
            for(int i=1;i<=n;i++)
                pref[i]=(pref[i-1]+A[i-1])%mod;
            long ans=(pref[n]*(k/n))%mod;
            if((k/n)%2==0)
                ans=(ans+pref[k%n])%mod;
            else ans=(ans+pref[n]-pref[n-(k%n)]+mod)%mod;
            pn(ans);
        }
        static long mod=(long)1e9+7l;
        static AnotherReader sc;
        static PrintWriter out;
        public static void main(String[]args)throws IOException
        {
            boolean oj = true;
            if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
            else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
            int t=1;
            t=ni();
            while(t-->0) {process();}
            out.flush();out.close();  
        }
     
        static void pn(Object o){out.println(o);}
        static void p(Object o){out.print(o);}
        static void pni(Object o){out.println(o);out.flush();}
        static int ni()throws IOException{return sc.nextInt();}
        static long nl()throws IOException{return sc.nextLong();}
        static double nd()throws IOException{return sc.nextDouble();}
        static String nln()throws IOException{return sc.nextLine();}
        static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
        static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
        static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
        static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
        static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
     
    /////////////////////////////////////////////////////////////////////////////////////////////////////////
     
        static class AnotherReader{BufferedReader br; StringTokenizer st;
        AnotherReader()throws FileNotFoundException{
        br=new BufferedReader(new InputStreamReader(System.in));}
        AnotherReader(int a)throws FileNotFoundException{
        br = new BufferedReader(new FileReader("input.txt"));}
        String next()throws IOException{
        while (st == null || !st.hasMoreElements()) {try{
        st = new StringTokenizer(br.readLine());}
        catch (IOException  e){ e.printStackTrace(); }}
        return st.nextToken(); } int nextInt() throws IOException{
        return Integer.parseInt(next());}
        long nextLong() throws IOException
        {return Long.parseLong(next());}
        double nextDouble()throws IOException { return Double.parseDouble(next()); }
        String nextLine() throws IOException{ String str = ""; try{
        str = br.readLine();} catch (IOException e){
        e.printStackTrace();} return str;}}
       
    /////////////////////////////////////////////////////////////////////////////////////////////////////////////
    }