CHEFPTNT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Omkar Prabhu
Tester: Hanlin Ren
Editorialist: Hanlin Ren

DIFFICULTY:

SIMPLE

PREREQUISITES:

None

PROBLEM:

Chef’s company should fill N patents in the first M months. The M months are numbered from 1 to M, and there are K workers in the company. Any worker can only fill one patent, and only works in odd months or even months. You are given a string s, if s[i]='E', then the i-th worker only works on even months(2,4,etc.), otherwise s[i]='O' and the i-th worker only works on odd months(1,3,etc.). At most x patents can be filled per month. Determine if it’s possible to fill N patents in M months.

QUICK EXPLANATION:

Suppose there are o 'O''s and e 'E''s in s, then output yes if and only if

\min(o,x\lfloor\frac{M+1}{2}\rfloor)+\min(e,x\lfloor\frac{M}{2}\rfloor)\ge N.

EXPLANATION:

First consider odd months. There are \lfloor\frac{M+1}{2}\rfloor odd months among the first M months, so we can fill at most x\lfloor\frac{M+1}{2}\rfloor patents. We can also count the number of 'O''s in s, say there are o 'O''s, then at most o patents can be filled. In total, we can fill at most \min(o,x\lfloor\frac{M+1}{2}\rfloor) patents in odd months.

Then we consider even months. There are \lfloor\frac{M}{2}\rfloor even months among the first M months, so we can fill at most x\lfloor\frac{M}{2}\rfloor patents. We count the number of 'E''s in s, say there are e 'E''s, then at most e patents can be filled. In total, we can fill at most \min(e,x\lfloor\frac{M}{2}\rfloor) patents in even months.

Therefore, in total we can fill

\min(o,x\lfloor\frac{M+1}{2}\rfloor)+\min(e,x\lfloor\frac{M}{2}\rfloor)

patents, and we compare this number to N.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

where is the fault in my solution where I find maximum possible in M day and compare with n [link text][1]

[1]: CodeChef: Practical coding for everyone pls help me because I didn’t solve next question due to the frustration of error !!!