Don't forget that Google Code Jam Round 1C will be starting in less then 28 hours !! Visit the Code Jam site and get ready to compete.
Let's discuss solutions here after the contest. I would like to know other peoples approaches.
Good Luck :)
Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | SecondThread | 148 |
| 5 | atcoder_official | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.07.2024 21:31:13 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
C-large?
you are genius! my solution of C_small is about 100 lines:)
Can you please explain what you are doing? You have chosen diff as min(s, k), so any pair of (jacket, pants) will not occur more than 'diff' times. But what about the (jacket, shirt) and (shirt, pants) pairs? I did not understand how this guarantees that those pairs will also occur <= k times.
It's easy to prove that for arbitrary present pair (i1, i3) of jacket and shirt and every l in range [0;diff) there is at most one valid pants i2, i.e. satisfying constraints i3 ≡ (i1 + i2 + l)(mod s), because s ≥ p ≥ j. That's why we get no more than diff ≤ k pairs (i1, i3).
The same holds for arbitrary present pair (i2, i3).
is the solution to problem A: always remove first two biggest numbers of senators?
nvm source code removed
No. If there is three senators from different parties, you should firstly remove only one of them.
Countertest is 1 1 1. You'll remove AB. Then you'll have one C. But the correct answer is A B C.
You probably made a typo there. The correct answer is "A BC" and symmetric versions thereof. The answer "A B C" is not correct because after A and B leave C would have majority.
Yes, you're right. I've misprinted.
If there are odd no of total senators , In first move remove only 1 largest senator Then for rest keep removing 2 largest ones
It was so frustrating that I was debugging my B for more than 20 minutes just because I was printing extra spaces between the elements. =/
Reminds me of how stupid I can be at times.
Oh. I just learned I made the same mistake. Never fixed it during the contest. I know how you feel...
C-small?
I generate set of all possible variants and the find best subset. But it looks like just hardcore all answers is simpler:)
Isn't it O(T * 2 ^ 27 * 27)?
I mean, that shouldn't give an answer in 4 mins, right?
You can remove one 27 with just doing dfs, which is enough.
O(T * 2 ^ 18 * 18), I hardcore answers for 3 3 3 k
Thanks!
But it gives the answer in about 2 mins, Lily
OK, will definetely try brute-force next time.
P.S. You missed letter 'l' in my name.
I wrote O(T × 227 × 27) in Java with multithreading, and it took 3 minutes 21 seconds (8 minutes 58 seconds total CPU time)—but I screwed up a bit and ended up running out of submission time somehow (and with too little contest time to make another attempt).
After the contest, I added these lines at the start of the 227 loop body:
Now the whole thing terminates in just 12 seconds.
I did total brute with some optimizations ( I read the constraints incorrect and I thought total combinations will be only 9 ) that is why I wrote a total brute.
Link to code
It ran in about 27 seconds
Yep, the popcount check really helps. Like I said in another comment above, my brute went from 9 minutes to under 20 seconds when I added the popcount check. Sadly, I didn’t do it during the contest, as I didn’t imagine it would have such a huge effect.
Was brute force able to pass for C small?
Yes, if you hardcore answer for 3 3 3 k
Why is this a special case?
Because for this case there are 27 possible variants and for all others less then 18. O(2^27) is too much (if you haven't 10+ threads), but O(2^18) is OK:)
1B rank — 1206
1C rank — 1149
i think i will never make to top 1000 :(
1B rank — 1042
1C rank — 1003
Hahaha, and this time the error was so stupid :'(
I saved all files as .txt and uploaded.Worked fine .
What is the solution for B?
The main idea is following: let's build a graph, where there is an edge V -> U (for all V, U, V < U). It's easy to see, that in this graph the total amount of ways to get from point 1 to point N is 2 ^ (N — 2) (because we can choose any subset of vertices from 2 to N — 1 to go through). Now, if we delete an edge 1 -> V0, we'll lose 2 ^ (N — V0 — 1) ways. Thus, we can use greedy algorithm : iterate over all V0 (from 2 to N — 1) and try to remove an edge (1 -> V0).
Code : http://pastebin.com/WrGmMdtU
We can also not to remove, but add the edges (1 -> K) using the binary representation of (m - 1)
(edge (1 -> B) that gives us 1 way I took in any case).
Code: http://paste.ubuntu.com/16298555/
Yeah and I kept adding edges from i to j for all i < j in a loop going through all j for each i from 2 to B-1 until I had gone above M, and then I used the binary representation of the difference between how many paths there currently was (which I had kept count of) and M, to delete the edges between the bits that are on in the difference and B-1, it follows the same kind of logic to prove it works.
Your solution seems to be unnecessarily complicated. The main reason for me to use binary representation was to avoid greediness. Since every number has exactly one binary representation, I can iterate from 0 to B-3 or vise versa and get the solution anyway.
I agree that yours which is also the way of the contest analysis is much more straight forward, I just came to the other one, and thought I'd share a similar but different approach :). I don't use anything that's greedy either though, I just keep adding edges until I'm past M and if it's not equal to M I use the binary representation of the difference to remove edges that will make the paths == M
I did backtracking + dfs Basically kept adding edges using dfs as long as no. of paths was less than M If addition of new edge led to no of paths >M remove it and try others Keep count of no. of paths starting at a particular bldg and ending at final building
http://pastebin.com/MaKJBdGK
I accidentally deleted my input0 for 1st problem, so when I downloaded it again, it triggered input1 for the problem, so two incorrect solutions. Can anyone expain this? Anyway I finished with 1004 missing the cut by 20 seconds :(
If you download input twice, you should have only one incorrect submission, you can try making a complaint.
Now you're in :)
That moment when your problem B fails due to ll maximum = 1 << (B-2); overflow that should've been ll maximum = 1ll << (B-2);
"luckily" I would only have placed around 1300 if I'd gotten it correct due to being slow, otherwise I would be punishing myself for that for a week :P.
Same Here