You are not logged in. Please login at www.codechef.com to post your questions!

×

# TRUEDARE - EDITORIAL

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

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:

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

This question is marked "community wiki".

asked 16 Nov '18, 17:48 4.0k31104
accept rate: 22% 19.8k350498541

 1 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. answered 22 Nov '18, 02:58 5★joffan 948●8 accept rate: 13%
 0 can you help to find error in my solution https://www.codechef.com/viewplaintext/21647086 answered 19 Nov '18, 15:52 1 accept rate: 0% remove break; statements (20 Nov '18, 00:42)
 0 "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 answered 20 Nov '18, 11:18 1 accept rate: 0% I saw your code, and your binary search is faulty. Read more on binary search. (21 Nov '18, 00:04)

# include<stdio.h>

int main() { int T; scanf("%d",&T); while(T--) { int tr,dr,ts,ds,i; int rt,rd,st,sd; 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&lt;dr;i++){" scanf("%d",&rd[i]);="" d1="rd[i];" }="" scanf("%d",&ts);="" for(i="0;i&lt;ts;i++){" scanf("%d",&st[i]);="" t2="st[i];" }="" scanf("%d",&ds);="" for(i="0;i&lt;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..

answered 20 Nov '18, 12:04 1
accept rate: 0%

Can you help me why this code is wrong?

# include<iostream>

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; }

answered 20 Nov '18, 19:07 1
accept rate: 0%

 0 Will this work if we use vectors? What is wrong with my solution. https://www.codechef.com/viewsolution/21647105 answered 21 Nov '18, 18:38 1 accept rate: 0%
 0 Can anyone help me to find error in my solution https://www.codechef.com/viewsolution/21678604 please? answered 23 Nov '18, 15:43 2★ghostron 3●1 accept rate: 0%

# include <stdlib.h>

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

    int tr, dr, ts, ds;
int ram_truth, ram_dare, shayam_truth, shayam_dare;
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;


}

answered 09 Dec '18, 14:02 1
accept rate: 0%

 0 someone please help me to find error in my solution https://www.codechef.com/viewsolution/23581875 answered 14 Mar, 07:12 1 accept rate: 0%
 0 Please point out problem in my solution: link: ERROR IN THIS SOLUTION EVEN WHEN IT IS RIGHT!!!!!!!!!!!!!! answered 17 Mar, 22:19 1●1 accept rate: 0%
 0 Hi, I was not able to get the slow solution to work. Can someone please help me with this. Thanks in advance. Please refer to my solution below. https://www.codechef.com/viewsolution/23620718 answered 21 Mar, 11:28 3●2 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,688
×1,409
×728
×163
×50
×11

question asked: 16 Nov '18, 17:48

question was seen: 1,441 times

last updated: 21 Mar, 12:34