Invitation for Encoding JAN'20

general
14

You could have also played some random tic tac toe on google setting the difficulty to impossible. I used this to arrive at the result.

2 Likes
15

thanks bro. That was my question :3:3

2 Likes
16

I am the author of this problem. Since @anon55659401 has already explained the intuition, I am just sharing the resource I followed while making the question.
https://mindyourdecisions.com/blog/2015/06/02/the-best-strategy-for-tic-tac-toe-game-theory-tuesdays/

3 Likes
17

Can u explain the approach…

18

For tic tac toe I just wrote a straightforward dp, since there are only like 3^9 states.

5 Likes
19

:dizzy_face:

1 Like
20

And I just did 3-times if-else for tic-tac-toe question :joy::joy::joy::joy:
I still don’t know why it has so few submissions, it has lesser submissions than the convex hull problem lol :rofl::rofl::rofl:

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