Привет, Codeforces!
У меня появилось желание перед Good Bye 2016 хорошенько проверить, что всё работает как надо.
Приглашаю вас принять участие в Testing Round 13. Старт состоится 29-го декабря в 12:05. Раунд будет неофициальным, нерейтинговым. Продолжительность: 75 минут.
Претесты будут необычно слабыми, чтобы спровоцировать побольше взломов.
Ждите интерактивных задач. Надеюсь и увидеть взломы по ним.
Спасибо,
MikeMirzayanov
UPD: Соревнование завершено. Спасибо всем, кто помог протестировать платформу. Всё работает отлично, мы готовы к Good Bye 2016!
I would help with the testing but the time is so early for me :(
Since there will be an interactive problem in the Good Bye contest, will the testing round also have an interactive one?
"You may expect interactive problems. Hope for hacks for them."
Yeah guess I just skipped over that while reading.
Anyone else is desiring to change nickname like me? :)
nice presents(cf round) for saying Goodybye 2016
I desire
How many problems?
3 or 4
When we can change Nickname?
After Good bye.
This reminds me the great Education Codeforces Round by Edvard .
Ahh missing those Educational Codeforces Round .Sir do you have any plan to restart this Round?
Happy Hacking for All.
I was just thinking the same yesterday !! :D
I have a lot of games did not attend, in The hope that The contest Goodbye2017 would it be possible for me to rise!
** ** *****? :P
"It will be unofficial unrated round."
Число 13 меня изрядно напрягает...
А меня нет.
Завидую вашему оптимизму)
How to solve C task? I couldn't invent something with smaller than 15 queries :(
Most solutions I see in my room uses Brute Force (always query one possible candidate and then eliminate all the impossible numbers. Repeat until your set of possible candidates is of size 1). However, I don't think this will work because I hacked 2 other people in my room who passed pretests with 9431. I might fail System Test as well.
UPD : I failed System Test as expected.
P.S. There is a decision tree here that claims to solve the problem in 7 moves.
I think that what you should also be doing, is not just choosing one possible candidate, but the one that minimizes the number of remaining candidates in the worst outcome.
I submitted your idea using
unordered_setand got WA on test61: 23664758when I submitted same code using
setmy code accepted: 23665361I can't figure out what is the problem with my first submission and what is difference between
unordered_setandsetin this case? :(UPD:
unordered_setis a container based on hash, and hash is hackable! I guess it is the reason.That's interesting. I precomputed "optimal" decision tree (always choose a query which minimises the maximum candidature of the outcome) on my computer and copied it into an array. Managed to fit solution size into 38kb.
Check out [submission:23395909]
Update: actually, I just realised my decision tree isn't optimal at all. Minimising maximum number of remaining candidates is actually greedy: I should be minimising the maximum depth of remaining candidate subsets! I wonder if you can find the optimal tree deterministically faster than NP...
Thanks !
I thought all the time about some greedy algorithm :)
0123,1234,2345...6789 gives 7 queries to ask. I could not figure out how to infer the string from them in the time left..Just a guess. :)
You can only ask 6 because the 7th one should be a correct guess.
There's a five-guess algorithm (https://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm) by Knuth for Mastermind.
Same idea applies here as well, except for there are ten possible digits instead of six, thus giving not five, but a little bit more moves (7-ish or so)
UPD: Yet it failed system tests :(
http://slovesnov.users.sourceforge.net/bullscows/bullscows.pdf
I can't endure these academic papers.
no hacks !! lets enjoy system testing now
I had one solution in 8 queries but none in 7 queries :(
someone got Runtime error on test 367 in Problem C
LOL XD
someone got Runtime error on test 367 in Problem C
LOL XD
It's quite easy to get a Runtime error if you forget about the fact that the program must terminate after it makes a correct guess. It's unlikely to happen on a random test case (as the test which such a solution fails depends on the way the queries are generated, and there are very few such tests for any reasonable way of generation), but it's likely to happen on at least one test case of a few hundreds.
It's me. :(
The RE is from that if I can't guess out the hidden string, it will trigger an assertion fail.
But, after changing random first guess to fixed first guess, it got AC now. However, I'm still not sure why random first guess will fail to guess the hidden string in 7 queries.
Now that's what I call exhaustive testing.
Hello,
Why did http://codeforces.net/contest/753/submission/23394205 pass, given that it does not terminate after it makes a correct guess?
:D
Sorry, possible I am not enough good at Interactive problems and maybe I didn't read careful Interactive guide, but I have question :D
I spent a lot of time to find mistake at my program and it was printf without "\n" (new line). Is somewhere written that we need to use "\n" ?
White space is enough. You just need to separate your answers: 23397246
Bad:
12341235Good:
1234 1235Thanks, now I understand.
Somehow I thought they will separate answers without my help :D
real programmers always defeat cheaters
No Comments! ;)
What is the logic behind Problem A? I tried it by finding a number 'd' such that given number 'n' lies between 1+2+....d and 1+2+...(d+1). But i was unable to do any further. Any help of explaining the approach would be helpful. Also, i have went through some of the accepted solutions and they did some "add n to the last element". Why?
The number of kids to which we will give n candies is k + 1. We will give 1 + 2 + ... + k candies to the first k kids and remaining n - 1 - 2 - ... - k candies to the last (k + 1)'th kid.
1. This sum is strictly less than n. That is 1 + 2 + ... + k = k·(k + 1) / 2 < n.
2. The remaining amount of candies is strictly larger than k. That is r = n - k·(k + 1) / 2 > k.
Could you shed some more light on second inference. I am having trouble in finding why this method should work OR more clearly, intuition with which you came to such solution. Thanks a lot.
I've gained intuition after solving this problem.
For now you could try looking into examples:
10 = 1 + 2 + 3 + 4
11 = 1 + 2 + 3 + 5
12 = 1 + 2 + 3 + 6
13 = 1 + 2 + 3 + 7
15 = 1 + 2 + 3 + 8
In the last case n = 15, we can try to improve our distribution by splitting 8 into two parts.
Here are all the possible partitions of 8 into two parts:
8 = 1 + 7
8 = 2 + 6
8 = 3 + 5
8 = 4 + 4
We know that the next number we can use has to be at least 4, because we have used numbers {1, 2, 3} already. This automatically discards 3 out of 4 partitions: {(1, 7), (2, 6), (3, 5)}, because these partitions contain forbidden numbers 1, 2 and 3. The only partition that is not discarded because of the already used numbers is the following: 8 = 4 + 4. But we cannot use the number more than once in our distribution, so the following partition is invalid: 15 = 1 + 2 + 3 + 4 + 4.
But we can improve k from 4 to 5 if we are given n = 16:
16 = 1 + 2 + 3 + 4 + 9 = 1 + 2 + 3 + (4 + 5).
Let d be the minimal number such that 1 + 2 + ... + d > n. Denote this sum 1 + 2 + ... + d as s.
We are almost finished, just output all numbers from 1 to d, except s — n.
E.g. if n = 13, it's 1 + 2 + 3 + 4 + 5, s = 15, output 1, 3, 4, 5 and don't output 15 — 13 = 2.
:D
Experience is your reward :)
:D
I'm a bit curious of how the run time is determined for the interactive problem, e.g. is running time of the testing machine (that we interactive with) is counted?
I submitted the same solution for C 3 times and got 3 different results:
TLE test 25
TLE test 259
AC
The problem is the 3rd submission run in ~300 ms less than the 2nd submission at test 259 (they are run with same source code, and same input)
editorial?
In the Hard version of Bulls & Cows, were all the test cases static numbers to guess? Or we need to guess the number from a smarter adversary. I think the latter is more challenging.
arent both same,since testcaes consisted of all possible strings
No, since an smart adversary doesn't need to pick the hidden number from the beginning. He only needs to keep their answer consistent, it means, at least one valid answer must exist, but he can guide you through a path of outcomes that force you to do more than 7 question, analyzing your guesses.
It can be guaranteed as you say, if all possible numbers are asked and the solution is deterministic, otherwise I'm not so sure. Btw, I don't think all possible numbers are asked, but only ~400.
But if all possible strings are included, a 'killer adversary' won't make a difference (your guess will still be the same), unless your algorithm included something random (well, it's not the fault of adversary :p)