WFWIN - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You are M minutes into a 300-minute contest, with a penalty of P and one problem left to solve.
Making a correct submission at time X gives you an additional penalty of X.
Making a wrong submission at time X gives you an additional penalty of 20, and you must wait one minute before making the next submission.

You want to both solve the problem before the 300-th minute, and also ensure your total penalty is \leq 1000.
What’s the maximum number of wrong submissions you can make?

EXPLANATION:

Suppose you fix k, the number of wrong submissions you make.
Then, since you have to wait a minute between each of them, it’s best to make them at minutes
M, M+1, M+2, \ldots, M+k-1
Following this, you can make a correct submission at time M+k to solve the problem.

The total increase to our penalty is 20\cdot k + (M+k): 20 for each wrong submission, and M+k for the final correct one.

There are two things to ensure here:

  1. The correct submission should be within the 300-th minute, that is, M+k \lt 300.
  2. The total penalty should be \leq 1000, that is, P+20\cdot k + (M+K) \leq 1000.

If both conditions are satisfied, it’s possible to make exactly k wrong submissions.
Otherwise, it isn’t.
Simply loop over all k starting from 0 to find the largest valid one.
You can stop at 300 since making more than 300 wrong submissions definitely won’t allow us to make the correct submission in time.

TIME COMPLEXITY:

\mathcal{O}(300) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    m, p = map(int, input().split())
    ans = 0
    for k in range(300):
        if m+k < 300 and p + 20*k + (m+k) <= 1000: ans = k
    print(ans)
2

My code failing in hidden testcase can someone highlight where this fails.

cook your dish here

for I in range (int(input())):
B=list(map(int, input().strip().split()))

 remaining_points=999-B[1]-B[0]     
 remaining_time=300-B[0]
 max_wrong=int(remaining_points//21)
 if max_wrong <=(remaining_time-1):
         print(max_wrong)
 else:
         print(remaining_time-1)
3

Best Solution O(1) time complexity

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

int main() {
	int t; cin>>t;
	
	while(t--){
	    int m, p; cin>>m>>p;
	    
	    int a = 300 - m;
	    
	    int b = (1000 - p - m)/21;
	    
	    if(a <= b) cout<< a-1;
	    else if ( (p + (21*b) + m) <= 1000){
	        cout<<b;
	    }
	    else cout<<b-1;
	    cout<<endl;
	    
	}

}
4

Explanation

so the problem boils down to two conditions

first is:
k < 300 - m

second is :

    p + (20 * k) + m + k <= 1000
    i.e. 21k <= 1000 - p - m
         k <= 1000 - p - m / 21

and k must satisfy both conditions.

so :-

    a = 300 - m;
    and b = 1000 - p - m / 21

now there will be two condition

1: a == b or a < b then since k < a nullifies  k <= b 
thus answer is a-1

2: a > b then answer could be b or b-1
      if p + (21*b) + m <= 1000 then b 
      else b-1