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

×

TRUEDARE - EDITORIAL

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. :)

This question is marked "community wiki".

asked 16 Nov '18, 17:48

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 19 Nov '18, 12:59

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 22 Nov '18, 02:58

joffan's gravatar image

5★joffan
9488
accept rate: 13%

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

link

answered 19 Nov '18, 15:52

pankajjoshics's gravatar image

3★pankajjoshics
1
accept rate: 0%

remove break; statements

(20 Nov '18, 00:42) meetrockstar4★

"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

link

answered 20 Nov '18, 11:18

vaibhavraj10's gravatar image

2★vaibhavraj10
1
accept rate: 0%

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

(21 Nov '18, 00:04) taran_14076★

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&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..

link

answered 20 Nov '18, 12:04

sarthak2580's gravatar image

1★sarthak2580
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; }

link

answered 20 Nov '18, 19:07

ibrahimbhuyia's gravatar image

0★ibrahimbhuyia
1
accept rate: 0%

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

link

answered 21 Nov '18, 18:38

pulkitp2707's gravatar image

3★pulkitp2707
1
accept rate: 0%

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

link

answered 23 Nov '18, 15:43

ghostron's gravatar image

2★ghostron
31
accept rate: 0%

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

link

answered 09 Dec '18, 14:02

poreddyrohan's gravatar image

0★poreddyrohan
1
accept rate: 0%

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

link

answered 14 Mar, 07:12

syampawan's gravatar image

2★syampawan
1
accept rate: 0%

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

link

answered 17 Mar, 22:19

officialnitish's gravatar image

2★officialnitish
11
accept rate: 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

link

answered 21 Mar, 11:28

chenreddy's gravatar image

3★chenreddy
32
accept rate: 0%

edited 21 Mar, 12:34

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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