Google Code Jam Round 1C

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

DP Bitmask - Topic Stream

Shayan

Трансляция идет

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя manishbisht

Google Code Jam Round 1C

Автор manishbisht, история, 9 лет назад, По-английски

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 :)

google, google code jam, codejam, gcj

manishbisht
9 лет назад
47

Комментарии (43)

Показать архивные | Написать комментарий?

adamant

9 лет назад, # |

C-large?

→ Ответить

Shapo

9 лет назад, # ^ |

+19

int j, p, s, k;
cin >> j >> p >> s >> k;
vector< vector< int > > res;
int diff = min(s, k);
for (int i1 = 0; i1 < j; ++i1) {
    for (int i2 = 0; i2 < p; ++i2) {
        for (int l = 0; l < diff; ++l) {
            int i3 = (i1 + i2 + l) % s;
            res.push_back({i1 + 1, i2 + 1, i3 + 1});
        }
    }
}

→ Ответить

WasylF

9 лет назад, # ^ |

you are genius! my solution of C_small is about 100 lines:)

→ Ответить

satyaki3794

9 лет назад, # ^ |

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.

→ Ответить

Shapo

9 лет назад, # ^ |

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).

→ Ответить

mgemaakbar

9 лет назад, # |

← Rev. 5 →

-6

is the solution to problem A: always remove first two biggest numbers of senators?

nvm source code removed

→ Ответить

adamant

9 лет назад, # ^ |

No. If there is three senators from different parties, you should firstly remove only one of them.

→ Ответить

abistrigova

9 лет назад, # ^ |

Countertest is 1 1 1. You'll remove AB. Then you'll have one C. But the correct answer is A B C.

→ Ответить

misof

9 лет назад, # ^ |

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.

→ Ответить

abistrigova

9 лет назад, # ^ |

Yes, you're right. I've misprinted.

→ Ответить

sanket407

9 лет назад, # ^ |

If there are odd no of total senators , In first move remove only 1 largest senator Then for rest keep removing 2 largest ones

→ Ответить

anh1l1ator

9 лет назад, # |

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.

→ Ответить

HappyPerson

9 лет назад, # ^ |

Oh. I just learned I made the same mistake. Never fixed it during the contest. I know how you feel...

→ Ответить

NedoL

9 лет назад, # |

C-small?

→ Ответить

WasylF

9 лет назад, # ^ |

I generate set of all possible variants and the find best subset. But it looks like just hardcore all answers is simpler:)

→ Ответить

NedoL

9 лет назад, # ^ |

Isn't it O(T * 2 ^ 27 * 27)?

I mean, that shouldn't give an answer in 4 mins, right?

→ Ответить

kalimm

9 лет назад, # ^ |

You can remove one 27 with just doing dfs, which is enough.

→ Ответить

WasylF

9 лет назад, # ^ |

O(T * 2 ^ 18 * 18), I hardcore answers for 3 3 3 k

→ Ответить

NedoL

9 лет назад, # ^ |

Thanks!

→ Ответить

adamant

9 лет назад, # ^ |

+13

But it gives the answer in about 2 mins, Lily

→ Ответить

NedoL

9 лет назад, # ^ |

+11

OK, will definetely try brute-force next time.

P.S. You missed letter 'l' in my name.

→ Ответить

Chortos-2

9 лет назад, # ^ |

← Rev. 3 →

I wrote O(T × 2²⁷ × 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 2²⁷ loop body:

    if (Integer.bitCount(mask) <= bestTotal)
        continue;

Now the whole thing terminates in just 12 seconds.

→ Ответить

anh1l1ator

9 лет назад, # ^ |

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

→ Ответить

Chortos-2

9 лет назад, # ^ |

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.

→ Ответить

pyrexshorts

9 лет назад, # |

Was brute force able to pass for C small?

→ Ответить

WasylF

9 лет назад, # ^ |

Yes, if you hardcore answer for 3 3 3 k

→ Ответить

satyaki3794

9 лет назад, # ^ |

Why is this a special case?

→ Ответить

WasylF

9 лет назад, # ^ |

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:)

→ Ответить

kobe24

9 лет назад, # |

1B rank — 1206
1C rank — 1149

i think i will never make to top 1000 :(

→ Ответить

mredigonda

9 лет назад, # ^ |

← Rev. 2 →

+11

1B rank — 1042

1C rank — 1003

Hahaha, and this time the error was so stupid :'(

→ Ответить

sanket407

9 лет назад, # ^ |

+11

I saved all files as .txt and uploaded.Worked fine .

→ Ответить

justforlaugh

9 лет назад, # |

What is the solution for B?

→ Ответить

NedoL

9 лет назад, # ^ |

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

→ Ответить

WhatIsLove

9 лет назад, # ^ |

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/

→ Ответить

Goldsmith94

9 лет назад, # ^ |

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.

→ Ответить

WhatIsLove

9 лет назад, # ^ |

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.

→ Ответить

Goldsmith94

9 лет назад, # ^ |

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

→ Ответить

sanket407

9 лет назад, # ^ |

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

→ Ответить

rajeevkgp

9 лет назад, # |

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 :(

→ Ответить

P___

9 лет назад, # ^ |

If you download input twice, you should have only one incorrect submission, you can try making a complaint.

→ Ответить

unprost

9 лет назад, # ^ |

Now you're in :)

→ Ответить

Goldsmith94

9 лет назад, # |

+14

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.

→ Ответить

spiderbatman

9 лет назад, # ^ |

Same Here

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 19.11.2024 16:25:29 (k3).

Десктопная версия, переключиться на мобильную.

При поддержке