A. A Simple Tree Problem How to solve this? My approach : Build rooted tree using two dimensional vector or say in form of linked list containing all the nodes for a parent.
operation — "o" use queue to negate all values. Query — "q" use queue to count all the nodes of subtree having values as non-zero.
My approach was leading to TLE. Can you please share your approach.
why my below solution is leading to WA?
Your code here...
while(scanf("%d%d%d",&N,&W,&K) == 3)
{
N=N+2;
float cost=0.0;
while(N > 0)
{
if(N>=K)
{
cost+=(W*(K-1));
N=N-K;
}
else
{
cost+=(W*N);
N=0;
}
}
float ans=cost/2.0;
printf("%.2f\n",ans);
}
@Rubanenko It seems you participated in the contest. Can you share your approach?
Hey, Kumar! It seems that you have problem with rounding. What if ans=0.05 before dividing by 2? It's better to add eps before dividing. Acually, I didn't like this problem because if it's statement.
Problem A:
What if you have not tree, but a simple array and have to evaluate the same kind of operations on segments? It can be solved using sqrt-decomposition. How to make segments from subtrees? — Just run dfs and add a vertex whenever you come into it for the first time. Then you will notice that for each vertex it's subtree lay on some consecutive segment of the list. You can store l[v] and r[v] for each vertex which means that it's subtree begins at l[v] and ends in r[v]. So whenever you have (o v) or (q v) query you just solve the first problem above for l[v]..r[v] segment. It is a standart trick so try to remember it :)
thanks Roman :)
Problem H: How can total value of lunch be in decimals? Since W is an integer value. The total cost of lunch should always be an integer value, right?
It is not guaranteed that W is an integer. That's why I don't like the problem :)
+1