|
|
|
So, this match has really terminated me and although I would love to blame my current flu for that, it looks like it is worse than that.
So, bunnies are unnecessary, I've read many threads and I still don't get it. So here is my question.
I've read that it only depends on getting the probability of taking all the monsters before you, and then it is 1/(M+1) , but the thing is that it is possible that there was an even amount of monsters selected before you, yet you still die, let's see:
M=4, B=1
MM MB MY
In this case the 4 monsters come before you, but one gets to kill the bunny, so the last monster can just kill you.
PS: Look at my submission for this problem during the match, it just doesn't make any sense, and I am not sure why it wasn't challenged... |
|
|
|
|
That one gets to kill the bunny, and stays alive. So after that monster killed the bunny, we have 2 monsters and you left. Suppose the 2 monsters meet each other afterwards, you survive. So it actually is:
MM MB MM Y |
|
|
|
|
I'm surprised this set got past the testers at all just looking at the success rate. Abysmal. At least I'm back to div 2... |
|
|
|
|
I am not so good at explaining but let me try
Bunnies
They can't save you from monster , so their number is independent of answer
Now the Monster
Two case exist case M is odd
How monster meet can't change your luck , you
will be kill ultimately
if M is even (smart person don't bistate to think small)
if M is 2 let number them 1,2 and your no is 0
now the sample space of metting is 12,10,20
now you are alive only in case of 12 if two monster
meet
so the probabililty is 1/3 in this case
If you look at the pattern for some M you will get your explanation why it is 1/(M+1);
A more interesting problem for marathon match will be if we give some weight to each monster , i.e their fighting capabilities than chance your survival |
|
|
|
|
It is possible to get a solution to work with a 2D memoized approach without making the assumption that the bunnies don't matter, you just have to be a little careful about the fact that if 2 bunnies meet (or if you meet a bunny and decide not to kill it), then you end up in the same state you're in at the moment. Your solution does something a little funny when 2 bunnies meet. The function logic should be something like:
f(0,B) = 1.0 // no monsters left, so we survive
f(1,B) = 0.0 // 1 monster left, so we always die
f(M,0) = p(2 monsters) * f(M-2,0) // No bunnies left, so only consider monsters
Now assume that if we meet a bunny at this step we will kill it
fkill(M,B) = p(2 monsters)*f(M-2,B) + p(monster/bunny)*f(M,B-1) + p(us/bunny)*f(M,B-1) + p(2 bunnies)*f(M,B)
Here we have f(M,B) on both sides of the equation, so we have to solve for it. I.e,
fkill(M,B) = [ p(2 monsters)*f(M-2,B) + p(monster/bunny)*f(M,B-1) + p(us/bunny)*f(M,B-1) ] / [1.0 - p(2 bunnies)]
Similarly,
fdon't-kill(M,B) = [ p(2 monsters)*f(M-2,B) + p(monster/bunny)*f(M,B-1) ] / [1.0 - p(2 bunnies) - p(us/bunny)]
and clearly
f(M,B) = max(fdon't-kill , fkill)
I think I would also have fluffed this problem if I had met it in the match. My intuition would have told me that the bunnies don't matter, but I never trust my intuition and would probably have tried to implement the above solution and made a mistake somewhere.
Nasty problem for a 250! I think I would have rated this one at 350 and the 600-pointer at 500 (I don't really see what's hard about the 600). |
|
|
|
|
I've read that it only depends on getting the probability of taking all the monsters before you, and then it is 1/(M+1) , but the thing is that it is possible that there was an even amount of monsters selected before you, yet you still die, let's see:
M=4, B=1
MM MB MY
In this case the 4 monsters come before you, but one gets to kill the bunny, so the last monster can just kill you.
There are M monsters plus you. Let the fights continue until only one of you is left. Of all the fights that happen, look at the subset of fights that are either monster vs. monster or monster vs. you (call these the "important" fights). Order the monsters (plus you) according to when they first appeared in an important fight. Does that make it clearer? |
|
|
|
|
The problem set was as close to division 1 level set as you can get; the easy had the "Ah ha!" solution as many other solutions have had (but if you can't find the "Ah ha!" there's a slightly longer way), and med/hard were about normal. The major difference was the fact that there were quite a fair number of division 2 coders competing, which is going to skew the stats towards a lower success rate initially.
This set gave anyone with either of two skills the opportunity to advance: a) solve a problem, or b) successfully challenge. It ended up just as they've done in previous Qual rounds, with less than 500 advancing in the first round.
I'm not 100% positive if it's good, but it's consistent with what's been done before. |
|
|
|
|
I really don't know what happened there, I also subtracted monsters when they met bunnies (which is not good)
I knew my solution would fail because of the non-state changing part that you solved (thanks btw, that I really needed to learn) but when I saw the solution again after the match I found out it was totally implemented badly.
I had some hopes for the challenge phase to prevent myself a 0.0 but I think I accidentally left KawigiEdit testing my ultra slow initial solution for 900 (I really liked this one unlike the rest, wish I started with it) cause my computer froze during the challenge phase, after I rebooted the challenge phase ended. |
|
|
|
|
A division 1 set is not something you'd expect for the qualification rounds, even so , it didn't look like a div 1 set to me. It was very strange, that or my brain was turned off that day (which is likely) but hey! I have been given a chance to play this Saturday! |
|
|
|
|
First, dplass, you are being unfair here. If you want to say something about the quality of the problem set, blame the one responsible, i.e. the writer (which in this case would be me).
The testers did a great job, the problem statements were clear (I think we got a total of four questions during the entire match), and there were no issues with the system tests.
As for the difficulty, the results are exactly what I was aiming for -- this was the first of three qualification rounds, and the difficulty was intentionally a bit harder than the other two rounds.
As connect4 said, "This set gave anyone with either of two skills the opportunity to advance: a) solve a problem, or b) successfully challenge."
This was intentional, and anyone who bothered to take a look at previous years would know that "trying to make sure I have a positive score" is the way to go in the quals.
When compared to div1 and div2 sets, I think that the difficulty of this one was somewhere halfway in between. The 600 was a vanilla DP, and the 900 could be easily pre-computed using brute force (and quite a few lower rated coders managed to do this). Anyone that can solve them -- regardless of how quickly -- or see the trick in the 250, or even manage to make a successful challenge, deserves to advance and relax. And for the others there are two easier qualification rounds yet to come, and they should resemble div2 sets more. (And no, I didn't write those. :) ) |
|
|
|
|
That's exactly how I would have approached the problem. I wouldn't have wanted to take a chance on my first instinct and said that bunnies don't matter, for fear of some corner case. You could just look at the problem and see that it screams for challenges. |
|
|
|
|
I agree that there was nothing wrong with the problem set. In fact, I think it was perfectly suitable for a qualification round.
However the 250 pt'er threw me off as well, but I don't think anyone is to blame for that. It was my own stupid fault really. Personally, I blame my mind for not working properly after 3:00 AM.
The a-ha! moment for me was when I stopped and realized two things completely unrelated to the actual problem:
- This is the EASY problem in a QUALIFICATION round for the TCO where 1800 people will compete. It cannot possible be this hard; there must be an easy solution.
- The example cases are suspiciously unhelpful. They only give away the most basic cases. This suggests there might be an extremely trivial solution that would be spoiled by more complex test cases. |
|
|
|
|
Now I know why you don't want to compete ;) |
|
|
|
|
So was the 250 designed to trip up so many people? It was deliberately a "trick question"? That's mean, but also not inappropriate in my opinion. Perhaps a little cruel to do it in a TCO round but I think problems like that in SRMs make things a bit more varied. |
|
|
|
|
I implemented that but my function calc(,) called survivalProbability(,) instead of calling itself and memo was cleared at each step. I spent 7 minutes trying to find the bug that was causing TLE and found it 30 seconds after the coding phase. Then I challenged a gray that "forgot" to use the bunnies and made an "stupid" solution(1/(M+1)). |
|
|
|
