Still in buoyant humour after Good Bye 2014? While waiting for the editorial, maybe you would like to know why there were so many hacks in the last round of this year?
As always, please share you thoughts, ideas or maybe hacks :)
Previous posts can be found here.
Stats
Problem | Successful hacks | Unsuccessful hacks | Other* | Sum | Solutions which can be hacked | Accepted solutions | All solutions on final tests | Hackers efficiency** |
---|---|---|---|---|---|---|---|---|
500A - Транспорт на Новый год | 199 (40.61%) | 124 (25.31%) | 167 (34.08%) | 490 | 375 (9.32%) | 3650 (90.68%) | 4025 | 34.67% |
500B - Новогодняя перестановка | 738 (67.40%) | 214 (19.54%) | 143 (13.06%) | 1095 | 573 (24.89%) | 1729 (75.11%) | 2302 | 56.29% |
500C - В Новый год --- с книгой! | 0 (0.00%) | 9 (75.00%) | 3 (25.00%) | 12 | 23 (1.08%) | 2114 (98.92%) | 2137 | 0.00% |
500D - Новогоднее взаимодействие Санта-Клаусов | 4 (26.67%) | 3 (20.00%) | 8 (53.33%) | 15 | 150 (16.82%) | 742 (83.18%) | 892 | 2.60% |
500E - Новогоднее домино | 0 | 0 | 0 | 0 | 8 (3.77%) | 204 (96.23%) | 212 | 0.00% |
500F - Новогодние покупки | 0 | 0 | 0 | 0 | 1 (3.03%) | 32 (96.97%) | 33 | 0.00% |
500G - Новогодний забег | 0 | 0 | 0 | 0 | 0 | 0 | 0 | — |
*one of the: INVALID_INPUT, GENERATOR_INCOMPILABLE, GENERATOR_CRASHED, IGNORED, OTHER.
**suggested by marat.snowbear and Yura_Sultonov — hacked solutions / (hacked solutions + solutions which failed on final tests).
Hacks and possible hacks description
500A - Транспорт на Новый год
Test #13 is pretty worth seeing:
4 4
2 2 1
Also, many hacks was something like:
n n
1 1 1 1 1
Many people forgot about last cell (the n-th one), maybe because of input.
500B - Новогодняя перестановка
Because there are no editorial yet, I have to say something about one solution which passed all pretests and was hacked many times.
It was just greedy swapping positions if it was possible, like this:
while(swapped)
{
swapped = False
for i=1,2,...,n
for j=i+1,i+2,...,n
if M[i][j] and p[i] > p[j]
swap(p[i],p[j])
swapped = True
}
You may see that for such test:
3
2 1 3
001
001
110
the output for this algorithm would be 2 3 1
, when you can simply make 1 2 3
(2 1 3 -> 2 3 1 -> 1 3 2 -> 1 2 3).
Probably, it was also included in test #15.
Thanks to tbm, Aeon and minty99 for finding mistakes.
500C - В Новый год --- с книгой!
500D - Новогоднее взаимодействие Санта-Клаусов
With this problem, you may noticed that it could be problem with big values. Really big values... Let's think about simple tree: a lane (with edges 1—2, 2—3, 3—4, ..., n - 1 — n). Let's say that every edge cost d and we suppose that we choose vertex with number one as one of the Santas' warehouse. We can notice that the approximation of the summarized cost for all networks with 1 is already pretty big:
With n ≤ 105 and d ≤ 103 can be little too big even for 64-bit numbers (the sum above was only with one fixed points).
Thankfully, we just needed to count expected cost, so with some division we can do it with long longs — you just have to be careful with calculations.
It was checked by test #22.
500E - Новогоднее домино
500F - Новогодние покупки
500G - Новогодний забег
Fastest hackers
Problem | Time | Hacker | Defender | Hack |
---|---|---|---|---|
500A - Транспорт на Новый год | 0:08:44 | ondrah | AboveWood | 130441 |
500B - Новогодняя перестановка | 0:43:02 | yuusti | rui-de | 130478 |
500D - Новогоднее взаимодействие Санта-Клаусов | 1:34:07 | TMandzu | JATC | 130897 |
Best hackers
Best rooms
Room | #hacks | Hackers |
---|---|---|
21 | 14 | Misha100896 [13], smv98 [1] |
30 | 14 | maximumSHOT [12], osank [2] |
3 | 13 | kozinov [9], KonanMentor [4] |
51 | 13 | ddt [11], kefaa [2] |
141 | 13 | Artem_kh [8], Damon [4], Reyna [1] |
12 | 12 | Programist [9], VietaFan [1], Zhandos [1], 31201153 [1] |
20 | 12 | kzyKT [10], sivukhin [2] |
27 | 12 | SirShokoladina [8], mohamednabil00000 [2], AGrigorii [1], m.h [1] |
69 | 12 | liympanda [12] |
92 | 12 | Isfandiyor [7], domen111 [5] |
9 | 11 | Marcin_smu [6], Milanin [5] |
39 | 11 | ilyakor [6], HYPERHYPERHYPERCUBELOVER [3], dwoolley3 [2] |
40 | 11 | svanidz1 [6], ASverdlov [4], Shapo [1] |
82 | 11 | redoak [6], rasinhas [4], zhabo [1] |
87 | 11 | albertg [11] |
134 | 11 | shilov [8], TONYTRAN [2], Mohammad_Yasser [1] |
10 | 10 | aandrukhovich [7], Kareem [2], SamanSami [1] |
50 | 10 | tourist [7], Lee_vincent [2], DimaPhil [1] |
78 | 10 | Horea [6], JoeyWheeler [2], MrSunday [2] |
83 | 10 | sparik [9], nguyenchicuong [1] |
89 | 10 | Antoniuk [10] |
95 | 10 | akashdeep [10] |
143 | 10 | Honour_00 [8], ngochai94 [2] |
Best countries
Thanks for reading and happy New Year!
In problem B, you have written,
(swapping first 3 with 1 and then 1 with 2)
if initially the array is2 1 3
then swapping 3 with 1 will give2 3 1
then swapping 1 with 2 will give1 3 2
. How I cansimply
make1 2 3
?2 1 3 -> 2 3 1 (swap(2nd, 3rd)) -> 1 3 2 (swap(1st, 3rd)) -> 1 2 3 (swap(2nd, 3rd))
Sorry for mistake, I tried to swap the output instead of input :)
In the wrong code example of problem B:
if M[i][j] and p[i] < p[j]
I think it should be "if M[i][j] and p[i] > p[j]" (Because we should make the small numbers to the front of permutation)
Thanks for your great post!
Yeah, thanks for pointing it out. :)