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

*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 - New Year Transportation

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 - New Year Permutation

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 - New Year Book Reading

500D - New Year Santa Network

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 ≤ 10⁵ and d ≤ 10³ 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 - New Year Domino

500F - New Year Shopping

500G - New Year Running

Fastest hackers

Best hackers

Best rooms

Best countries

Country	#hacks	Hackers
Russia	182	Misha100896 [13], SirShokoladina [8], Tviskaron [8], niyaznigmatul [8], shilov [8], Artem_kh [8], Vaness [7], Nikitosh [6], VArtem [6], redoak [6], Petruchcho [6], Lelby [6], Romchela [6], Petr [6], qwerty787788 [5], gepard211 [5], Um_nik [5], Milanin [5], alberist [5], ASverdlov [4], Sert [4], el_sanchez [4], KBOPYM [3], al13n [3], Babanin_Ivan [3], Schullz [3], knst [3], SlavaSSU [3], Merkurev [3], sivukhin [2], GlebsHP [2], AGrigorii [1], Igorjan94 [1], pvs [1], Malinovsky239 [1], HolkinPV [1], ultizet [1], Belonogov [1], AndreySiunov [1], arturom [1], Shapo [1], Sinner [1], Slamur [1], GoDDoS [1], shevk [1], enot110 [1], DimaPhil [1], nic11 [1], DmitriyH [1]
Iran	65	aliasadiiii [8], SAKT [8], poopi [6], somag [5], mosiomohsen [5], spOoky [5], hsnprsd [4], Damon [4], oofldw289 [3], ashkan_d13 [3], No0oB [3], M.Mahdi [2], Kianoosh [2], Haghani [1], JeBeK [1], taki [1], Reyna [1], NikaraBika [1], MHR [1], m.h [1]
India	59	ddt [11], akashdeep [10], rituranjna [8], logic_max [6], girish347 [4], swap [3], rivudas [3], osank [2], anudeep2011 [2], abhay26 [2], grayhathacker [2], PraveenDhinwa [1], ShekharNain [1], utsav_deep [1], SameerGulati [1], ashu1461 [1], anuraganand [1]
Belarus	58	Ra16bit [8], aandrukhovich [7], tourist [7], sas4eka [6], subscriber [5], KonanMentor [4], omse1998 [3], Rostislav_the_great [3], AlvinMax [3], greencis [3], Yury_Bandarchuk [2], kefaa [2], taxicoo [1], vitux [1], sdryapko [1], wilcot [1], vilcheuski [1]
China	55	liympanda [12], InheritG [8], zerotrac [5], SanSiroWaltz [4], hzt1 [2], MrSunday [2], last_one [2], tianchouczl [2], Lee_vincent [2], chuizi [2], Skyshirk [2], LGWLGWLGW [2], mathlover [1], C_SUNSHINE [1], BrightestSirius [1], Dwayne [1], JCsoulsky [1], JayYe [1], only_998 [1], v-guihom [1], 31201153 [1], wangchaohui [1]
Japan	54	kzyKT [10], yuusti [7], rng_58 [6], kmjp [6], ChronoireSchwarzVI [5], atetubou [4], zeosutt [3], kakira [3], iga-c [3], dai1741 [3], evima [1], wrong [1], DEGwer [1], UminchuR [1]
Ukraine	45	Antoniuk [10], Programist [9], I_love_Tanya_Romanova [8], sdya [6], MrDindows [5], KADR [5], DJiGIT [1], ibra [1]
Brazil	32	tiagob.reis [7], Juniorandrade [7], ffao [6], fulvioabrahao [4], rasinhas [4], thiagocarvp [3], marcoskwkm [1]
Egypt	31	Killever [5], Noureldin [4], Walid_Amin [3], MahmoudAGawad [3], zetamoo [3], TahaMahmoud [3], Kareem [2], mohamednabil00000 [2], hamedArafa [2], BitHashTech [1], Mohammad_Yasser [1], AhmedAtef07 [1], ahmad_mamdouh [1]
Vietnam	28	Foy1998 [7], phankhai [5], ngfam_kongu [4], dnk [3], sillyboy [2], TONYTRAN [2], ngochai94 [2], vodanhna [1], nguyenchicuong [1], duyduc [1]
Armenia	22	albertg [11], sparik [9], armand [2]
Poland	22	Marcin_smu [6], kostka [5], Errichto [5], dj3500 [3], liadoon [2], akrasuski1 [1]
Kazakhstan	21	Aeon [6], a_kabdygali [5], SmallBoy [3], ADJA [2], mexmans [2], Na2a [1], Zhandos [1], zhabo [1]
Taiwan	18	dreamoon_love_AA [7], paulwang [6], domen111 [5]
Indonesia	14	chaotic_iak [8], PieceOfCode [6]
Bangladesh	12	Honour_00 [8], the_redback [2], ashiquzzaman33 [1], imtzhsn [1]
Switzerland	12	W4yneb0t [6], ilyakor [6]

Thanks for reading and happy New Year!