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

×

TWTCLOSE - Editorial

2
1

PROBLEM LINKS:

Practice
Contest

DIFFICULTY

Cakewalk

PREREQUISITES

Basic string reading, using array

PROBLEM

The problem essentially is to maintain binary (open(1) or close(0)) state of N tweets and simulate K actions on them. The two types of actions are (a) CLICK X , which toggles the state of Xth tweet and (b) CLOSEALL , which sets the state of all the N tweets to close(0). After each of the K actions given, we need to find the total number tweets in open(1) state.

EXPLANATION

If you are beginner in programming contests, note that its common to assume that 108 basic arithmetic operations are performed in 1 second on modern computers. It may actually be faster than this (roughly 109 operations per second) on your computer. This is not always guaranteed as it may depend on several other factors. Some of them are handling heavy input/output, using modulo operator a lot, using long or double operands etc. So its always good to try a few practice problems in a site, for better estimation of actual run times.

For this problem, first lets look at a very naive approach, which is fast enough for the given constraints N ≤ 1000 and K ≤ 1000. We need to maintain the current state (isOpen) of N tweets, for which we can simply use an array of booleans (true/false) or integers (1/0). CLICK X toggles the state of Xth tweet, so if isOpen[X] == 1 then set isOpen[X] = 0, else if isOpen[X] == 0 then set isOpen[X] = 1. This can be done using a single statement isOpen[X] = 1 - isOpen[X] or using xor(^) operator, isOpen[X]^=1. CLOSEALL sets the state isOpen[X] = 0, for all the tweets X = 1 to N. To find the number of opened tweets at any time we can simply traverse the state array and count the number of opened tweets. This method requires O(N) memory, O(1) time for toggle, O(N) time for each CLOSEALL and O(N) time to find number of opened tweets. Overall for K operations it has worst case time of O(NK), which is fast enough for the given constraints.

SETTER'S SOLUTION

Can be found here

APPROACH

The problem setter used the above approach to solve the problem. For comparing two strings, the inbuilt function strcmp in string library is used.

TESTER'S SOLUTION

Can be found here

APPROACH

Note that we don't need to run a O(N) loop each time we want the count of opened tweets. The number of opened tweets changes by only either +1 or -1 with each CLICK X. So if the state of Xth tweet changes from close to open, we add 1, else if it changes from open to close, we subtract 1. So we can have this count in O(1) time per CLICK. Note that CLOSEALL still requires to reset all the states to 0 and is O(N). The overall solution if still O(NK) worst case time. Refer tester's solution for this approach.

EXERCISE

  1. Can you solve this problem in O(K) time using O(N) memory ? meaning, constant time for each CLICK and each CLOSEALL. Think about it and write your ideas in comments below.
This question is marked "community wiki".

asked 18 Jun '12, 00:21

flying_ant's gravatar image

3★flying_ant ♦♦
171313
accept rate: 0%

edited 25 Dec '12, 14:22

admin's gravatar image

0★admin ♦♦
17.4k347487515

I used memset for filling 0s. My solution was showing wrong answer though I have implemented it same as mentioned in the tutorial. http://www.codechef.com/viewsolution/1132512 Can't find what is the difference :(

(18 Jun '12, 13:04) vikram5353★
1

@vikram535 : Please check the 'memset' function in the library. The last parameter should be the number of bytes, and not number of elements in the array. If your array is int A[1001]; , you should use it as, memset(A,0,sizeof(A));

(18 Jun '12, 13:16) flying_ant ♦♦3★

Thank you so much for pointing out my mistake. I was not able to find it. Thanks again :)

(18 Jun '12, 16:21) vikram5353★

Here I present some way how to do all in O(K) time and O(N) memory.

Note however that complexity of dealing with each particular CLOSEALL query can be not O(1).

Additionally to approach described in the editorial you just need to save in some stack all tweets that were clicked. Once we have CLOSEALL query we pop each tweet from the stack and set isOpen[X] to 0, where X is the current tweet. Note that for some X we can have already isOpen[X] == 0 if it was clicked several times but we don't care about that. After this loop we will have empty stack and can continue to handle queries one by one.

This approach has complexity O(K) since we analyze each click at most twice: one time when we deal with actual query of this click and second time for the first CLOSEALL query after this click. This is a so-called amortized analyses - very useful logic that anyone should learn.

link

answered 18 Jun '12, 02:54

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.6k62119138
accept rate: 12%

And now let's discuss actual solution to the exercise where each query performed in O(1) time.

At first we numerate all queries starting from 1.

Next let's modify a bit our array isOpen[] and store the following information there: isOpen[X] = 0 if tweet X is closed, otherwise isOpen[X] is equal to the index of the last query where it was clicked. Further let's num be a number of currently open tweets (as in tester solution). Finally we also need additional variable last which is equal to the index of the last CLOSEALL query.

Initially last, num and isOpen[X] for all X are zeros.

Now suppose we have query CLICK X with index i. If isOpen[X] == 0 then we simply set isOpen[X] = i and add 1 to num. If isOpen[X] = j where j is not zero then situation is a bit trickier. At first we check whether j < last. If so then it means that in fact tweet X was closed during query CLOSEALL with index last after it was clicked last time and hence at first we should set isOpen[X] to 0 and then proceed as in the previous case. On the other hand if j > last then this tweet is actually opened and hence we should close it. That is, we need to set isOpen[X] = 0 and to decrease num by 1. Thus, we consider all possible cases for CLICK query. Note that we can combine first and second case in one case by condition isOpen[X] <= last. Indeed if isOpen[X] == 0 then it is always <= last.

If we have CLOSEALL query then we simply set last = i and num = 0.

It is easy to see after each query num is the correct number of opened tweets. Also now it is straightforward that each query is performed in O(1) time.

You can check this solution as a reference for this approach.

link

answered 18 Jun '12, 03:24

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.6k62119138
accept rate: 12%

link

answered 26 Jan '16, 20:49

code_hard123's gravatar image

5★code_hard123
7717
accept rate: 7%

Here's an alternate solution in O(Q) which is easier to understand:-

Q= no of queries

each time we have a click we add the element clicked to our click list, if an element is even no of times in our clicklist it means it is closed.

now when we have a close all query, we

1)decrease the opencount to 0

2) for all clicked elements, unclick them(we find the clicked elements by traversing the clicklist)

3) decrease the listCtr to 0

since each click is used only once while clicking and second while unclicking (during CLOSEALL) the net solution is O(no of clicks)= O(Q) link= solution

link

answered 25 Aug '12, 17:50

karan173's gravatar image

5★karan173
68591119
accept rate: 0%

import java.util.Scanner;
class twt
    {
    public static void main(String args[]) 
        {
    Scanner s = new Scanner(System.in);
    int n,k,i,j,c,p;
    String x ;
    String y;

    n = s.nextInt();
    k = s.nextInt();
    i = k;
    c = 0;
    int a[] = new int[1002];
    while(true)
        {

        i--;
        x = s.next();

        if(x.equals("CLOSEALL"))
            {
            c = 0;
            System.out.println(c);
            for(p=0;p<n;p++)
            a[p]=0;
            }
        else
            {
                y = s.next();
                j = Integer.parseInt(y);
                if(a[j]==0)
                {
                a[j]++;
                c++;
                System.out.println(c);
                }
                else
                {   
                a[j]--;
                c--;    
                System.out.println(c);
                }
            }   
        if(i==0)
        break;
        }
        }
    }

I M NOT ABLE TO FIND OUT WAT IS WRONG IN MY SOLUTION..PLZ HELP.

link

answered 05 Oct '12, 19:22

herman's gravatar image

3★herman
514512
accept rate: 0%

edited 05 Oct '12, 19:25

betlista's gravatar image

3★betlista ♦♦
16.8k49115225

here is counter example - http://ideone.com/A6o21

(05 Oct '12, 19:31) betlista ♦♦3★

hey thnx..my mistake i didn't observe dat..thnx a lot..

(05 Oct '12, 19:49) herman3★
#include<iostream>
#include<string>
#include<bitset>
using namespace std;
int main()
{
    int n,k;
    string str;
    cin>>n>>k;
    bitset<1000>status(0);
    getline(cin,str);
    while(k--)
    {
        getline(cin,str);
        if(str == "CLOSEALL")
            status.reset();

        else
            status.flip(str[6]-1-48);

        cout<<status.count()<<endl;
    }
    return 0;
}

What's wrong????

link

answered 27 Oct '12, 18:48

dosachef's gravatar image

3★dosachef
1
accept rate: 0%

edited 29 Oct '12, 17:21

betlista's gravatar image

3★betlista ♦♦
16.8k49115225

public class tweet {

    public static void main(String[] args) throws java.io.IOException {
        java.io.BufferedReader r = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
        String[] t = r.readLine().split(" ");

        int N = Integer.parseInt(t[0]);
        int K = Integer.parseInt(t[1]);

        boolean arr[] = new boolean[N];

        java.util.Arrays.fill(arr, false);
        int count = 0;
        for (int i = 0; i < K; i++) {
            String t1 = r.readLine();
            int n = t1.length();

            char a = t1.charAt(n - 1);

            if (a == 'L') {
                java.util.Arrays.fill(arr, false);
                count = 0;
                System.out.println(count);
            } else {
                int c = Integer.parseInt(t1.substring(n - 1, n));
                c = c - 1;
                if (arr[c] ) {
                    arr[c] = false;
                    count--;
                } else {
                    arr[c] = true;
                    count++;
                }
                System.out.println(count);
            }

        }
    }
}

Why am i getting NZEC in this solution ? Can anyone help me out ?

link

answered 20 Mar '14, 12:24

jigar2407's gravatar image

2★jigar2407
1
accept rate: 0%

edited 20 Mar '14, 14:54

betlista's gravatar image

3★betlista ♦♦
16.8k49115225

Your class cannot be public, that's the first problem at CodeChef. In addition

int c = Integer.parseInt(t1.substring(n - 1, n));
c = c - 1;

smells - http://ideone.com/J3TYWf

(20 Mar '14, 14:58) betlista ♦♦3★

Im getting NZEC with the following code.. although sample input works fine.. smone please help me out.. i'm new


import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String[] input = br.readLine().split("\s");

int N = Integer.parseInt(input[0]);

int k = Integer.parseInt(input[1]);

String str; int open=0;

int arr[]=new int[1000];

while(k!=0){

String[] input1 = br.readLine().split("\s");

if (input1[0].equals("CLOSEALL"))
{   open=0;
    System.out.println(open);

    for(int i=0;i<arr.length;i++)
        arr[i]=0;

        }

else if (arr[Integer.parseInt(input1[1])]==1)
{
    arr[Integer.parseInt(input1[1])]=0;
    open--;
    System.out.println(open);
}

else 
{ open++;
 arr[Integer.parseInt(input1[1])]=1;
    System.out.println(open);
}

k--;

}}}

link

answered 30 Aug '14, 00:58

asharma's gravatar image

2★asharma
1
accept rate: 0%

Please find the error in this solution :

My Solution :) Thanks in advance!

link

answered 02 Dec '14, 12:57

ajinkya1p3's gravatar image

5★ajinkya1p3
49238
accept rate: 26%

1

@ajinkya1p3
You forgot to print number of open tweets after input "CLOSEALL"
I have added print statement and here's the accepted version of your code
http://www.codechef.com/viewsolution/5479172

(02 Dec '14, 13:19) rishabhprsd72★

Thanks a lot!! :D

(02 Dec '14, 13:55) ajinkya1p35★

most welcome :)

(02 Dec '14, 14:14) rishabhprsd72★

include<string.h>

include<stdlib.h>

void main() { int t,n,p,q,i,j,k,x; char a[8]; scanf("%d %d",&t,&n); p=(int)calloc(t,sizeof(int)); q=(int)calloc(n,sizeof(int)); for(i=0;i<n;i++) { k=0; scanf("%s",a); if(strcmp(a,"CLICK")==0) { scanf("%d",&x); if(p[x-1]==1) p[x-1]=0; else p[x-1]=1; } else{ for(j=0;j<t;j++) p[j]=0;} for(j=0;j<t;j++) if(p[j]==1) k++; q[i]=k; } for(i=0;i<n;i++) printf("%d\n",q[i]); }

Is there any error in my code??? It works fine when i run it in my system but it is giving a runtime error when i submit it!! :/

link

answered 22 Jun '15, 23:31

shiva_35's gravatar image

0★shiva_35
11
accept rate: 0%

edited 22 Jun '15, 23:33

import java.io.*;
import java.util.ArrayList;
class TWTCLOSE{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out, true);
        String str[] = br.readLine().split(" ");
        ArrayList<Integer> al = new ArrayList(),ans = new ArrayList();
        int tweets = Integer.parseInt(str[0]);
        int clicks = Integer.parseInt(str[1]);
        while(clicks-->0){
            int twtnum;
            String twtstr[] = br.readLine().split(" ");
            if(!"CLOSEALL".equals(twtstr[0])){
                twtnum = Integer.parseInt(twtstr[1]);
                if(al.contains(twtnum))
                    al.remove(twtnum);
                else
                    al.add(twtnum);
            }
            else
                al.clear();
            ans.add(al.size());
        }
        for(int a:ans)
            pw.println(a);
    }
}
link

answered 03 Jul '15, 22:57

joshinjohnson's gravatar image

2★joshinjohnson
1
accept rate: 0%

https://www.codechef.com/viewsolution/8138468 Please have a look at the above link. I need some help. What I did? I simply calculated the length of the choice-"7 for CLICK X" otherwise "CLOSEALL". If len==7,then I just checked choice[6] what is it's numeric value.To calculate the numeric value I simply did this: choice[6]-'0'. But it showed wrong answer. I will be thankful to anyone who will take some patience and will help me for this. I will learn something which I should have known till now. Thank You. :)

link

answered 12 Sep '15, 17:15

sanal05_'s gravatar image

2★sanal05_
1
accept rate: 0%

i cant find out my mistake..can anyone help me..

#include<stdio.h>
#include<string.h>
#include<assert.h>

 void closeAll(int t[],int n)
{
int i;
 for(i=0;i<=n;i++)
{
    t[i]=0;
}
printf("%d\n",countOpen(t,n));
  }


   void toggle(int t[],int pos,int n)
  {
  if(t[pos]==0)
    t[pos]=1;
else
    t[pos]=0;

printf("%d\n",countOpen(t,n));
 }
 int countOpen(int t[],int n)
{
int i,count=0;
for(i=1;i<=n;i++)
{
    if(t[i]==1)
        count++;
}

return count;
   }
   int main()
   {
int t[1000]={0},n,k,x=0;
char operation[10];
scanf("%d",&n);
assert(n>0&& n<1001);
scanf("%d",&k);
assert(k>0&&k<1001);
while(k){
                        scanf("%s",operation);
                        if(strcmp("CLICK",operation)==0)
                        {
                            scanf("%d",&x);
                            //printf("val x=%d",x);
                            assert(x>0&&x<=n);
                            toggle(t,x,n);
                        }
                        else
                            closeAll(t,n);
                    k--;
                }





return 0;

}

link

answered 15 Oct '15, 17:06

sk03's gravatar image

0★sk03
11
accept rate: 0%

please help me out in this problem name "Closing the Tweets". I am getting wrong output error for my solution

link

answered 29 Oct '15, 15:07

sk03's gravatar image

0★sk03
11
accept rate: 0%

edited 29 Oct '15, 15:12

I have used a Set for inserting and deleting of elements which requires O(logN) for both operations and clear for closing all the tweets, which takes O(N) hence, overall it took O(NK) time. Even though my solution got AC in 0.0 seconds, still O(NK) is more for this problem right?

link

answered 19 Jan '16, 13:43

shyamsingh8's gravatar image

2★shyamsingh8
11
accept rate: 0%

On what test case this code fails?

include<stdio.h>

int main() { int n,k,i; scanf("%d %d",&n,&k); char s[10]; int a[n]; for(i=0;i<n;i++) a[i]="0;&lt;/p">

while(k--){ int flag=0,y=0,m,num=0; scanf (" %[^\n]%c",s); for(i=6;s[i]!='\0';i++) { m=s[i]-'0'; num=num10+m; }

if(num>=1 && num<=n) { if(a[num-1]==0) a[num-1]=1; else a[num-1]=0; } else{ y=0; flag=1; }

if(flag==0){ for(i=0;i<n;i++) {="" if(a[i]="=1)" y++;="" }="" }="" printf("%d\n",y);="" }="" }<="" p="">

link

answered 26 Jan '16, 19:15

dusht1408's gravatar image

1★dusht1408
111
accept rate: 0%

Why is this problem placed among medium difficulty problems? It looks trivial to me and should belong to the beginner problems.

link

answered 20 Apr '16, 17:28

tony_hager's gravatar image

5★tony_hager
412
accept rate: 0%

include<iostream>

include<string>

using namespace std;

int change(int* arr, char c,int n) {
int sum=0; arr[int(c)-49]=(arr[int(c)-49])?0:1; for(int i=0;i<n;i++) sum+=arr[i];

return sum;

}

int main() { int n,k; string s1,s2; char c; cin>>n>>k; int arr[n]; for(int j=0;j<n;j++) arr[j]=0;

for(int i=0;i<k;i++)
{
    cin>>s1;
    if(s1=="CLICK")
    {
        cin>>s2;
        c=s2.at(0);     
        cout<<change(arr,c,n)<<"\n";
    }
    if(s1=="CLOSEALL")
    {
        for(int j=0;j<n;j++)
            arr[j]=0;
        cout<<"0\n";
    }   
}

}

Why am I getting wrong answer?

link

answered 20 May '16, 15:24

shubham269's gravatar image

2★shubham269
1
accept rate: 0%

link

answered 23 Jun '16, 16:45

sanchit_aga's gravatar image

4★sanchit_aga
16
accept rate: 50%

can anyone please point out my mistake in this solution, it gives wrong ans on submission. https://www.codechef.com/viewsolution/11548341

link

answered 18 Sep '16, 00:10

timekeeper's gravatar image

2★timekeeper
1
accept rate: 0%

its showing wrong answer but works fine. can anyone please tell me whats wrong?

def checker(x):
    p = 0
    for i in range(len(x)):
        if x[i] == 1:
            p += 1
    print(p)


def end(x):
    return x[-1:]
n,k = input().split()
n,k = int(n),int(k)

tweetstatus = []
while n>0:
    tweetstatus.append(0)
    n -= 1
while k>0:
    s = str(input())

    if s == 'CLOSEALL':
        for i in range(len(tweetstatus)):
            tweetstatus[i] = 0

    else:
        z = int(end(s))

        if tweetstatus[z-1] == 0:
            tweetstatus[z-1] = 1
        else:
            tweetstatus[z-1] = 0

    checker(tweetstatus)



    k-= 1
link

answered 07 Apr, 14:59

ahuja_vaibhav's gravatar image

3★ahuja_vaibhav
3
accept rate: 0%

https://www.codechef.com/viewsolution/15965360

Can anyone tell me what's wrong in my solution? It's showing Runtime error.

link

answered 27 Oct, 02:37

amey_492's gravatar image

2★amey_492
1
accept rate: 0%

My solution is working correctly with the sample test case(after running on my system) But not working after submission. Please help me out! `#include<iostream>

include<string>

using namespace std; int main(){ int N,K; cin>>N>>K; string choice; int in,count = 0,arr[N]; for(int i = 0;i < N;i++) arr[i] = 0; while(K--){ cin>>choice; if(choice.compare("CLICK")==0){ cin>>in; if(arr[in-1]){ arr[in] = 0; count--; } else{ arr[in-1] = 1; count++; } } else if(choice.compare("CLOSEALL")==0){ for(int j = 0;j < K;j++) arr[j] = 0; count = 0; } cout<<count<<endl; } }`

link

answered 07 Dec, 03:46

vil_c's gravatar image

0★vil_c
1
accept rate: 0%

-1

Cant we use memset function for making all the values to 0( when we get CLOSEALL ) . i think this will take less than O(N) time.

link

answered 18 Jun '12, 01:35

tutulive's gravatar image

3★tutulive
01
accept rate: 0%

Memset would also take O(N) time to go through each element. But yes, the actual time might be lesser. For every CLOSEALL, we do not do anything if number of tweets is 0. That could help but doesn't lower worst case time.

(18 Jun '12, 01:58) orderof13★

You meant for example O(1/2 * N)? In fact that doesn't matter, it's asymptotically O(N).

(18 Jun '12, 14:12) betlista ♦♦3★
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:

×12,344
×1,155
×9
×1

question asked: 18 Jun '12, 00:21

question was seen: 8,206 times

last updated: 07 Dec, 03:46