Adding kj to all the nodes in the subtree of the j-th node. using general update in N nodes in segment tree and to clear it will take O(n). Then why did he use segment tree for that? Or if he use any other technique to update values to all the nodes in the subtree. please someone answer this.
I think you are confused about prefix sum related techniques.
You can read more about prefix sums & fenwick trees, thatāll also help you in understanding how O(log n) operations can be used to maintain prefix sums using segment trees.
how did you come up with the intuition of creating the segment tree in form of time - depth[v] . Going through DFS and updating and removing is intuitive and makes sense. But this sudden time - depth thing is seems of the blue. Shed some light.
@r_64 I followed your approach. I am getting TLE and SIGSEGV error can you please tell me why this is happening . I hope you will help me this is my code -
https://www.codechef.com/viewsolution/27471192
One thing that immediately caused a crash (in debug mode) for me is that your compare
function is wrong: for a +
query q
it is not anti-reflexive as it should be i.e. compare(q,q)
is not false
. This will cause wrongness during sort
ing.
Thank you very much @ssjgz . Now this works - CodeChef: Practical coding for everyone
This one works -
bool compare(int a,int b)
{
if(queries[a].seq_val!=queries[b].seq_val)
return queries[a].seq_val<queries[b].seq_val;
return (queries[a].type==ā+ā)&&(queries[b].type==ā?ā);
}
Could you please clarify why the previous compare function does not works.
This was my previous compare function -
bool compare(int a,int b)
{
if(queries[a].seq_val<queries[b].seq_val) return true;
if(queries[b].seq_val<queries[a].seq_val) return false;
if(queries[a].type==ā?ā) return false;
else return true;
}
Comparing any +
query with itself with you original compare
function will return true
- try it!
The requirements of a comparator used with std::sort
are that it give a Strict Weak Ordering over its domain - in particularly, that it be irreflexive.
Here is the output from a simple testcase with gcc
ās -D_GLIBCXX_DEBUG
flag used at compilation time:
/usr/include/c++/7/bits/stl_algo.h:4866:
Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).
Objects involved in the operation:
instance "functor" @ 0x0x7fffc2868758 {
type = bool (*)(int, int);
}
iterator::value_type "ordered type" {
type = int;
}
Thanks a lot again
I used a different, not so efficient but i believe instructive strategy. Iāll provide a rough outline.
1) Static case(no updates)
This isnt so hard, you can have level-link pointers and store precomputed sum of bacterias from root to leaves. Now we can solve this easily by finding the level ancestor. We need to treat leaves differently(taking the level sum) as compared to non-leaves(taking level value) for queries, but nothing hard.
2) Dynamic. Take 1.
Letās store the initial values as in case 1. For updates, we can maintain an update box for each node. This update can be propagated downwards. The problem however is that the update time for each time unit can quickly climb to O(N), and so we must rebuild the tree many times. Not good enough.
3) Dynamic. Take 2.
Letās group the nodes into groups of k = \sqrt{NlogN} (this value of k can be found by writing down total time to do binary search on all group leader ancestors and minimizing it wrt k, see below). To do this, we do a bfs and mark each node as '1' until k nodes are marked. Now do bfs recursively on remaining elements in our bfs queue with value '2' (then '3' and so on). For each group designate a group leader. Whenever our propagation reaches a group leader, stop propagating and store the timestamp and update value in the group leader. For each node, we store pointers to all the group leaders on its root to node path. For queries, we can thus return (static case + propagated value + checked value from all ancestor group leaders). Note that each update propagates at most k times, and Nk just barely fits into time limit. There is one problem though: if our tree is very unbalanced, number of ancestor blows up. Not good.
3.1) Small improvement
Observe that as we move down the tree the depth/size ratio of our groups lessens. So going downward we can afford larger groups. We can recursively multiply our k by, say 1.2 for each incremented group ID.
4) Dynamic. Take 4.
I ended up using centroid decomposition, but only to designate group leaders and group sizes. Since the centroid decomposed tree is sufficiently balanced, we can prevent the problem of try 3. This means our group sizes are no longer exactly O(\sqrt{NlogN} ) but this is an improvement and I managed to use this to squeeze my time to under 2 seconds.
Final thoughts.
This was one hell of a question and I used a crazy contrived approach. Should have thought of the given solution which was much less complicated. Nevertheless, I learnt a lot solving this.
Good problem, and good editorial. Thanks
my solution is exact same as editorial but it is still failing and getting WA.I have tried using it on many different cases but still couldnāt find a case which fails my solution.i have coded in c++
EDIT: wa got corrected by converting only one occurence of int into long long int
but still tle issue
can anybody help as it is getting tle on last 50pt subtask .Should i use fenwick tree instead of seg tree?
https://www.codechef.com/viewsolution/27550087
@ssjgz @r_64.
Glad you fixed the WA
This is causing a lot of slowdown, according to my experiments:
int sort_by(vector<ll> a,vector<ll> b){
You should take the vector
s a
and b
by reference instead of by value.
Iām not sure if thatās going to be enough to get AC, though.
how to take by reference
I am new to c++ as I usually code in python
Oh, sorry - replace it with
int sort_by(vector<ll>& a,vector<ll>& b){
or (even better, stylistically):
int sort_by(const vector<ll>& a,const vector<ll>& b){
The time limit is still very tight, though.
although time for first subtask and second reduced drastically but still tle on 3rd one.
will try and use structs as they are generally faster than vectors.
once again thanks for helping
No problem - I suspect youāre very close to AC, and just need a few micro-optimisations here and there.
Remember that this has tons of I/O, so consider changing the endl
to \n
, and maybe using the scan_integer
type of stuff from my solution.
Good luck!
removing endl didnāt do the job
when I added the scan_integer and stuff it starts giving tle on the smallest of cases.(examples also)Am i missing something
You have to be very careful with scan_integer
as you canāt mix it with calls to cin >>
.
Ok, lets ignore scan_integer
for now: itās probably time to start using a more lightweight segment tree like I did in my solution (profiling shows that the vast majority of time is spent inside update
).
Definitely still replace endl
with \n
, though (itās at least as fast).
A quick gain can also be obtained by changing:
string s;
to
char s;
and
if(s[0]=='?'){
to
if(s=='?'){
but probably using a faster segment tree would bring the largest gain.
The following is my C++14 depth-first segment-tree based solution of the problem.
https://www.codechef.com/viewsolution/27226555
Only one segment-tree is used to keep the count of bacteria that appears along the present path from the root of the original tree, and each vertex in the original tree is augmented with a boolean flag that indicates whether the vertex is leaf or non-leaf. A sub-tree is processed only if at least one query about one of its vertices exists.
I tried using different templates of segment tree in c++ but they are giving other answer(wa one)
my code is at-KUTZ8w - Online C++0x Compiler & Debugging Tool - Ideone.com
what is wrong in my code pls help me ,i know i should have used segment tree,but since i didnāt know how to use segment tree i tried a different approach
(i used 2 arrays for storing changes in each second e array for even second and o for odd,leaf array to know if it is leaf or not )
my code