PERFCONT - Editorial

editorial
, , ,
1

PROBLEM LINK

Practice

Contest

Author: Praveen Dhinwa

Tester: Alexey Zayakin

Editorialist: Jakub Safin

DIFFICULTY

CAKEWALK

PREREQUISITIES

none

PROBLEM

For a contest with P participants and N problems, you’re given the number of participants who solved each problem. Determine if exactly one problem was solved by at least \frac{P}{2} participants and exactly two problems were solved by at most \frac{P}{10} participants.

QUICK EXPLANATION

Count how many problems satisfy each inequality.

EXPLANATION

As a cakewalk problem, this is very easy: read N,P, compute \left\lfloor P/2 \right\rfloor and \left\lfloor P/10 \right\rfloor (the result of integer division is obtained when dividing an integer by another integer in most languages, where P/2 and P/10 gives what we need; Python 3 for instance needs P//2 and P//10), then read the numbers of participants solving each problem to count the number of cakewalk problems c and of hard problems h.

For a problem solved by x participants, check if x \ge \left\lfloor P/2 \right\rfloor or x \le \left\lfloor P/10 \right\rfloor. If x \ge \left\lfloor P/2 \right\rfloor is true, the problem has cakewalk difficulty and you should increase c by 1. If x \le \left\lfloor P/10 \right\rfloor is true, the problem has hard difficulty and you should increase h by 1.

Afterwards, you should check if c=1 and h=2.

Note that it’s possible for a problem to be both cakewalk and hard if P=1 and in that case, all problems will be cakewalk, so if we have exactly 2 hard problems, then we have at least 2 cakewalk problems, so it’s not a balanced contest (and contests with 1 participant are stupid anyway). For P \ge 2, it can’t happen since \left\lfloor P/2 \right\rfloor > P/2-1 and \left\lfloor P/10 \right\rfloor \le P/10, so we get \left\lfloor P/2 \right\rfloor > \left\lfloor P/10 \right\rfloor.

The time complexity is obviously O(N), since we’re doing just a linear number of comparisons and some arithmetic. The memory complexity is O(1) – we’re only storing a small constant number of variables.

AUTHOR’S AND TESTER’S SOLUTIONS

Setter’s solution: Will be uploaded soon.

Tester’s solution

Editorialist’s solution

2

Any idea why does this keep giving me TLE on the codechef ide? This works on minGW and ideone as well. I printed the first value and it comes up as garbage which is why the loop keeps running.

3

You definitely shouldn’t break the loop that reads the input.

4

include

main()
{
int n,num,solved[100],count=0,count1=0,parti,i,t;
printf(“test cases”);
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d %d",&num,&parti);
for(i=0;i<num;i++)
{
scanf("%d",&solved[i]);
}
for(i=0;i<num;i++)
{
if(solved[i]<parti/10)
{
count++;
}
else
{
count1++;
}
}
if(count1==2&&count==1)
{
printf(“yes”);
}
else
{
printf(“no”);
}

    }
}