I was unable to solve the problem GRID GAME ( GRID GAME ) during the recently conducted ICPC Preparatory Series by team Enigma . The reason being i couldn't write the correct code to check whether the xor of the series x, x+2, x+4, ..., x+2*m-2 is 0 or not . But, after the contest i saw several different approaches to the problem . Some of them involved just 5-10 lines of code whereas some involved 20-30 lines of code . I'm very interested in knowing your approach . Thanks in advance for sharing :)
Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3741 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3443 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 158 |
| 5 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | djm03178 | 155 |
| 9 | TheScrasse | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.12.2024 05:41:46 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
I tried a lot on this problem but alas couldn't get AC :\ Here is what i observed. If (x % 4 == 2 | x % 4 == 3) and x != 2 then no matter what the value of m is first player wil always win since xor of the series would never be zero. So x can be like: 3,6,7,10,11,14,15...
The second thing was all numbers that don't belong to the above series if xored 4/8/12/multiple of 4 times then the result will be zero. Eg: 5^7^9^11 = 0 and 5^7^9^11^13^15^17^19 = 0 Last thing if x == 2 then it works with multiple of 3/7/11/15.. times Eg: 2^4^6 = 0 and 2^4^6^8^10^12^14 = 0
Still got WA after implementing above logic, but i am unable to find out where i am going wrong
Edit: I got it i was missing on the base case when m == 0 so no move can be made and BOB will win. AC submission on the above logic: https://www.codechef.com/viewsolution/8857389
Your first assumption is completely wrong . Consider this case x = 6 and m = 1 . In this case , we have just one element i.e 6, and ALICE (player1) can take all of them , leaving BOB unable to make a move and will win thus .
Yeah i mistyped here. Fixed it now. It should be since xor would never be zero it will always the first player who will win. Also i got the mistake after checking others code and can't believe it its the stupid base case when m == 0 :| Here is link to submission: https://www.codechef.com/viewsolution/8857389