kkr.ashish
BAN USERwill not work the denomination loop has to come out to stop the reoccurance of patterns
- kkr.ashish January 05, 2014600-620 ? 1000-1030 ?
- kkr.ashish January 05, 2014summation over(n-1)(l-2)+(n-2)(l-3)+(n-3)(l-4)...(n-Z)(l-Z-1).... m times or till n-Z or l-Z-1 becomes negative
this has close form solution
summation (n-z)(l-z-1) = nl + z^2 +z - lz-nz-n
= nl + z^2 - (l+n-1)z -n
this summation can be calculated over 1-> Z
where Z = min(m,n,l-1)
keep a list of all the leave nodes and process all the nodes keeping their parent id as the weight..
then just update the list above the leaf nodes adding the weights up..
a basic solution: i am sure there will be an elegant one for this problem
Keep a disjoint time SET (can be done without sorting) and for every entry check if there is an overlapping element in SET and then take a UNION if its there(you will need to run a further overlaping check for the updated element in SET till it keeps updating) or create a new element. The SET can be maintained in a sorted order for better performance
Steps:
new duration: SET
(1,2) : S{(1,2)}
(2,3): S{(1,3)}
(4.5): S{(1,3),(4,5)}
(4,8): S{(1,3),(4,8)}
(3,5): S{(1,3),(3,8)} : S{(1,8)}
its not a single table restaurant i suppose
- kkr.ashish December 06, 2013only sum is asked no need to generate both the numbers
int min_sum(int a[],int size)
{
int sum=0;
sort(&a[0],&a[size]);
if(size%2==1)
sum+=a[0];
for(int i=size%2;i<size;i+=2)
sum = (sum*10+a[i]+a[i+1]);
return sum;
}
just generate the sum;
- kkr.ashish December 02, 2013the complexity should be O(n*N^2)
- kkr.ashish November 28, 2013you start with 1 at all the positions as in 0 steps all positions have 0 probability of dying..
then it uses the updation rule where val(x,y) = sum of all valids((val(x+-1,y+-1))
which is evaluating 1 step at a time
a preliminary solution can be to just sort the array and then push the last (n/2) elements at the even positions in any order and the condition will hold good
complexity O(nlogn)
or you can use selection algorithm for median finding and then push the number greater than median at even positions and others at odd position
complexiy O(n)
good handling of not generating similar combinations
How about just finding the total number of ways possible. Can we lower the complexity?
let the sting of length(n)
the for each char index x we check(assuming it is the center element in palindrone) that for i<x<j till there is a palindrone (max comparison n/2)
if index char[x] ==char[ x--] ||char[x]==char[x++] then we need to do another search assuming length of palin is even x is one of the mid elements another (n/2) comparison at max
now if we know [i,j] the limits of palindrone with x as the centre element
then number of palinds = summation of over all elements( if(j-i == even)? (j-i) /2 : (j-j+3)/2)
complexity = n*(3n/2) = n^2
As i read more on this , this is similar to Manacher's algorithm which can construct[i,j] in linear time and also inserts # to make sure all palin substring are odd length .. so
yes the complexity can be reduced to O(n)
O(n) solution
string preprocess(string s)
{
if(s.length()==0)
return "^$";
string z = "^";
for(int i=0;i<s.length();i++)
{ z +="#";
z = z.append(s.substr(i,1));}
z+="#$";
return z;
}
int find123(string s)
{
string z;
int *count = (int *)malloc(s.length() *sizeof(int)* 2 + 3*sizeof(int));
int L=0,R=0,C=0,sum=0;
z = preprocess(s);
for(int i=1;i<z.length();i++)
{
int index = 2*C-i;
count[i] = (R>i) ? min(R-i,count[index]):0;
while(i+1+count[i]<z.length()&&z[i+1+count[i]]==z[i-1-count[i]])
count[i]++;
if(i+count[i]>R)
{
C=i;
R = i+count[i];
}
if(count[i] > 1)
sum+=(count[i]+1)/2;
else
sum+=count[i];
}
return sum;
}
@- Miguel Oliveira why not we just run it only till half of the string and save the rest half of the problem
i dont have the complete code but if we are able to match the 1st half and 2nd half
we dont need to do the vice-versa operation
btw nice solution indeed
ok my bad .. i assumed the number should be atleast as beautiful.. seems the question seemed to be about equal to
for the given question it seems odd as there is not much choice for the players to make wise decisions the moves are very much forced nothing much they can do
as you can see in the test case you mentioned both return to 10011 state
say for 100110011
there will be total 2+ 3*2 moves possible the ordering can be different but it will be 8 moves
100110011 - > 10110011->1110011->1101011->1011011->111011->110111
->101111->111111
so i assume for 1001100110011
the output will be 2+ 2*3+2*5 = 18 moves
so this looks pretty much fixed if the beauty is preserved
100101 - > 2+ 1*2 = 4 moves so A loses
10101 - > 1+ 2*1 =3 B loses
1011101-> 1+ 4*1 = 5 B loses
please correct me if my understanding is wrong but all the moves are forced , players intelligence will not have any impact on the game for equally beautiful, but if its "atleast" then this problem is very interesting indeed
@keinnnn
@ kkr.ashish, " the number n-2^k has to be as beautiful as n", therefore, A cannot change "10011" to "1111"
1111 has 4 1's
and 10011 has 3 1's
so 1111 is more beautiful than 10011
so holds good
correct me if i am wrong
the question is correct your solution is wrong
- kkr.ashish November 06, 2013there is a minor bug the leftchild and rightchild being null doesnt make it BST because its own value needs to be checked so remove the 2nd if statement
- kkr.ashish November 06, 2013I have a similar solution to 1 explained
why not do this
a1,.........,an
go to n/2 index if (n/2) even then if a(n/2)+a(1) = a(n/4+1)+a(n/4-2)
if (n/2) odd
if a(n/2)+a(1) = 2*a(n/4)
then left half is correct and right has the missing number
this is using the average concept of the AP where sum of first and last term is 2wice the middle term or equal to sum of middle terms
did you test this?
the filling does not seem to be correct
for above code ::: Complexity = O(n^2 * (k))
k= average length of string i think they will be satisfied with this complexity..
i would rather go to each letter and look at its left and right till a palind is there and add them up so for abba
a = 1
b -> b, = 1
b -> b = 1
a - > a = 1
4 odd lenghts
for even length only consider if two adjacent characters are same
abba
bb - >bb, abba
2even length strings
num_palins = 6
this will be testing way less number of substrings as the total number of non-palin substring it will try is O(2n)
as it stops at first non-palin substring
in case all substrings are palin it will have same complexity as above solution
B can win the game by change it to "10011".
if B change it to 10011 A can then change it to 1111 where B actually loses
your moves are
1100->1010->1001->0101->0011
why will this not happen
1100->1010->1001->0111
why will one player play it badly its written it has to be as beautiful as previous
how about just using the vector<int>
- kkr.ashish September 14, 2013read about path and Trees
you will understand
the question is not that they have same path
the question is they are on same path
.. i cant explain more
thanks
example: [6,2,4,5] for the previous tree
BST
level 1: 6
level 2: 2 x
level 3: x 4 x x
level 4: x x 3 5 x x x x
i couldn't understand rest of your post
the above BST two path are visible because rest of element are x,
which are 6->2->4->5
and 6->2->4->3
i dont know if you are assuming group as a continguous subarray of the sorted numbers in BST which is not mentioned in question
The correctness is not proved.
I can show a counter-example
a BST
level 1: 6
level 2: 2 x
level 3: x 4 x x
level 4: x x 3 5 x x x x
the array: [2,3,4,5,6]
as pointed out you will give yes for this but the answer is no
a path is defined from root to a single leaf node
here 6 - 2- 4 - 5 is one path
and 6-2-4-3 is another path so the array is not on single path
see you are getting maximum and minimum and you will keep removing and again doing the min and max
so do sort once it will be less complex... only one min and max wont work
sort the vector array in increasing order
and then call
steps
1) sort the input array g
2) if root <= min then find if same path in root->right
3) if root >= max then find if same path in root->left
4) if min<root<max then not same path
bool ifsamepath(BinaryTree * root,vector<int> b,int length)
{
if(root == NULL && length!=0)
return false;
if(length==0)
return true;
if(root->data == b[0])
{
b.erase(b.begin());
return ifsamepath(root->right,b,length-1);
}
else if(root->data == b[length-1])
{
b.erase(b.end());
return ifsamepath(root->left,b,length-1);
}
else
{
if(root->data > b[length-1])
return ifsamepath(root->left,b,length);
else if(root->data < b[0])
return ifsamepath(root->right,b,length);
else
{
return false;
}
}
}
yes you are right but if you take any bit compactness .. golomb , exp golomb..you would use start and end symbol which inherently will give you space symbol
- kkr.ashish September 01, 2013lets see the possible number of combinations possible
8*8*8*8/2 = if positions mutually independent = 12 bits
otherwise
8*8*(8*8-1)/2 = 2016 combinations
total number of combinations possible with 3 bits=
0,1,00,01,10,11,000,001,010,011,100,101,110,111
2+2^2+2^3 = 14 = 2 (2^3-1)
total combination with 10 bits=
2(2^10-1)= 2046 combinations.. i will update the answer with a logical division or some1 can work it out
what if you consider 00010 and 10 as two different numbers then the whole argument you made will not hold good..
- kkr.ashish September 01, 2013what you are doing is correct but look at the complexity part.. you are accessing n-1 elements for every 1 element in output array
Complexity = O(n(n-1))= O(n2)
the question asked is to reduce the complexity
also your updated res[] is not correct the first elemeny should be bcde and abcde
n! mine one is on overall better as you try every combination possible,
you can also do it like bunch of n/2 1's and n/2 0's and do the permutations and try all the combinations
{1, 2, 30, 30, 30, 87}
- kkr.ashish August 29, 2013the DP i proposed is this
a = { 1,2,3,4,5,6,7,8}
find 4 elements in a which addupto 14
so you form a DP where you keep track of how many numbers you are using and whats the addition
in above case F(1) = 1(1) => () count of numbers uses
F(2) = 2(1)
F(3) = 1,2 (2) or 3(1)
F(4) = 1,3(2)
F(5) = 1,4(2) or 2,3(2)
so you throw if the count gets more than 4 and keep moving forward
this one is simple
you will need two array of same size
solution as example:
{a,b,c,d,e,f}
generate
{1,a,ab,abc,abcd,abcde}
and
{bcdef,cdef,def,ef,f,1}
now do a dot product of the above two array
you are done..
complexity O(3n)= O(n)
the above array are easily calculable as they can be generated the first from the front of array and other from back with 1 multiplcation for each element.
I think this can be solved like this:
1) Average of both (n/2) blocks is same=> total is same
2) Total of both blocks = 1/2 * total of n number
=> Add up all n numbers = T
=> find (n/2) numbers which add upto T/2
=> the leftover will also add up to T/2 (obvious)
we can use a DP for the above solution.. which is like the coin & sum problems
why are we even constructing the final tree. the question is to only calculate the minimum tree weight..
just sort the array and dot multiply with
a[]={1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,.....}-> n length
example 4,5,6
sorted 6,5,4
answer= 6*1+5*2+4*2 = 24
@above
for(int i=1;i<=10;i++) maxx=max(maxx, mx[i] - mn[i]);
this should be
for(int i=1;i<=9;i++) maxx=max(maxx, mx[i+1] - mn[i]);
and set maxx = -1e9
and it will work even if even in best case there is a lose in buying and selling as mentioned above
yes i agree @golodnov thanx for point it out
the difference shouldn't be elementwise it
should be
diff(i) = G(i+1) - H(i) because one will sell only aftr he has bought
int getdepth(int input_array[],int depth[],int k,int size)
{
if(depth[k]!=-1)
return depth[k];
if(input_array[k]==-1)
{
depth[k] = 1;
return 1;
}
if(depth[k]==-1)
{
depth[k] = 1+getDepth(input_array,depth,input_array[k],size);
return depth[k];
}
}
int calcDepth(int input_array[],int size)
{
int depth[size] = {-1};
int max=0;
for(int i=0;i<size;i++)
{
if(max<getdepth(input_array,depth,i,size))
max = getdepth((input_array,depth,i,size);
}
return max;
}
the above code should visit each edge of the tree only once O (n) while the worst case complexity for donnell code is around O(n^2)
- kkr.ashish July 23, 2013this is O(n +n +n) = O (n)..wat else you want
F(k) = min(F(k-1),input_array(k))
G(k) = max(G(k+1),input_array(k))
so both of these are n comparisons
so O(n)
and subtraction and max is also O(n)
so total O(n)
construct two arrays as follow:
F(i)= min(0<x<i)
G(i) = max(i<x<10)
where i [0,10)
so u will get for your test case
F = 5 1 1 1 1 1 1 1 1 1
G = 9 9 9 9 9 9 9 9 9 9
take the difference as follow
diff(i) = G(i+1) - H(i)
and take the max of it
answer = 9-1 = 8
your examples is simple
a good test case should be 8 9 11 12 7 6 4 9 1 4
F = 8 8 8 8 7 6 4 4 1 1
G = 12 12 12 12 9 9 9 9 4 4
diffence
: 4 4 4 1 2 3 5 0 3
so the answer is 5
which you can verify
@above
Hello,
please have a look in this way
i am at (x,y) i will check (x-1,y) ,(x,y-1),(x+1,y) ,(x,y+1) and not necessarily in this order.. but all of these will be checked
i sure have made (x,y) as new color but when i am at(x-1,y) i am still going to check (x,y),(x-1,y-1),(x-1,y+1),(x-2,y) because still the if statement needs to run so this is redundant check.. but if i know from [1,15] all are newcolor at given y-coordinate .. i dont need to check those coordinate again rather i will be looking at (y-1) coordinate points [1,15] and then left and right extend to get the new Line[L,R] at y-1 coordinate and same way the y + 1 direction.
use a linefill approach much faster..
start with (x,y) extend to [L,R] where L & R are left and right extreme on the monochromatic extensions.
then construct lines top and bottom of this line which are monochromatic extensions
this one will fill as lines and will beat the above algorithm in complexity as you are visiting every point 8 times
The solution is more like fibonaci series
where there is a choice
F(n) = F(n-1)+F(n-2)
or F(n) = F(n-1)
and the condition is atoi(string[n-1] string[n] ) < 27
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char * input ="1234";
int size = strlen(input);
int prev_val=0,curr_val=0,prev_prev_val=1;
for(int i=0;i<size;i++)
{
if(i!=0)
{
if((int)(input[i-1])<2+48 || ((int)(input[i-1])==2+48 &&
(int)(input[i])<7+48))
curr_val = prev_val + prev_prev_val;
else
curr_val = prev_val;
}
else
{
curr_val = 1;
prev_val = 1;
}
prev_prev_val = prev_val;
prev_val = curr_val;
}
cout<<curr_val<<endl;
return 0;
}
check for n=0,n=1
- kkr.ashish January 05, 2014for n=0;
answer is 0
for n=1
answer is 0