BACREP - Editorial

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 sorting.

3 Likes

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;
}

1 Like

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;
    }

3 Likes

Thanks a lot again :smiley:

1 Like

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

2 Likes

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.

1 Like

Glad you fixed the WA :slight_smile:

This is causing a lot of slowdown, according to my experiments:

int sort_by(vector<ll> a,vector<ll> b){

You should take the vectors a and b by reference instead of by value.

Iā€™m not sure if thatā€™s going to be enough to get AC, though.

3 Likes

how to take by reference
I am new to c++ as I usually code in python

1 Like

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.

3 Likes

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

1 Like

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! :slight_smile:

3 Likes

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

1 Like

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.

3 Likes

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