CAMPON Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi

PREREQUISITES:

NONE

PROBLEM:

In the next month you are gonna solve problems. The month consists of 31 days. You know for each day how many problems you will be solving at. You are given D pairs of the form (day_i,prob_i) denoting that you will solve prob_i problems at the {day_i}^{th} day of the month.

You are given then Q Queries of the form (dead_i,req_i). For each query you have a deadline dead_i which presents the last day that you could be solving problem at (the day itself is included). You need to tell if you will solve at least req_i problems up to that day (answer is Yes/No).

EXPLANATION:

This problem is a straightforward translation of the words written in the statement. Due to low constraints, we can manage to keep the pairs of problem-solving events (day_i,prob_i) in a vector/array.

Afterward, for each query, we can iterate through all the problem-solving events. If the day corresponding to some event is the deadline day (or someday before) we can assume that we are gonna solve the number of problems planned for that day. We sum up all the problems amounts of these days.

If our total sum is less than the required, we report that we cannot satisfy. Otherwise, we are fine.

Check the author’s code for the implementation of this approach. It runs in O(Q*D).

The tester’s approach is a bit faster (but not needed for such constraints). We maintain an array tot[1..31] recording how many problems we will solve each day.

Let’s run the following pseudo-code:

for(i from 1 to 31)
    tot[i] += tot[i-1]

Thus we will have in tot_i the total number of problems we will solve from the first day till the i_{th} day (included). Now our query (dead_i,prob_i) can be answered faster.

We can simply check if(req_i<= tot[dead_i]) and output the answer accordingly. Check the tester’s implementation for details. This implementation runs in O(Q)

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

1 Like
2

In tester’s solution why it is taken as MAX=31+3?

3

My solution is not being accepted. Can anyone please just give me a hint of what i am doing wrong?

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
{
    int D,Q,i,j,d[200],p[200],dead[200],req[200],sum=0,temp=0;
    cin>>D;
    for(i=1;i<=D;i++)
    {
        cin>>d[i]>>p[i];
    }
    cin>>Q;
    for(i=1;i<=Q;i++)
    {
        cin>>dead[i]>>req[i];
    }
    for (i=1;i<=Q;i++)
    {
        
        sum=0;
        
        for(j=1;j<=dead[i];j++)
        {
            
            for(temp=1;temp<=D;temp++)
            {
                
                if(d[temp]==j)
                {
                    sum+=p[temp];
                    
                    
                    
                }
            }
            if(j==dead[i])
            {
                
                if(sum>=req[i])
                {
                    cout<<"Go camp\n";
                    
                }
                else 
                {
                    cout<<"Go sleep\n";
                    
                }
            }
        }
    }

    
    
    
}
    return 0;
}
4

for now, I would like you to check your output; it has to be “Go Camp” instead of “Go camp”. both Camp and Sleep should be capitalized. I had the same bug only to discover after 7min of debugging that it was the content of my output stream.

5

Can somebody check my code and tell why its not getting accepted??
https://pastebin.com/GgY3AhwG

6

Please someone help me find error in my code.It is not being accepted.It shows Wrong Answer everytime.

import java.util.*;

import java.lang.*;

class Ex
{
public static void main(String args[])
{

  Scanner in=new Scanner(System.in);
    int a[]=new int[32];
    int d,s;
       for(int i=1;i<=31;i++)
            a[i]=0;
    
      int t=in.nextInt(); 
    for(int i=1;i<=t;i++)
    {
            d=in.nextInt();
         for(int j=1;j<=d;j++)
         {
            int x=in.nextInt();
            int y=in.nextInt();
             
               for(int m=x;m<=31;m++)
                      a[m]=a[m]+y;
             
         }
           s=in.nextInt();
        for(int k=1;k<=s;k++)
        {
           int dl=in.nextInt();
           int rq=in.nextInt();
            
              if(a[dl]>=rq)
                  System.out.println("Go Camp");
              else
                  System.out.println("Go Sleep");
        }
        
    }   
   
    
}

}

7

@ssshauryaa you are getting an error because in line 23 the loop should start from i=2, not i=1, because for i=1, you are getting data from i-1=0; ie. date=0 which is wrong.

i=1 would be the base case and eventually using this, data for other dates will be calculated.

Here is the corrected code:

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<utility>
using namespace std;

int main()
{
  int t,d,q,u,v;
  cin>>t;
  while(t--)
  {
    cin>>d;
    int a[32]={0};
    int b[32]={0};
    while(d--)
    {
      cin>>u>>v;
      a[u]=v;
    }
//Corrected
    for(int i=2;i<32;i++)
       a[i]=a[i]+a[i-1];
    cin>>q;
    while(q--)
    {
      cin>>u>>v;
      if(a[u]>=v)
          cout<<"Go Camp\n";
      else
          cout<<"Go Sleep\n";
    }
  }
  return 0;
}