Invitation for Encoding JAN'20

general
21

Thanks @anon55659401 !

1 Like
22

Thanks a lot ! Nice Question :grin:

3 Likes
23

Was not expecting a dp solution tho :3:3:3:3

24

Thats what I was wondering too throughout the contest lol

1 Like
25

Its all pyschological .Bro.

Convex hull problem(s) got first 10 submissions very fast, so ppl didnt even bother checking the X-O game problem assuming it will be hard!

1 Like
26

i m getting continuously WA in ECJAN20G
ques. link CodeChef: Practical coding for everyone
my submission link : CodeChef: Practical coding for everyone .
pls help me. thanks in advance.

27

I got AC by implementing this kind of approach using strings…
I think maybe there are leading zeros in the input …

1 Like
28

Can someone check what is wrong in this code. It keeps on giving SIGSEGV. :frowning_face:
Problem Code

29

Can you explain the approach real quick?

30

The data vector for each node stores the updates and queries(also including the time 0 update for all the nodes). Then I’ve built a segment tree on query positions (i.e the time at which this query was done). Basically it stores all the updates of the current active branch from the root to the current node. On completing dfs for a particular node, I remove those updates from the segment tree.

31

The runtime error is because of this-
int val[n];
cin>>n>>q;

You are declaring the array before taking n as input.

2 Likes
32

And here is a testcase on which your code fails-

4 1
1 2
1 3
2 4
1 2 3 4
1 2

Your code outputs 9 (after removing the runtime error) whereas answer is 2 i guess

2 Likes
33

You can see my approach for this problem.
I have pre-processed the value for every node [of traversal from Xth node to Root node] using optimized LCA search (Binary Lifting), then I used sub tree queries along with lazy propagation of segment trees to get the desired result.

Simple code : here

1 Like
34

Thanks brother.

1 Like
35

what was the approach to solve ECJAN20H?

1 Like
36

Why did you use lca for the initializing nodes? cant we do it by a simple dfs? Is the lca helping in some way?

1 Like
37

I felt it to be a direct algorithm problem. Hence, used LCA.
No additional help, just a method, I used. :stuck_out_tongue:

1 Like
38

:sweat_smile::smiley: So we can use a simple dfs instead as well ?

1 Like
39

hey can you explain you code, i am not able to understand how you used the segment tree without making chains, I am only aware about HLD

40

There is no need of HLD here. Just think, if you update a node, it affects only the answer of nodes in the subtree of that node, so using the euler tricks & segment tree is sufficient for this problem!