acc1's blog

By acc1, 11 years ago, In English
Suppose there is a contest going on , and there is a question on interval trees.
Then "can" or rather "should" we ask on forums about the implementation of a interval tree. Because that makes no difference you see, an interval tree is so trivial, there is nothing new about it . (and to solve given problem you will atleast have to apply your mind , after implementing that tree)

And if there is a question on tree , then are we not allowed to discuss anything about tree?Like I want to know how many trees can be formed with n nodes.
Then if it helps a little bit , should we ask or not?

So, Actually I want to ask is that , should we ask a "trivial" question or not , given that it might help me solving that problem.


[for people who think that we should not ask, one question , with these competitions running like marathons , when will we get chance to ask others?]

-As I have seen Petr also discusses with his friends when he gets in trouble.
( although I am not sure whether he did it after the contest or during , but I think he did it during the contest.)

Read more »

 
 
 
 
  • Vote: I like it
  • -39
  • Vote: I do not like it

By acc1, 11 years ago, In English
Removed. Will get back to this in some time.
EDIT:It is standard problem known as Green Hackenbush.

Read more »

 
 
 
 
  • Vote: I like it
  • -47
  • Vote: I do not like it

By acc1, 11 years ago, In English
I don't know whether this question is correct or not, but I needed to ask.

I was thinking of game of nim with a restriction that number of stones that are removed from a heap is a fibonacci number(>= 1).

Then, is there a algorithm that can tell who is the winner?.
(Assume normal play of game.)

Read more »

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

By acc1, 11 years ago, In English
Can Every Impartial Game be converted to NIM game and How?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By acc1, 11 years ago, In English

http://codeforces.com/blog/entry/70

From Above I Downloaded some of Petr's video.

There is constant buzzing sound in the background (Is it his brainwaves :P ) , I want to Improve the Sound Quality, Is there a simple way .

Or If Anyone has better quality version of that?

And Are there other such tutoring videos available somewhere ?

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By acc1, 11 years ago, In English
Given Two arrays of n numbers. Find Whether they are disjoint or not.

Each Element lie in range [0,n^100] .

Space : O(n)

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

By acc1, 11 years ago, In English

The RUBIX Organizing Committee had planned to start publicizing their festival on the 29th of Jan,2011. Due to a last minute mishap they lost the document which contained the information as to which volunteer would visit which college on what day!
They turned to their God Rubixius to help them out with the planning for the next week. They provide him with the number of volunteers and the maximum number of people each volunteer can attract per day. Being God Rubixius knows how many people will be present at each college each day. Rubixius has cast a spell which puts you in his shoes for this job. You have to help the OC by telling them the maximum number of people they can get each day along with the actual plan.

Input

The first line contains an integer T with the number of test cases. Each test case will have 2 integers N and C representing the number of volunteers and the number of colleges respectively. The next line will have N integers with the maximum each volunteer can attract per day. Then C lines follow each having 6 integers representing the number of people present at that college from Monday to Saturday respectively.

Output

For each case print a line with the maximum number of people the volunteers can get.

Input:
1
3 3
1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1

Output:
18


I believe that it is NP-Hard . Can Anyone Throw some light !

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By acc1, 11 years ago, In English

I am in 90% sleep state...pardon me but the timing of hacker-cup was not suitable for India , it was at night 2:30 am :( .

Why is it so time taking...

<#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<numeric>
#include<vector>

#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()
#define sz(a) (a).size()
#define pb push_back

using namespace std;

typedef long long ll;
ll modu = 1000000007;
map <string,ll> mp;
int c=0;
ll f(string s)
{
//cout<<"here:"<<s<<" ";

if(sz(s) == 1) return 0;

if(mp[s]!=0) {return mp[s];}
ll sum = 0;
ll tmp,tmp2;
int arr[2];

arr[0] = 0;
arr[1] = 0;
for(int i = sz(s) ; i >= 2;i--)
{
for(int j = 0; j + i <=sz(s) ; j++)
{
c++;

tmp = 0;
tmp2 = 0;
// int p = 0;
for(int k = j ; k < j + i ; k++)
{
if(s[k] == 'a') { arr[0] = 1;}

if(s[k] == 'b') { arr[1] = 1;}
}
if(arr[0] == 1) {string new_s = s.substr(0,j)+'a'+s.substr(j+i); if(mp[new_s]!=0) tmp = 1 + mp[new_s] ; else tmp = 1 + f(new_s);
}
if(arr[1] == 1){string new_s = s.substr(0,j)+'b'+s.substr(j+i); if(mp[new_s]!=0) tmp = 1 + mp[new_s] ; else tmp2 = 1 + f(s.substr(0,j)+'b'+s.substr(j+i));
}
arr[0] = 0;
arr[1] = 0;

sum =(sum + tmp % modu + tmp2 % modu) % modu;
// mp[s]+=sum;
}
}
mp[s] = sum;
//cout<<mp[s];
return sum;
}


int main()
{
int T;
cin>>T;
string s="aa";
mp[s] = 1;
s="bb";
mp[s] = 1;
s="ab";
mp[s] = 2;
s="ba";
mp[s] = 2;
string S;
while(T--)
{
cin>>S;
c=0;
cout<<(f(S)+1)%1000000007;
cout<<endl;
// cout<<endl<<sz(mp)<<endl;
// cout<<c<<endl;
mp.clear();
}
return 0;
}

why is it exponential  :( :'(  :'(  .

Actually I know why is it exponential, I want to ask, can I change it to polynomial, without changing overall structure of my program.
>

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By acc1, 11 years ago, In English

I need to divide a set of players into two teams such that the team is balanced as far as possible .

Balancing is with respect to their skill values.

One of the team must have floor(n/2) players.

I initially thought it to be a NP-Complete problem , but I am now thinking that it a DP problem may be.

Can anyone tell how to solve this question.


Example:

Players: 5

Skill values:

Player 1 : 4

Player 2 : 1

Player 3 : 4

Player 4 : 56

Player 5 : 3


Optimal solution will have two teams of Total Skill values 11 and 57 respectively.


Now Constraints ( These contraints may also be helpful in solving the problems ):

Skill value of each player <= 570

Total Number of players  <  200

----------------------------------------------

Plz tell how to solve , any method You think of as the best  , plz write it .  



Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By acc1, 11 years ago, In English

Can anyone tell me where to find ..really nice article on it....


Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it