Hi all,
I would like to invite you all to participate in Bytecode 2011, a
6-hour ACM ICPC style algorithm intensive online programming
competition. Bytecode is organized as a part of Pragyan 2011, the
International Level Techno-Managerial Festival of National Institute
of Technology,
In any column, we can place atmost 2 pebbles.
(a) Considering an isolated column, we can place 1 or 2 pebbles.
Solutions: {1},{2},{3},{4},{1,3},{1,4},{2,4}
(b) Have an array dp[n][5][5]. Let dp[i][j][k] store the maximum sum
that can be achieved starting from column 'i' to column 'n-1' (columns
@juver++: yeah! i get that! i thought the segment tree approach was
worth mentioning because more general problems can be solved using
this. eg:- Find the longest increasing subsequence such that the
difference between any 2 consecutive elements of the sequence you
choose is atmost 'k'. (Instead
Another variation can be finding the longest subsequence such that the
'absolute'
difference between any 2 consecutive elements of the sequence you
choose is atmost 'k'. Here, query range is [a[i]-k,a[i]+k].
On Dec 31, 1:01 pm, suhash suhash.venkat...@gmail.com wrote:
@juver++: yeah! i get
@bhupendra: I think you are talking about longest increasing subword.
But, i think the question is longest increasing subsequence!
definitions:
subword: a contiguous sequence of characters. eg: 'abb' is a subword
of 'cabber'
subsequence: a sequence of characters of the original string, with
order
For longest increasing subword, this O(n) solution is correct.
For longest increasing subsequence, it can be found in O(n*log n)
using binary search or segment tree.
Here is the segment tree approach.
Assume input is a[1n]
Let the property of the segment tree be: stores maximum value in a
Btw...this is O(n*log n) (query and update in the segment tree each
take O(log n))
On Dec 31, 11:26 am, suhash suhash.venkat...@gmail.com wrote:
For longest increasing subword, this O(n) solution is correct.
For longest increasing subsequence, it can be found in O(n*log n)
using binary search
Is'nt this just a knapsack problem!
On Dec 29, 3:45 pm, rajeev kumar rajeevprasa...@gmail.com wrote:
you are given a string.It may have repeated characters.each character has
it's own weight.find combination of characters whose sum value is equal to
given value.
ex: given string
for all (f!=h), atleast one of x[f], y[f] will be 0. (by not
performing any swaps, and just evaluating the value at the node)
hence dp[i][j]=min(x[1],x[2],x[3],.x[k])
On Dec 28, 10:32 am, suhash suhash.venkat...@gmail.com wrote:
This problem can be solved using dp in O(n), where 'n
[x][0] for each child x of i});
for leaf i:
dp[i][j] = (value[i]==j ? 0 : INFINITY)
On 2010-12-28 13:32, suhash wrote:
This problem can be solved using dp in O(n), where 'n' is the number
of nodes in the tree.
Definitions:
Let gate[i] be a boolean denoting whether
values.
The value of an OR gate likewise is given by the logical OR of its TWO
children's values.
On 2010-12-28 13:35, suhash wrote:
Your approach is for a binary tree, but the problem statement does not
say anything about it.
On Dec 28, 10:27 am, pacific pacificpacific4
And of course boundary cases(leaf nodes) are to be handled. For a leaf
node 'i', ok[i][j]=1(if j==v[i]), 0 otherwise!!!
On Dec 28, 11:04 pm, suhash suhash.venkat...@gmail.com wrote:
I think this can be solved using dp. Consider the subtree rooted at
node 'i'. Let ok[i][j] be a boolean (0 or 1
This problem can be solved using dp in O(n), where 'n' is the number
of nodes in the tree.
Definitions:
Let gate[i] be a boolean denoting whether the gate at node 'i' is
'AND' or 'OR'. (0-'AND' 1-'OR')
Let dp[i][j] store the minimum no. of swaps required to get a value of
'j' (0 or 1), for the
Your approach is for a binary tree, but the problem statement does not
say anything about it.
On Dec 28, 10:27 am, pacific pacific pacific4...@gmail.com wrote:
here is my approach :
Starting from the root node ,
if root node need to have a 1 ...
if root is an and gate :
flips =
14 matches
Mail list logo
