Invitation for Encoding JAN'20

In the first month of 2020, we are back with another Contest.
Presenting before you Encoding JAN’20

Our Problems setters and testers have worked a lot to make this happen. DO PARTICIPATE !

Description:
Encoding is a monthly contest hosted by CodeChef-NSEC. This is a coding contest based on algorithms and data structures, and aims to encourage participants to apply their knowledge towards problem solving.

How to participate?
You just need to have a CodeChef username to participate. No seperate registration is required. If you do not have a CodeChef ID create one at https://codechef.com

Contest Link : here
Be there on :
Date: 26th January, 2020
Time: 7PM - 10PM

5 Likes

Is it rated?

2 Likes

Nope.

Nice contest
Especially that tree problem was very nice, got to revise some of the concepts!

1 Like

Can someone give the intuition behind Tic-Tac Theory ?

2 Likes

@piyush_kumar99
If you are “X” and “X” starts first. So, whenever “X” is an odd number except “5” {1,3,7,9}…and also (y!=5) …sheldon wins.

In simple words, if you make “X” at any odd place except the center and the opponent replies with anything except the center, you win!

1 Like

How did you come to this outcome ? Did you generate all possible cases ? If yes, then can you tell me the idea for the generation code?

1 Like

Can we expect editorials?

1 Like

Yes. We will upload them as soon as we can.

@piyush_kumar99
Let me tell you, tic-tac-toe, is a solved game, it has been proved mathematically, that if you play first and make an odd move(except-5), and opponent replies with anything other than “5” , you win ?

How do I know? (You can just see it here:-https://www.wikihow.com/Win-at-Tic-Tac-Toe)

Answer:-I played many tic-tac-toe gaes with my friends in the past, and soon realized, there is a strategy, which if you follow, you will never loose this game

3 Likes

If you have some feedbacks:

1 Like

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

thanks bro. That was my question :3:3

2 Likes

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

Can u explain the approach…

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

5 Likes

1 Like

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