TRUEDARE - EDITORIAL

general
, , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Praveen Dhinwa
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Data-structures. Sets/Arrays.

PROBLEM:

Given two lists T1 and D1 denoting the truth tasks and dare tasks, Ram can perform and lists T2 and D2 denoting the tasks Ram is asked to perform, Inform whether Ram can perform all tasks or not.

Note that performing a task does not cause Ram’s ability to perform that task again.

QUICK EXPLANATION

  • Ram can perform all tasks if all distinct elements of T2 and D2 are also present in T1 and D1.
  • Just print in yes/no terms, whether the above condition is satisfied or not.

EXPLANATION

In this problem, we know the tasks Ram can perform, and the task he will be asked to perform. So, we need to check, if for all tasks Ram will be asked to perform, Can Ram perform all of them. If he can, we print yes, otherwise, we print no.

So, checking whether T1 a task, can be done using a boolean array or using set data structure. We do the same for D1.

Using set

We insert all elements of T1 into a set, and for every element in T2, we check whether this element is present in the set. If not, we know Ram cannot perform all tasks.

Using boolean array

We make a boolean array and mark all the elements in T1 as doable. Now, for every element in T2, we can check immediately if this task is doable.

Both of these solutions takes time O(N) where N is the size of the input. The constraints of this problem were low enough to let even the slow solution pass, which is, for every task in the to-do list, iterate over all elements of the can-do list and check if todo task is present in the list or not.

Time Complexity

Time complexity is O(N) where N is the size of the input.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

1 Like
2

can you help to find error in my solution
https://www.codechef.com/viewplaintext/21647086

3

remove break; statements

4

“for every task in the to-do list, iterate over all elements of the can-do list and check if todo task is present in the list or not”
=> Here, does this mean that we will be using a nested loop for searching purpose O(N^2)? I think we are basically, talking about linear search for each of the elements of to do list. Going by this approach, Inspite of the low constraints, my submission got TLE. I then again tried using binary search to lower the complexity to O(N*logN), but still got the TLE! Can anyone help me here!
My Solution

5

#include<stdio.h>
int main()
{
int T;
scanf("%d",&T);
while(T–)
{
int tr,dr,ts,ds,i;
int rt[100],rd[100],st[100],sd[100];
int t1,t2,d1,d2;
{
scanf("%d",&tr);
for(i=0;i<tr;i++){
scanf("%d",&rt[i]);
t1=rt[i];
}
scanf("%d",&dr);
for(i=0;i<dr;i++){
scanf("%d",&rd[i]);
d1=rd[i];
}
scanf("%d",&ts);
for(i=0;i<ts;i++){
scanf("%d",&st[i]);
t2=st[i];
}
scanf("%d",&ds);
for(i=0;i<ds;i++){
scanf("%d",&sd[i]);
d2=sd[i];
}
}
if(t1>=t2&&d1>=d2)
printf(“yes\n”);
else
printf(“no\n”);
}
return 0;
}

plz explain why code chef say wrong answer bt i got same output which given in question…

6

Can you help me why this code is wrong?
#include
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int p1,p2,q1,q2,i,j,c1=0;
cin>>p1;
int pa[p1];
for(i=0;i<p1;i++){
cin>>pa[i];
}
cin>>p2;
int pb[p2],c2=0;
for(i=0;i<p2;i++){
cin>>pb[i];
}
cin>>q1;
int qa[q1];
for(i=0;i<q1;i++){
cin>>qa[i];
}
cin>>q2;
int qb[q2];
for(i=0;i<q2;i++){
cin>>qb[i];
}
for(i=0;i<q1;i++){
for(j=0;j<p1;j++){
if(qa[i]==pa[j]){
c1++;
}
}
}
for(i=0;i<q2;i++){
for(j=0;j<p2;j++){
if(qb[i]==pb[j]){
c2++;
}
}
}
if(c1==q1 && c2==q2){
cout<<“yes”<<endl;
}
else{
cout<<“no”<<endl;
}
}
return 0;
}

7

I saw your code, and your binary search is faulty. Read more on binary search.

8

Will this work if we use vectors?
What is wrong with my solution.
https://www.codechef.com/viewsolution/21647105

9

Because the options for “truth” and “dare” activities are limited to a list of 100 each, another approach is simply to mark all activities that Ram is capable of into two (reset) boolean arrays, then check each of activities Shyam might ask of him to see if Ram could fail. This means that the action for each of Ram’s and Shyam’s options is a single array element access.

1 Like
10

Can anyone help me to find error in my solution https://www.codechef.com/viewsolution/21678604 please?

11

#include <stdio.h>
#include <stdlib.h>

int main(){
int t;
scanf("%d", &t);
fflush(stdin);
while(t–){

	int tr, dr, ts, ds;
	int ram_truth[100], ram_dare[100], shayam_truth[100], shayam_dare[100];
	scanf("%d", &tr);
	for(int i = 0; i < tr; i++) scanf("%d", &ram_truth[i]);
	fflush(stdin);
	
	scanf("%d", &dr);
	for(int i = 0; i < dr; i++) scanf("%d", &ram_dare[i]);
	fflush(stdin);
	
	scanf("%d", &ts);
	for(int i = 0; i < ts; i++) scanf("%d", &shayam_truth[i]);
	fflush(stdin);
	
	scanf("%d", &ds);
	for(int i = 0; i < ds; i++) scanf("%d", &shayam_dare[i]);

	
	int i = 0, j = 0;
	int flag1 = 0, flag2 = 0;
	
	while(i < ts){
		while(j < tr){
			if(shayam_truth[i] == ram_truth[j]){
				flag1 = 1;
				break;	
			}
			else{
			flag1 = 0;
			 j++;
		}
		}
		i++;
	}
	
	int k = 0, l = 0;
		while(k < ds){
		while(l < dr){
			if(shayam_dare[k] == ram_dare[l]){
				flag2 = 1;
				break;	
			}
			else{
			 flag2 = 0;
			 l++;
		}
		}
		k++;
	}
	
	if(flag1 == 1 && flag2 == 1) printf("yes\n");
	else printf("no\n");
	
	
	
	
}

return 0;

}

It showing me wrong answer but I got sample outputs correct…Please help me

12

someone please help me to find error in my solution https://www.codechef.com/viewsolution/23581875

13

Please point out problem in my solution:
link: ERROR IN THIS SOLUTION EVEN WHEN IT IS RIGHT!!!