COLGLF2 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

None

PROBLEM

Given duration of shows of S seasons, each season having an intro song, Determine the time taken to watch all the episodes, while skipping intro song in each episode except once every season.

QUICK EXPLANATION

Simply subtract i-th intro song duration (E_i-1) times, as i-th song would be skipped E_i-1 times. Then take the total of all the episode times.

EXPLANATION

Since this is a simple problem, I’ll explain the solution from two viewpoints for interested readers. It’s perfectly okay to choose any veiwpoint as feels comfortable. Both are essentially same in idea.

Viewpoint 1

In this view point, we would compute the time spent on each episode. We’d subtract the duration of intro song from all except first episode for all seasons. So we have exact times spent on each episodes. We can take total of these and determine total duration.

Viewpoint 2

In this viewpoint, we’d focus on computing the time spent viewing the intro song and time spent viewing content in episodes. Since each intro song is watched exactly once, so sum of duration of each intro song determines the total time spent hearing intro songs.

Computing the time spent viewing content is subtracting the duration of intro song from each episode and adding the remaining episode time.

TIME COMPLEXITY

The time complexity is O(\sum{E_i}) per test case.
The space complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
#define pb push_back 
#define ll long long int
#define pii pair<int, int>
 
using namespace std;
  
FILE *fp;
ofstream outfile;
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        // char g = getc(fp);
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            // cout << x << " " << l << " " << r << endl;
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        // char g=getc(fp);
        assert(g != -1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
const int maxt = 5;
const int maxs = 1e5;
const int maxte = 1e5;
const int maxl = 1e5;
 
int main()
{ 
    int t = readIntLn(1, maxt);
    while(t--){
        int season = readIntLn(1, maxs);
        vector<int> q; q.clear();
        for(int i = 0; i < season; i++)q.pb(i == season - 1 ? readIntLn(1, maxl - 1) : readIntSp(1, maxl - 1));
        int te = 0;
        ll ans = 0;
        for(int i = 0; i < season; i++){
            int epi = readIntSp(1, maxte);
            te += epi;
            for(int j = 0; j < epi; j++){
                int len = j == epi - 1 ? readIntLn(q[i] + 1, maxl) : readIntSp(q[i] + 1, maxl);
                assert(len > q[i]);
                if(j == 0)ans += len; else ans += len - q[i];
            }
        }
        assert(te <= maxte);
        cout << ans << endl;
    }
    assert(getchar()==-1);
}  
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <limits>

#ifdef HOME
#define NOMINMAX   
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
	    char g = getchar();
	    if (g == '-') {
		    assert(fi == -1);
		    is_neg = true;
		    continue;
	    }
	    if ('0' <= g && g <= '9') {
		    x *= 10;
		    x += g - '0';
		    if (cnt == 0) {
			    fi = g - '0';
		    }
		    cnt++;
		    assert(fi != 0 || cnt == 1);
		    assert(fi != 0 || is_neg == false);

		    assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
	    }
	    else if (g == endd) {
		    assert(cnt > 0);
		    if (is_neg) {
			    x = -x;
		    }
		    assert(l <= x && x <= r);
		    return x;
	    }
	    else {
		    //assert(false);
	    }
    }
}

string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
	    char g = getchar();
	    assert(g != -1);
	    if (g == endd) {
		    break;
	    }
	    // 		if(g == '\r')
	    // 			continue;

	    cnt++;
	    ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
    return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
    return readString(l, r, ' ');
}

int main(int argc, char** argv)
{
#ifdef HOME
    if (IsDebuggerPresent())
    {
	    freopen("../COLGLF2_0.in", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 5);
    forn(tc, T)
    {
	    int S = readIntLn(1, 100'000);
	    int64_t res = 0;
	    vector<int> Q(S);
	    forn(i, S)
	    {
		    if (i + 1 == S)
			    Q[i] = readIntLn(1, 100'000);
		    else
			    Q[i] = readIntSp(1, 100'000);
		    res += Q[i];
	    }
	    forn(i, S)
	    {
		    int E = readIntSp(1, 100'000);
		    int EE;
		    forn(j, E)
		    {
			    if (j + 1 == E)
				    EE = readIntLn(2, 100'000);
			    else
				    EE = readIntSp(2, 100'000);
			    assert(EE > Q[i]);
			    res += EE - Q[i];
		    }
	    }
	    printf("%lld\n", res);
    }
    assert(getchar() == -1);
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class COLGLF2{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        long time = 0;
        int S = ni();
        long[] introSong = new long[S];
        for(int i = 0; i< S; i++){
            introSong[i] = nl();
            time += introSong[i];
        }
        for(int i = 0; i< S; i++){
            int E = ni();
            for(int j = 0; j< E; j++)time += nl()-introSong[i];
        }
        pn(time);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new COLGLF2().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

VIDEO EDITORIAL:

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

first, I added all the intro song time in Intro[s] array then I subtracted ith season intro song multiply by total episodes in ith season from the added result.
i.e sum-episodes[i]*intro[i]
Although all the test cases are passed but still not getting correct answer on submission so please help admins!!

#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t–)
{
int s;
cin>>s;
int intro[s];
for(int i=0; i<s; i++) cin>>intro[i];
//vector n_epi(s);
vector episodes[s];
for(int i=0; i<s; i++)
{
vector v;
int x;
cin>>x;
v.push_back(x);
for(int j=0; j<x; j++)
{
int y;
cin>>y;
v.push_back(y);
}
episodes[i]=v;
}
long long int sum=0;
for(int i=0; i<s; i++) sum+=intro[i];

    for(int i=0; i<s; i++)
    {
        for(int j=1; j<episodes[i].size(); j++) sum+=episodes[i][j];
        sum=sum-episodes[i][0]*intro[i];
    }
    cout<<sum<<endl;
}
return 0;

}

2 Likes

I missed because of integer overflow in sum.

2 Likes

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
FastScanner fs=new FastScanner();

    int t=fs.nextInt();
	for(int l=0;l<t;l++){
	    int s=fs.nextInt();
	    int[] q=fs.readArray(s);
	    long total=0;
	    
	    for(int i=0;i<s;i++){
	        int e=fs.nextInt();
	        
	        for(int j=0;j<e;j++){
	            total=total+fs.nextInt();
	        }
	        total=total-(e-1)*q[i];
	    }
	    System.out.println(total);
        
	}

}

}
class FastScanner
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
public String next()
{
while (!st.hasMoreTokens())
try {
st=new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();

	}
	public String nextLine() throws IOException
	{
	    return br.readLine();
	}
	int[] sort(int arr[])
	{
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i:arr)list.add(i);
		Collections.sort(list);
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=list.get(i);
		}
		return arr;
	}
	char[] charsort(char arr[])
        {
    	ArrayList<Character> list = new ArrayList<>();
    	for(char c:arr)list.add(c);
    	Collections.sort(list);
    	for(int i=0;i<list.size();i++)
    	{
    		arr[i]=list.get(i);
    	}
    	return arr;
        }
	long[] longsort(long arr[])
	{
		ArrayList<Long> list = new ArrayList<Long>();
		for(long i:arr)list.add(i);
		Collections.sort(list);
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=list.get(i);
		}
		return arr;
	}
	public int nextInt() 
	{
		return Integer.parseInt(next());
	}
	public int[] readArray(int n)
	{
		int[] arr=new int[n];
		for (int i=0; i<n; i++) arr[i]=nextInt();
		return arr;
	}	
	public long nextLong()
	{
		return Long.parseLong(next());
	}
	public long[] longreadArray(int n) 
	{
		long[] a=new long[n];
		for (int i=0; i<n; i++) a[i]=nextLong();
		return a;
	}

}
Can anyone tell me the problem with this solution? It is working fine with the test cases, but getting the wrong answer on submission.

Can anyone tell me the problem with this solution? It is working fine with the test cases, but getting the wrong answer on submission.

import java.util.*;

public class sample{
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int t=sc.nextInt();
while(t–>0){
int n=sc.nextInt();
int[] q=new int[n];
for(int i=0;i<n;i++){
q[i]=sc.nextInt();
}
int[] e=new int[n];
int[] l=new int[n];

		for(int i=0;i<n;i++){
			e[i]=sc.nextInt();
			l[i]=0;
			for(int j=0;j<e[i];j++){
				l[i]=l[i]+sc.nextInt();
			}
		}

		long ans=0;

		for(int i=0;i<n;i++){
			l[i]=l[i]-(e[i]-1)*q[i];
			ans=ans+l[i];
		}
		System.out.println(ans);
	}
}

}

what’s wrong with this code…all test case pass but still WA
#include
using namespace std;
#include<bits/stdc++.h>
int main() {
// your code goes here
int t;
std::cin >> t;
while(t–)
{
long long int sum=0;
int s; cin>>s;
int q[s];
for(int i=0;i<s;i++)
{
cin>>q[i];
}
for(int i=0;i<s;i++)
{
long long int z=0;
int n;
cin>>n;
int l[n];
for(int j=0;j<n;j++){
cin>>l[j];
z+=l[j];
}

        z=z-q[i]*(n-1);
        
        sum+=z;
    }
    
    std::cout << sum << std::endl;
}
return 0;

}

I got my solution accepted when i changed the Integer to Long. Someone please explain me why _/_

Working Solution simple

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int t;
	cin >> t;
	
	while(t--){
	   ll s,j=0,sum=0;
	   cin >> s;
	   ll q[s];
	   for(int i=0; i<s; i++)
	       cin >> q[i];
	   while(s--){
	       
	      ll totalEpisode;
	      cin >> totalEpisode;
	      ll epiDur[totalEpisode];
	      
	      for(int i=0; i<totalEpisode; i++)
	      {
	        cin >> epiDur[i];
	      }
	      sum += epiDur[0];
	      for(int i=1; i<totalEpisode; i++)
	      {
	          sum = sum + epiDur[i] - q[j];
	      }
	      j++;
	   } 
	   cout << sum << endl;
	   
	}
	return 0;
}
2 Likes

Can someone please tell what is wrong with my code? Changing sum to long long int is not working for me, sample test cases passed, but WA on submitting.

#include
using namespace std;

int main() {
int t;
cin>>t;
while(t–)
{
long long int sum=0;
int s;
cin>>s;
int song_duration[s];
for(int i=0;i<s;i++)
cin>>song_duration[i];
for(int i=0;i<s;i++)
{
int no_of_episodes;
cin>>no_of_episodes;
if(no_of_episodes>1)
sum -= ((no_of_episodes-1)*song_duration[i]);

       while(no_of_episodes--)
	       {
	            int x;
	            cin>>x;
	            sum+=x;
	       }
   }

    cout<<sum<<endl;
}
return 0;

}

Same… :sob: But in the constraints they said

Sum of all Ei Ei in a single testcase is at most 10^5
That’s why I didnt try long int. It struck me only when I saw this comment here!!

you tool sum as long long int but the problem is in episodes[i][0]intro [i] both can be upto 10^5 and 10^5-1
and this multiply can be aprox.10^10 which result as integer overflow and take only integer part hence you would get wrong answer
to improve you can change data types long long int initially
or you can do-
sum=sum-(long long int)episodes[i][0]
(long long int)intro[i];

can someone tell me why this code isn’t working
for i in range(int(input(""))):

s = int(input(""))

q = list(map(int,input("").strip().split()))[:s]

for i in range(s):

    e = list(map(int,input("").strip().split()))

    for j in q:

        if len(e)==2:

            print(e[1]*q[j])

        else:

            for i in e[2:]:

                a=(e[1]*q[j]) + (e[i]-q[j])

                print(a)

integer overflow will occur for large testcase that’s why use long long … it is prefferable to use long long while solving problems everytime as in most cases it will be helpful

Great buddy, Today It helped me.