×

# CAMPON Editorial

Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi

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:

TESTER's solution

This question is marked "community wiki".

1181234
accept rate: 0%

19.8k350498541

 0 In tester's solution why it is taken as MAX=31+3? answered 25 Dec '18, 12:20 1 accept rate: 0%
 0 My solution is not being accepted. Can anyone please just give me a hint of what i am doing wrong? #include 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; }  answered 26 Dec '18, 21:04 1●1 accept rate: 0%
 0 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. answered 26 Dec '18, 22:54 0★c_r0ck 1 accept rate: 0%
 0 Can somebody check my code and tell why its not getting accepted?? https://pastebin.com/GgY3AhwG answered 27 Dec '18, 19:43 1 accept rate: 0%
 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"); } } }  } answered 29 Dec '18, 00:50 1 accept rate: 0%
 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 #include #include #include #include #include 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; }  answered 16 Feb, 10:43 0●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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