S10E - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Alexey Zayakin
Tester: Hanlin Ren
Editorialist: Hanlin Ren

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM

We’re given the price of a phone over N days. Everyday we considers the price good if it’s strictly smaller than all the prices during previous five days. If on some day (before the first day) we didn’t record the price, we assume the price is infinite. Find the number of days with a good price.

EXPLANATION:

We simply iterate through the array, and for each index we check if it’s good. If it’s good, then we increase our answer. Pseudocode:

ans = 0
for i = 1 to N : 
  Check whether day i is good
  if day i is good then
    ans = ans + 1
print ans

Now we still need to check whether an index i is good. We can use a for-loop to iterate through its previous 5 indices.

Pseudocode:

for j = 1 to 5 : 
  if i-j > 1 then // if i-j>1, then the day i-j is valid, we need to check if its price is higher than the price in day i. 
    if P[i-j] < P[i] then day i is bad
return day i is good

Let’s put them together. We use a variable good to denote whether the i-th day is good. Initially we set good to be True, and when we find day i is bad, we set it to be False.

Pseudocode:

ans = 0
for i = 1 to N : 
  //Check whether day i is good
  good = True
  for j = 1 to 5 : 
    if i-j > 1 then // if i-j>1, then the day i-j is valid, we need to check if its price is higher than the price in day i. 
      if P[i-j] < P[i] then good = False
  if good then
    ans = ans + 1
print ans

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

using namespace std;

const int MX = 100;

int a[MX];

int main() {
	int T;
	ignore = scanf("%d", &T);
	while (T--) {
		int n;
		ignore = scanf("%d", &n);
		for (int i = 0; i < n; i++) ignore = scanf("%d", a + i);
		
		int ans = 0;
		for (int i = 0; i < n; i++) {
			bool ok = true;
			for (int j = max(i - 5, 0); j < i; j++) {
				ok = ok && a[i] < a[j];
			}
			
			if (ok) ans++;
		}
		
		printf("%d\n", ans);
	}
	
	return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;

int n, p[2000];
void doit() {
  int i, j, ans = 0;
  cin >> n;
  for (i = 1; i <= n; i++) cin >> p[i];
  for (i = 1; i <= n; i++) {
    for (j = max(1, i - 5); j < i; j++)
      if (p[i] >= p[j]) break;
    if (j == i) ans++;
  }
  cout << ans << endl;
}

int main() {int t; cin >> t; while (t--) doit(); return 0;}
2 Likes

I don’t feel that this is a cakewalk problem…

8 Likes

The problem can as well be solved by maintaining minimum value in a sliding window which for bigger N and k can reduce the time complexity to O(N) from O(N * k).

3 Likes

Can anyone tell me why this is wrong?

@coder7297 You missed the equal to sign at line 31.See this

1 Like

Thanks a lot! It was driving me crazy as I knew it was correct. But the editorial also contains the same mistake. :thinking:

1 Like

In problem statement it is given that price should be strictly less than all previous five days.
Hope you find where::stuck_out_tongue:

This task should be categorized as hard.

1 Like

Hi, im new here,(my first attempt at solution here)what happens if the user input is not within the constraint range?
i solved it without the constraint checking

also can someone explain how the subtasks work?

Can someone explain why this is wrong

https://www.codechef.com/viewsolution/27234098

https://www.codechef.com/viewsolution/27401844
gives nzec
but works perfectly in my ide
help needed

https://www.codechef.com/viewsolution/27402788
shows WA
custom input shows correct answer
help plz

I’ve just done a seat-of-the-pants implementation of this plus a testcase generator, and it looks like your solution fails on the following testcase:

1
9
690 570 470 385 712 710 391 584 579 

Edit:

Diagnostics:

Day: 1 out of 9 Good
Day: 2 out of 9 Good
Day: 3 out of 9 Good
Day: 4 out of 9 Good
Day: 5 out of 9 Not good - price is 385 on day 4 which is <= 712
Day: 6 out of 9 Not good - price is 385 on day 4 which is <= 710
Day: 7 out of 9 Not good - price is 385 on day 4 which is <= 391
Day: 8 out of 9 Not good - price is 391 on day 7 which is <= 584
Day: 9 out of 9 Not good - price is 391 on day 7 which is <= 579
4
3 Likes

thank u so much!:slightly_smiling_face:
i’ll check it again

1 Like

Yours seems to fail on:

1
8
399 411 491 621 745 602 482 537 

This is what I get (I’ve added some diagnostics to my code to explain what’s going on):

Day: 1 out of 8 Good
Day: 2 out of 8 Not good - price is 399 on day 1 which is <= 411
Day: 3 out of 8 Not good - price is 411 on day 2 which is <= 491
Day: 4 out of 8 Not good - price is 491 on day 3 which is <= 621
Day: 5 out of 8 Not good - price is 621 on day 4 which is <= 745
Day: 6 out of 8 Not good - price is 491 on day 3 which is <= 602
Day: 7 out of 8 Not good - price is 411 on day 2 which is <= 482
Day: 8 out of 8 Not good - price is 482 on day 7 which is <= 537
1
3 Likes

https://www.codechef.com/viewsolution/27403656
thank u! managed to give a correct solution
used your testcase to find an error in my code

1 Like

Take a look at the breakdown of my BACREP submission, here:

https://www.codechef.com/viewsolution/27345547

There are 16 “Tasks”. Each “Task” is a test input file which is provided to your program as input when your submission is evaluated. These Tasks are grouped into subtasks[1] - for example, the Tasks/ test input files 0, 1, 2 3 and 12 are all grouped into Subtask #1.

Let’s see what the constraints section says about Subtask #1:

Subtask #1 (20 points): 1 \le N,Q \le 5000

That means that the test input in each of the Tasks 0, 1, 2, 3 and 12 are guaranteed to have N \le 5000 and Q \le 5000 - this means that a naive O(N \times Q) solution will likely satisfy this Subtask (i.e. will successfully pass Tasks 0, 1, 2 ,3 and 12), and so get at least 20 of the possible 100 points.

[1] Yes, you read that right: a subtask is, rather confusingly, formed out of tasks.

3 Likes

Can’t understand why my program is giving me the wrong answer, I have tested the program with some of the custom inputs mentioned in the comments but its still not working https://www.codechef.com/viewsolution/27403916. If somebody can please hep me understand where I am getting it wrong

Consider the testcase:

1
9
468 463 701 508 670 638 463 394 402

My results (with Diagnostic info):

Day: 1 out of 9 Good
Day: 2 out of 9 Good
Day: 3 out of 9 Not good - price is 463 on day 2 which is <= 701
Day: 4 out of 9 Not good - price is 463 on day 2 which is <= 508
Day: 5 out of 9 Not good - price is 508 on day 4 which is <= 670
Day: 6 out of 9 Not good - price is 508 on day 4 which is <= 638
Day: 7 out of 9 Not good - price is 463 on day 2 which is <= 463
Day: 8 out of 9 Good
Day: 9 out of 9 Not good - price is 394 on day 8 which is <= 402
3
1 Like