You are not logged in. Please login at www.codechef.com to post your questions!

×

CAMPON Editorial

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

This question is marked "community wiki".

asked 23 Dec '18, 18:49

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 25 Dec '18, 04:19

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 25 Dec '18, 12:20

bhavin_18's gravatar image

2★bhavin_18
1
accept rate: 0%

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;
}
link

answered 26 Dec '18, 21:04

rahuldevkureel's gravatar image

2★rahuldevkureel
11
accept rate: 0%

edited 27 Dec '18, 20:15

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.

link

answered 26 Dec '18, 22:54

c_r0ck's gravatar image

0★c_r0ck
1
accept rate: 0%

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

link

answered 27 Dec '18, 19:43

ssshauryaa's gravatar image

2★ssshauryaa
1
accept rate: 0%

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");
        }

    }


}

}

link

answered 29 Dec '18, 00:50

alucard2711hs's gravatar image

2★alucard2711hs
1
accept rate: 0%

@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;
}
link

answered 16 Feb, 10:43

vandana_98's gravatar image

2★vandana_98
01
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×74
×8

question asked: 23 Dec '18, 18:49

question was seen: 731 times

last updated: 16 Feb, 10:43