Anachor's blog

By Anachor, 5 years ago, In English

Recently I came across the following problem in a contest. We tried the problem for a long time, but could not come up with a correct solution.

Alice and bob are playing a game across $$$ n \leq 10000 $$$, 3×3 Tic-tac-toe boards with both players marking the board with X. Each board already has some X's on it. One player can choose an arbitrary board and put an X on any of the empty cells. Alice always makes the first move. You can not make any further moves on a board after it has three consecutive X's (column, row or diagonal). A game ends when all the boards contain three consecutive X's. The player that made the last move loses the game.

Given a configuration of the game, you have to find out the winner. It is given that none of initial boards contain three consecutive X's.

Sample Input:

5
1
XX.
..X
..X
1
..X
X..
X.X
1
..X
.X.
.X.
1
..X
X..
XX.
1
..X
X..
..X

Sample Output:

Game #1: Alice
Game #2: Alice
Game #3: Bob
Game #4: Bob
Game #5: Bob

Full text and comments »

  • Vote: I like it
  • +66
  • Vote: I do not like it

By Anachor, history, 6 years ago, In English

Greetings Codeforces community! We welcome programmers all over the world to participate in CodeChef’s May Cook-Off sponsored by ShareChat. The contest will feature brand new and exciting problems for you to sharpen your skills. Problems statements will also be available in multiple languages. Participation could also bring you closer to work opportunities at ShareChat — India’s fastest growing social network. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Visit the contest page for more details. I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

  • Setters: solaimanope (Mohammad Solaiman), Anachor (Pritom Kundu), Erfan.aa (Erfan Alimohammadi)

  • Admin: kingofnumbers (Hasan Jaddouh)

  • Tester and Editorialist: teja349 (Teja Vardhan Reddy)

  • Statement Verifier: Xellos (Jakub Safin)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: Team VNOI

  • Russian Translator: Mediocrity (Fedor Korobeinikov)

  • Bengali Translator: solaimanope (Mohammad Solaiman)

  • Hindi Translator: Akash Shrivastava

Contest Details:

  • Start Date & Time: 19th May 2019 (2130 hrs) to 20th May 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
  • Contest link: https://www.codechef.com/COOK106
  • Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
  • Prizes: Top 10 performers in Global and top 10 performers in Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344 (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck!

Hope to see you participating!!

Happy Programming!!

Full text and comments »

  • Vote: I like it
  • +50
  • Vote: I do not like it

By Anachor, history, 6 years ago, In English

Suppose you have a set of lattice points each of whose coordinates lie in the interval [0, N]. I've heard that the number of points on the convex hull is O(N2 / 3). However, I cannot seem to be able to prove this. How can this be proven?

Also, how to generate testcases such that the convex hull contains as many points as possible?

Full text and comments »

  • Vote: I like it
  • +73
  • Vote: I do not like it