Code Invicta Discussion

general
6

changed

7

approach for XORSEQ

8

@chaudhary_19 is it working for 1 0 2 0 ? answer should be NO.

9

yeah…it is showing NO

10

for XORSEQ approach ?
@chaudhary_19

11

There is a pattern in consecutive numbers xor.
It’s explained really well here.

And after that, you can use binary search(upper or lower bound) to find the starting and ending consecutive range of 0’s.
I used two set’s for it, one for positions of 1 and other for positions of houses which are still 0 and in neighbourhood of 1.

Solution

2 Likes
12

will this round effect my codechef rating?
I mean it was a rated round or not rated?

13

Not rated.

14

test case : 2 6 5 1
answer should be YES but your solution is getting NO.

15

not able to understand your solution

16

Can you explain the logic behind the conclusion of
For BCK2:
for every edge add 2 * weight_of_edge * min_of_number_of_nodes_on_both_side_of_edge

17

No, the round was unrated for everyone.

18

The approach is greedy.
In order to maximize my answer, for an edge i want all persons standing on nodes of one side of that edge to go towards other side of edge and vice versa. However only the minimum of both the sides of an edge can go passing that edge so taking minimum.

2 Likes
19

Great! I got it. Thanks for sharing.

1 Like
20

then how will you balance the sweetness in this testcase

21

divide n=2 and m=6 equally between them

22

gurudev ye bhi bta do …
https://www.codechef.com/viewsolution/30738993

23
24

literally I do not understand how you are talking about division between n = 2 and m = 6
can you please tell briefly. I don’t know why I am not getting it

26

I passed CHRIST02 with a sketchy sqrt-decomp that probably shouldn’t have passed.

First, optimize the naive O(NQ) with LCA (specifically binary lifting), making it so you only traverse exactly the vertices on the path. Then the solution looks roughly like:

while (u != lca) {
  if (l <= arr[u] && arr[u] <= r) ++ans;
  u = par[u];
}
# do the same for v

Then fix some power of 2, call it C. For each node with depth >= C, store its first C ancestors in a sorted array. For a query, if the node is at least C depth below the LCA, binary search on how many values are between L and R for the query in the sorted values. Then use the jump-pointer from the binary lifting to advance C ancestors of the current node. This becomes O(Q\log(N)(C + \frac{N}{C})) overall, which passed in 1.9s with C = 256.

Submission (code is quite ugly though)

Seems like other people used persistent segment trees or heavy-light decomposition.

I don’t know how to do CHRIST01.