Closing the tweets

Lets begin by solving one moderate level programming question on codechef. Please go through the question once.

Now if you have gone through the question, it basically maps to a problem that says there is an array sort of thing which is of type bool (initialized with false) and the user has the option to toggle it on/off and also there is one button to set all to false. Now with each attempt of user doing his input job you have to say how many bools are on/true in the array.

HINT: since the array is just 1000 size long even any algo of time complexity N is also fine.

Read the size of array vs time complexity relation here

Copying here just for your reference.

  • when N <= 10, then both O(N!) and O(2N) are ok (for 2N probably N <= 20 is ok too)
  • when N <= 100, then O(N3) is ok (I guess that N4 is also ok, but never tried)
  • when N <= 1.000, then N2 is also ok
  • when N <= 1.000.000, then O(N) is fine (I guess that 10.000.000 is fine too, but I never tried in contest)
  • finally when N = 1.000.000.000 then O(N) is NOT ok, you have to find something better…

SOLUTION:

Since it is clear that any algo with O(N2) complexity with work here.

What we will do is on every entry we will update the array which in case of click x will take o(1) time since x index can be reached in constant time, where as operation close all will take o(n) since we need to go to every index of array to update the element. After each entry we will also update our currentActive variable which stores the number of true bools of array.

So in worst case it will take  O(N2) time where each entry is closeall.

CODE:

// closethetweets.cpp : Defines the entry point for the console application.
//

#include
#include
using namespace std;

#include
#include
#define S(a,x) scanf("%"#a,&x) //#a expands to "a" we use this bcoz, arguments are not replaced within quoted strings
#define PS(a,x) printf("%"#a" ",x) //print with space
#define PN(a,x) printf("%"#a"\n",x) //print with newline
#define FOR(i,a,b) for( i=a;i<b;i++) #define FORD(i,a,b) for( i=a;i>=b;i--)
#define REP(i,n) FOR(i,0,n)
#define Max(a, b) ((a>b)?a:b)
#define Min(a, b) ((a>b)?b:a)
#define MAXSIZE 1010

int main()
{
int n, k, num;
int currentActive = 0;
bool arr[MAXSIZE] = { 0 };
S(d, n);
S(d, k);
char s[15];

while (k--)
{
S(s, s);
if (!strcmp(s, "CLICK"))
{
S(d, num);
num--; //0 based index
arr[num] = !arr[num]; //toggle
if (arr[num])
currentActive++;
else
currentActive--;
}
else
{
currentActive = 0;
memset(arr, 0, n + 1);
}
PN(d, currentActive);
}
return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *