### Xellos's blog

By Xellos, history, 7 years ago,

The next edition of Internet Problem Solving Contest is here!

In case you don't know (yet), IPSC problems come in a great variety, from standard algorithmic ones to problems where you interact with the grader or need to find a specific input.

Most problems have an easy input worth 1 point and hard input worth 2 points; otherwise, the scoring is ACM-like, with WAs on easy inputs giving time penalty 10 minutes instead of 20. The input files are available for download and you only upload your outputs (in a similar manner to GCJ, except there's no additional time limit).

It's a team competition for teams of three. IPSC 2015 takes place on 20th of June, from 11:00 UTC and lasts 5 hours. You may register here.

#### CONTEST IS OVER.

Registered teams

(I won't be adding teams here anymore, because who cares anymore)

Place Points Time Team name Member 1 Member 2 Member 3
5 30 2775 Warsaw Capybaras mnbvmar Swistakk Errichto
6 29 2155 Havka-papstvo Egor pashka Petr
12 28 2166 Knifeproof Tank niyaznigmatul VArtem tourist
16 27 2577 sudo set-position rand()%N fsouza marcoskwkm StefanoT
26 25 1815 Andromeda Express ainu7 JongMan Astein
27 25 1873 Team Accepted Limit Exceeded popoffka Alex_2oo8 Ingus
32 24 2417 ThankYouMikeMirzRAYanovForYou- (sic) CodeforceAndPolygonPlatforms xxTastyHypeBeast666xx JoeyWheeler junkbot
33 24 2423 Unpretired ilyakor Jacob gusakov
35 23 1803 SPb SU 8/3 Dmitry_Egorov PavelKunyavskiy nk.karpov
36 23 2029 Corridors of Time flydutchman Riatre this_isssssyy
40 23 2468 Dig LiTi PrinceOfPersia HosseinYousefi
42 23 2565 stigma sugim48 evima stqn
44 22 1528 RaccoonRush subscriber enot110 antonkov
52 21 1826 W4yneb0t W4yneb0t
55 21 1890 MooOOoOooOOOOoOooooP DemiGuo ksun48 yummy
61 20 1503 iThan chaotic_iak jonathanirvings nathanajah
63 20 1639 itmo150216 izban vlad107 Belonogov
64 20 1706 My Igloo Is Melting Kuroba FatalEagle zxqfl
67 20 1773 Return of Celtic Warriors Tanaeem Sunny dragoon
72 20 2014 ALREADY HAVE DONE _menhera ko_osaga Jiyong Youn
80 19 1345 dolphin secret agents stan acherepanov permin
91 19 1837 MSU Tashkent Old Coders Timur_Sitdikov SergeyLazarev helThazar
102 19 2425 Ural FU Dandelion mpivko Umqra Um_nik
104 18 1335 PAPFans M.Mahdi PAP SeyedParsa
115 18 1692 GD-PSP Jokser sweiss pvasilyev
128 17 1244 Frozen Heart Nikitosh Tehnar ComradePetr
131 17 1433 Zenith ngfam_kongu I_love_Hoang_Yen flashmt
141 17 2324 12.0ngskar dolphinigle Gyosh fushar
142 16 1244 CodeFights ---Grigor--- aram90 armen.tsirunyan
143 16 1281 AOI2 GaryYe fleimgruber
156 16 1722 BajaB ShayanH Lost aliasadiiii
174 15 1309 Please explain why havka eto papstvo OutSide FxF Fcdkbear
180 15 1472 Bangladesh Avengers emo moshiur sohelH
183 15 1533 Saratov SU 1 kuviman IlyaLos danilka.pro
212 14 1319 ZER zholnin e19-un AClover
243 13 1314 cup_of_team cup_of_tea
255 13 1748 Dirsa how_to_become_purple Sanja Mishutnik
265 12 1073 Masr Islamia (╥‿╥) KhaledKEE ahmednaoum Mohamed Al-Jamal
270 12 1197 B-b-b-b-bones! mysterion knst
271 12 1240 ☺ I can't see plus-plus ☺ tjandra
279 12 1389 namelist.insert("দৌড়ের উপর") enzam VUAcoder wasi.ahmed
280 12 1425 kvark161: Kvark161
282 12 1564 8-HD-720p-YIFY-Ganool.3gp azaky farisv makanbeling
301 11 1128 For the watch ashish1610 rohangarg kshitij_jain
303 11 1164 Chega de saudades ivanilos
309 11 1246 sorry_helli SaDDaS Reyna IloveGoodness
318 10 739 Donkey Fly EKGMA ITDOI Teshnizi
320 10 802 dpsd_team rajat1603 sidhant additya1998
321 10 817 Flawless Fdg Furko mgch
335 10 982 unemployed, useless dropout & cute woman vadimmm Rubanenko baba_beda
343 10 1062 Alexander Udalov udalov
348 10 1104 85-85 farzad.shbfn shamir0xe
361 10 1303 Samne Porikkha...Asen Contest Kori zubaer.kh amlansaha Honour_00
376 9 673 bambino 2shraaf Badry mohamed.mehany
383 9 824 SPiromanii&Messi patrick.sava teoionescu george_stelian
414 8 786 Never Slowdown Reza_H DemoVersion
428 8 1023 les apparences sont trompeuses members Safrout KarimElSheikh MedoN11
430 8 1057 UHv6 jcg mnaeraxr
464 7 697 NHSPC Juniors ruhan.habib39 tasmeemreza rubabredwan
485 6 228 TeamUFRN xyz222 Zailton RailtonT
488 6 254 milkyway ptnk_1215_panaka_13 touristv2 TiChuot97
505 6 462 code_phoenix ajinkya1p3 yogeshg39 InnocentFool
519 6 647 Vypiem_za_Lubov Nicolas_Cage Montezuma JoriQ
565 5 489 Nalin Bhardwaj NibNalin
576 5 1031 Sandor team SandorGarcia
588 4 87 GG izi commend me jlr.terceiro ronisds
595 4 110 Nemidunam ArtinTD Alimol
618 4 188 ONU_Feuerbach VVI BronfenBova illarionovam_onu
623 4 204 Hot Tomato Sauce nirob_mh shm0007
633 4 259 DS & DP^2 besher Alex7 RedNextCentury
660 4 846 Primo Manurung zulkan
689 3 76 BK.Troll farmerboy thomas
717 3 159 The Deterministics asdoc asawasa xennygrimmato
746 3 312 hichzat bayram98 horojyk Kerim.K
769 3 512 thehandofgod belowthebelt deepankarak pulkit_180894
773 3 606 KBTU Tarjan azizkhan Madiyar Temirulan
N/A N/A N/A 2017 ACM-ICPC absolute winners T0RRES
N/A N/A N/A Abdelkarim abdelkarim
N/A N/A N/A Binam bijan Nastaran75 spOoky
N/A N/A N/A DivineByCode amankedia Kanish_The_Vista ace_atul
N/A N/A N/A Dodgers vlade087 balle deinier
N/A N/A N/A guptashvm gupta_shvm
N/A N/A N/A Istrebitel Alnair Suhaylee
N/A N/A N/A j1k7_7 j1k7_7
N/A N/A N/A Korol', mudak, i rzhavaya zapchast' accidentallygivenfuck bayram osmanuss
N/A N/A N/A Panda Po chrome Elibay ErzhaNN
N/A N/A N/A shockers AJAY Sundar karthik
N/A N/A N/A Team Zabava radoslav11 vanjo9800 P_Nyagolov
N/A N/A N/A Tmcoteam Allanur Bekmyrat.A _NinjA
N/A N/A N/A Whatever ikbal EMINAYAR enesoncu
N/A N/A N/A Zerry2015 lamngo96 nhathuyen95 duongtnhat

• +167

 » 7 years ago, # | ← Rev. 2 →   +6 Anyone interested in posting team members here?I'll go first:Zenith: (members are sorted in reversed alphabetical order).
•  » » 7 years ago, # ^ |   +5 Mhm, I'll make a table.
 » 7 years ago, # | ← Rev. 2 →   +12 Dig: (members are sorted in reversed alphabetical order).
•  » » 7 years ago, # ^ |   +40 In other words, in reversed reversed alphabetical order? :D
 » 7 years ago, # | ← Rev. 7 →   +6 Bangladesh Avengers
»
7 years ago, # |
Rev. 34   -8

Sorry guys due to some troubles we have changed the team please enter this instead

# sorry_helli

(O) Reyna
(O) IloveGoodness

•  » » 7 years ago, # ^ |   0 However they are sorted by rating (increasing).
•  » » 7 years ago, # ^ |   -8 please change the team Xellos
•  » » » 7 years ago, # ^ |   0 WTF? Everyone here knows that IloveGoodness is xtrome's fake handle and it's banned by administrators.
•  » » » » 7 years ago, # ^ |   +3 :| well he has to have at least one id
•  » » » » 7 years ago, # ^ |   +18 Well I didn't know. Time to make it more known (see edit history).We're gossiping like housewives, dammit.
 » 7 years ago, # | ← Rev. 2 →   0 12.0ngskar
 » 7 years ago, # |   0 If anybody need one more participant, I would like to join.
 » 7 years ago, # |   +1 Tmcoteam:
 » 7 years ago, # |   0 The Deterministics:
 » 7 years ago, # |   +11 Anyone looking for a third teammate or willing to set up a new team in Kiev? Last year I took 44-th place in single person contest but was unable to read all tasks which probably made Sereja a bit less happy.
•  » » 7 years ago, # ^ |   +18 You should ask Sereja to join your team. He won't let it happen again :)
 » 7 years ago, # | ← Rev. 2 →   +17 Team name: 2017 ACM ICPC absolute winners participant №1 : T0RRES participant №2 : ------------ participant №3 : ------------
 » 7 years ago, # |   +3 Team Zabava
 » 7 years ago, # |   +37 Hey Xellos, thanks for posting this! :)We certainly have some fun problems in store for this year as well. Don't miss out!
 » 7 years ago, # |   0 Corridors of Time Looking forward to some more "OMGPROVINGITISADISASTER" problem (like 2014G) :)
 » 7 years ago, # |   +8 GD-PSP - Jokser - sweiss - pvasilyev
 » 7 years ago, # |   0 Return of Celtic Warriors : Tanaeem , _sunny, dragoon
 » 7 years ago, # |   0 namelist.insert("দৌড়ের উপর"): enzam , VUAcoder , wasi.ahmed
 » 7 years ago, # |   +59 Havka-papstvo:
•  » » 7 years ago, # ^ |   +34 What is the story behind your team's name?
•  » » » 7 years ago, # ^ |   0 Havka — papstvo, m'kay?
•  » » » 7 years ago, # ^ |   +34
•  » » » » 7 years ago, # ^ |   +23 I didn't think that targets ever get high! Thanks for the video))
•  » » » » » 7 years ago, # ^ |   0 What is the english translation? I think I have the general idea :P
 » 7 years ago, # |   +22 Saratov SU 1:
 » 7 years ago, # | ← Rev. 2 →   +5 Unpretired:
 » 7 years ago, # |   +8 B-b-b-b-bones!
•  » » 7 years ago, # ^ |   -8 Is it possible to update colors in table? Since both of us improves a bit, during Looksery cup?:)P.S. It could be worth while to do it for all teams
 » 7 years ago, # |   +30 PAPFans: M.Mahdi PAP himself! :D SeyedParsa
•  » » 7 years ago, # ^ | ← Rev. 2 →   +23 what???change that team name please!!
•  » » » 7 years ago, # ^ |   +34 sorry_PAP! :D
•  » » » 7 years ago, # ^ |   +27
 » 7 years ago, # | ← Rev. 2 →   +32 Team Accepted Limit Exceeded (secondary school division, from Riga, Latvia) (popoffka, Alex_2oo8, Ingus) reporting in.IPSC was really fun when we participated (although in slightly different teams) in 2014 and 2013, so we're looking forward to seeing what interesting and unusual tasks the organisers have come up with this year :)
 » 7 years ago, # |   +3 Team: " Masr Islamia (╥‿╥) "Members: KhaledKEE, ahmednaoum, Mohamed Al-Jamal.
•  » » 7 years ago, # ^ | ← Rev. 5 →   0 Please write "br" to pass newline.
•  » » » 7 years ago, # ^ |   +6 hmmm let me try br br br br br hmm br???? :o it doesn't work
•  » » » » 7 years ago, # ^ |   0 Read about it here.
•  » » » » » 7 years ago, # ^ |   0 Too lazy to find a palm face picture.
 » 7 years ago, # |   0 Whatever:
 » 7 years ago, # |   0
 » 7 years ago, # |   0 Frozen Heart:
 » 7 years ago, # | ← Rev. 3 →   +10 Team ꓮꓡꓣꓰꓮꓓꓬ　ꓧꓮꓦꓰ　ꓓꓳꓠꓰ _menhera ko_osaga Jiyong Youn Our first and second teammates are participants of IOI 2015.Our third teammate doesn't have a codeforces account. In fact, he doesn't have a lot of algorithm background, but he is a great computer geek. He was a gold medalist of IBO (International Biology Olympiad) 2014.
•  » » 7 years ago, # ^ |   +14 Interesting team name. Reminds me of the time I got a mail starting with Dear â€Ž(ã £à²¥ç›Šà²¥ï¼‰ã £ ï¸µ â”»â” â”», (please change your team name)
•  » » » 7 years ago, # ^ |   0 Our actual teamname is "ALREADY HAVE DONE", and the text is written in "full-width forms" (전각 문자). http://en.wikipedia.org/wiki/Halfwidth_and_fullwidth_forms It shows our effort to make our team's name listed on top :) but I soon found out that even my iPhone didn't displayed it properly.. (We all tested the teamname in Firefox.) I think the teamname will be changed right before the contest...
•  » » » » 7 years ago, # ^ |   0 It was the same when I got that mail, the original team name was an Epic Tableflip in Unicode. At least we changed the name to something with no less impact.
 » 7 years ago, # |   +6 Donkey Fly:
 » 7 years ago, # |   +3 Istrebitel:
 » 7 years ago, # |   +16 My Igloo Is Melting
 » 7 years ago, # |   +53 We have changed since last year, so our team name also have changed:unemployed, useless dropout & cute woman (vadimmm, Rubanenko, baba_beda)
 » 7 years ago, # |   +13 iThan: chaotic_iak, jonathanirvings, nathanajah (in alphabetical order of Codeforces handles, in alphabetical order of real names, in increasing rating order at the time of posting)Also known as the team of Indonesians that are not in Indonesia:
 » 7 years ago, # | ← Rev. 4 →   0 Team Name: shockers1) Ajay2) Sundar3) Karthik
•  » » 7 years ago, # ^ |   +13 You can link handles directly when writing comments (look for "User" in the comment box).
•  » » » 7 years ago, # ^ |   0 Cool I will do that from now.
 » 7 years ago, # |   +41 Please explain why havka eto papstvo:
 » 7 years ago, # |   +11 Team Name : 8-HD-720p-YIFY-Ganool.3gp Team Members : - azaky - farisv - makanbeling
 » 7 years ago, # |   0 DivineByCode amankedia Kanish_The_Vista ace_atul
 » 7 years ago, # |   +4 85-85:
 » 7 years ago, # | ← Rev. 5 →   +5 Team : 'hichzat' - bayram98 - horojyk - Kerim.K
 » 7 years ago, # |   -7 Sandor team: - SandorGarcia
 » 7 years ago, # |   +3 Never Slowdown
 » 7 years ago, # |   0 Team: Dodgers Members: vlade087, balle, deinier
 » 7 years ago, # |   0 Team: ☺ I can't see plus-plus ☺Member 1: tjandra Member 2: - Member 3: -
 » 7 years ago, # |   +19 Team : BajaBShayan Hosseiny ShayanHAmin Bahjati LostAli Asadi aliasadiiii
 » 7 years ago, # |   +3 Flawless:
 » 7 years ago, # |   -6 Binam:
 » 7 years ago, # |   0 dolphin secret agents - stan - acherepanov - permin
 » 7 years ago, # |   0 Chega de saudadesivanilos
 » 7 years ago, # |   0 sudo set-position rand()%N
 » 7 years ago, # |   0 ZER:
 » 7 years ago, # |   -7 Vypiem_za_Lubov
 » 7 years ago, # |   0 UHv6:
 » 7 years ago, # | ← Rev. 4 →   -6 Team: Король, мудак и ржавая запчастьMembers: accidentallygivenfuck, bayram and osmanussEDIT: Respectively xD EDIT2: BTW Google Translate is not accurate lol
 » 7 years ago, # |   +24 SPb SU 8/3 Dmitry_Egorov PavelKunyavskiy nk.karpov
•  » » 7 years ago, # ^ |   +17
•  » » » 7 years ago, # ^ |   +17 He will be not in St.Petersburg on that date.
 » 7 years ago, # |   0 I am looking for a Teammate. Anyone care to join me as team mate for the IPSC 2015?
 » 7 years ago, # |   0 Abdelkarim abdelkarim
•  » » 7 years ago, # ^ |   0 Hey, care to become my team member?
 » 7 years ago, # |   +3 DS & DP^2 besher DS Alex7 DP
 » 7 years ago, # |   +3 Alexander Udalov udalov
 » 7 years ago, # |   +16 Team MooOOoOooOOOOoOooooP:
•  » » 7 years ago, # ^ |   +8 are team names case sensitive? :P
•  » » 7 years ago, # ^ |   -8 can you tell me DemiGuo's facebook?
 » 7 years ago, # | ← Rev. 2 →   0 Team: ONU_Feuerbach - VVI - BronfenBova - illarionovam_onu
 » 7 years ago, # |   0 Team: j1k7_7 — j1k7_7
 » 7 years ago, # |   0 Team dpsd_teamrajat1603sidhantadditya1998
 » 7 years ago, # |   +2 If the list includes individuals(which it seems to), add me:Team name: Nalin Bhardwaj Member: Nalin Bhardwaj [me]Plus, if you decide to make divisions in teams, I'm in the secondary school division...
 » 7 years ago, # |   0 AOI2:
 » 7 years ago, # |   0 Team name : les apparences sont trompeuses members : Safrout KarimElSheikh MedoN11
 » 7 years ago, # |   0 Fast and Furious Transform: ed1d1a8d,Chilli,smurty
 » 7 years ago, # | ← Rev. 4 →   0 Primo:Manurungzulkan
 » 7 years ago, # |   0 Team bambino : 1. 2shraaf 2. Badry 3. mohamed.mehany
 » 7 years ago, # |   0 NHSPC Juniors 1. ruhan.habib39 2. tasmeemreza 3. rubabredwan
 » 7 years ago, # | ← Rev. 2 →   +2 KBTU Tarjan:
 » 7 years ago, # |   +10 Look at the past results. Team R+T+J wins only in even years :)
•  » » 7 years ago, # ^ |   +6 Oops!
 » 7 years ago, # |   0 kvark161:
 » 7 years ago, # |   +10 Dirsa how_to_become_purple Sanja Mishutnik
 » 7 years ago, # |   0 MSU Tashkent Old Coders
 » 7 years ago, # |   0 Team name : Samne Porikkha...Asen Contest KoriMembers :
 » 7 years ago, # |   0 Team "SPiromanii&Messi"
 » 7 years ago, # |   0 Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).
 » 7 years ago, # |   +16 Warsaw Capybaras: mnbvmar, Swistakk, Errichto
 » 7 years ago, # |   0
 » 7 years ago, # |   0 GG izi commend me
 » 7 years ago, # |   0 thehandofgod : belowthebelt deepankarak pulkit_180894
 » 7 years ago, # | ← Rev. 3 →   0 Team name : Hot Tomato SauceMembers : nirob_mh , shm0007
 » 7 years ago, # | ← Rev. 2 →   +8 Team "Nemidunam"     —   ArtinTD     —   Alimol
 » 7 years ago, # | ← Rev. 4 →   0 Team Name: Zerry2015Member: lamngo96, nhathuyen95, duongtnhat
 » 7 years ago, # |   +3 cup_of_team: cup_of_tea
 » 7 years ago, # |   +16 It seams to be good idea to put some hashsum with test generator. And also, where should i write it? I can't find any way to send question.
•  » » 7 years ago, # ^ |   +5 http://ipsc.ksp.sk/2015/announcements The practice session will start in an hour. Should you have any questions or clarification requests, e-mail them to ipscreg@ksp.sk. Alternately, you may use any instant messaging client that supports XMPP to talk to us at ipsc-org@swissjabber.org whenever the account is online – which will certainly be during the beginning of the practice session and also during the entire contest tomorrow.
•  » » 7 years ago, # ^ |   +21 Do open s2gen.py and take a look :)You may note that: The test generator computes a checksum internally We tried to avoid using anything that could make the generator platform-dependent (such as the internal "random" library which is not guaranteed to give the same output everywhere, even with a fixed seed). We considered publishing a separate shasum for the generated input but ultimately decided against it. The problem is that the generator will produce different end-of-line characters on different platforms, and thus we would need to publish multiple checksums... and that would be even more confusing for beginners. At the moment, we assume that the internal checksum will be sufficient.
•  » » » 7 years ago, # ^ |   +3 for me and many other participants don't have python compilers on windows (I use C++ to solve problems) , so I think adding C++ generators would be more convenient for many participants, please consider this suggestion
•  » » » » 7 years ago, # ^ |   0 You should install Cygwin instead.One of the points of IPSC seems to be not catering to everyone's computers.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +13 ... what?First of all, you definitely don't need Cygwin to run Python on Windows.Furthermore, Python is trivial to install (for Windows, there are also "portable" versions but requiring installation) and works on pretty much every OS and architecture.Considering that people use different OSs, IDEs and programming languages, a simple-to-use crossplatform scripting language might as well be the best choice for IPSC. How is this "not catering to everyone's computers"?
•  » » » » » » 7 years ago, # ^ |   0 you definitely don't need Cygwin to run Python on Windows I know, but that doesn't prevent me from suggesting installing it. Considering that people use different OSs, IDEs and programming languagesHow is this "not catering to everyone's computers"? You asked and answered the question in the same paragraph. People use different things, but IPSC doesn't set an "everyone uses this" standard (because it's false) or "let's cover all possible choices of what the contestants could use" (because it's ineffective), and lets people get what they need instead.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +5 Installing Python is not that hard.. And you have 1 practice day to do it.
 » 7 years ago, # |   +85 BTW, Xellos, thanks for translating your post to Russian, glad to know that those Russian-speaking people who do not speak English well can still have some fun at least reading your post about IPSC!
 » 7 years ago, # |   -6 Team Name : For the watch
•  » » 7 years ago, # ^ |   0 Why negative votes ???? Its just a team name.
•  » » » 7 years ago, # ^ |   +8 Maybe the people who have downvoted have started hating the night's watch after the finale :P
•  » » 7 years ago, # ^ |   +19 We had a semi-serious discussion whether to "kill" your team at some point during the contest :D
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +10 Even we had the same discussion considering our performance. =D
 » 7 years ago, # |   0 stigma: sugim48, evima, stqn
 » 7 years ago, # |   0 guptashvm: gupta_shvm
 » 7 years ago, # |   +10 My team:W4yneb0tW4yneb0t
 » 7 years ago, # |   +66 Knifeproof Tank
•  » » 7 years ago, # ^ |   +25 Lol, there's a team named "Sorry, tourist". In retrospect, they probably should've named themselves "Knife".
 » 7 years ago, # |   +1 TeamUFRNxyz222
 » 7 years ago, # |   0 Team BK.Troll: farmerboy thomas
 » 7 years ago, # |   +8 Ural FU Dandelion:- mpivko- Umqra- Um_nik
 » 7 years ago, # |   0 Team : code_phoenix
 » 7 years ago, # |   0 Andromeda-express: http://intro.andromeda-express.com/
 » 7 years ago, # |   +21 itmo150216:
 » 7 years ago, # |   +9 This is my first IPS . were will the problem statement appear ? :P
 » 7 years ago, # |   +8 what was the answer to J — juicy . com ?
•  » » 7 years ago, # ^ |   0 Just got the first one,Try typing an upper case "A" and guess by yourself, you're entering a philosopher school by the way
 » 7 years ago, # |   0 How to solve B hard :(
•  » » 7 years ago, # ^ |   0 I solved it using meet in the middle with complexity (m ^ 2 ) + (n * m * log(n)).Basically store all possible pairs from the first 2 strings in a vector array. Suppose ith string in 1st set has strength x[i] , and jth string in 2nd set has strength y[j] , then in the vector array , do -> V[x[i] + y[j]].insert ( pair (i , j) ) . Now after that use a set to keep track of the insults we have already used . Now for a query , suppose we want an insult of strength 'X' , so iterate over the 3rd set of strings , suppose the stength of the string is Z[i] . so now take any unused value from the vector V[X — Z[i]] if its available and mark it as used . Code -> http://ideone.com/ZQe7PF
•  » » » 7 years ago, # ^ |   0 I'm a little bit confused with the complexity. In the 50th line of your code, shouldn't the complexity be the size of v[strong - str3[i]]? And in the worst case, this size can be m^2 !! So, why not overall complexity is (m ^ 2 ) + (n * m * m^2)? Please explain.
 » 7 years ago, # | ← Rev. 2 →   +28 Team Name: ThankYouMikeMirzRAYanovForYouCodeforceAndPolygonPlatformsxxTastyHypeBeast666xxJoeyWheelerjunkbotI'm curious about how to solve H2 and M2
•  » » 7 years ago, # ^ |   +13 H2: First value is mincut, ans1 = M — maxflow. Second value is the difference between sum of degrees of vertices in first team and second. Solve knapsack problem to find minimum.
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 M2 was really interesting and I spent more time solving it than I should've (and I didn't finish it in time).0 is written as +[] and 1 is written as +!+[]. Enclosing a number in [] casts it into a string. Adding + before a string casts it to a number again.You solve the problem using dynamic programming. For each number, remember three strings:A) One that evaluates to the number itself: for 2, the shortest one is !+[]+!+[].B) Same as A), but can be treated as "in brackets", meaning that you can multiply with it. For 2, this is +[!+[]+!+[]].C) A literal string value, for 2 (or '2', rather), this is [!+[]+!+[]].Iterate through the numbers in ascending order. When you reach number N, try to minimize the length of each of the three fields by casting between them as described above. Now for the DP part. If you know numbers from 0 to N, you can construct things with three operations: Add numbers using +. You don't need the "in-brackets" version of these. Multiply numbers with *, being careful to use bracket versions. Concat string literals using +, for example to create "10" from "1" and "0". Of course, for each number remember the shortest string you made. After this, make another pass, trying to subtract the numbers from each other to get shorter strings. If I'm not mistaken this should be enough to fit into the limit.
 » 7 years ago, # |   0 couldn't get G2 accepted because of stack-overflow >_<
•  » » 7 years ago, # ^ |   +5 ulimit -s UNLIMITED?
•  » » » 7 years ago, # ^ |   0 hmmm i don't know what that is :(
•  » » » 7 years ago, # ^ |   0 ulimit -s UNLIMITED bash: ulimit: UNLIMITED: invalid number 
•  » » » » 7 years ago, # ^ |   +10 Lowercase needed :P
•  » » 7 years ago, # ^ |   0 I wrote dfs non-recursive :-)
•  » » » 7 years ago, # ^ |   0 i didn't have much time to correct it sadly...
 » 7 years ago, # |   +5 Wow, we beat both Petr team and tourist team :D! And even fact that I and Errichto started one hour delayed didn't stop us :D.Can anyone tell me, why output in I is so small (~20 points at most)? My code runs in , so I didn't know whether it will TLE or not, because a priori I couldn't give any good estimation for output, so it made me very happy that it is so small :P.
•  » » 7 years ago, # ^ |   +17 I think that reason for small output doesn't exist since it can be huge (O(m) or O(n) at least), but I just discovered this sentence in a statement "Note that the implementation of this generator might matter." and it was completely randomized, so I guess this was fully intended :P.
 » 7 years ago, # |   +5 Does anyone know how to solve J2 task?I tried to do some kind of dsbox-debug magic, but failed. I can only get this message "Verifying license information... OK", but this doesn't help me
•  » » 7 years ago, # ^ |   +13 All solutions are here http://ipsc.ksp.sk/2015/real/solutions/booklet.pdfBut I would still like to hear how the teams approached this problem — what was the solving process like.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +5 I solved it as described with a "few" differences — had to download dosbox to run it, had only knowledge of Z80A assembler, so had to decrypt it. But it was the most interesting problem I solved today :) I liked the idea in J2 that "hackers" spoiled bytes which were really needed for the program to run properly. It reminded me about early 1990s and breaking copy protection in ZX Spectrum — good old days :)upd: Disassembler I found online was working in AT&T notation. It did add a lot of confustion at first. :)
•  » » » 7 years ago, # ^ |   0 I solved it several minutes after the contest end. Just disassembled it with ndisasm, and was running it in DosBox after making changes. Regular ndisasm that comes with nasm in Ubuntu was able to disassemble it just fine.
•  » » » 7 years ago, # ^ |   +8 For me the process is less exciting, I did something like "loading them in IDA Pro, staring at the code for minutes, and solve"...
 » 7 years ago, # | ← Rev. 2 →   +5 Spent a lot of time by solving M1 — we missed that we can create strings without ". Essentially, we tried to obtain numbers by considering their binary notations by having 2 operations — multiplying by 2 and adding 1. The naive approach resulted in too many characters (about 280), so we had to do some optimizations: Adding 1 adds parenthesis. Parenthesis is a lot of characters. So, instead for every long (>= X) group of consecutive 1s instead of adding 1 at every single bit (0111111) we add 1 in previous bit and then subtract 1 at the end of the group (100000[-1]). Sometimes, considering two digits at the same time is better, since multiplying by 4 is shorter than multiplying by 2 two times. So, at every stage, consider two bits and see how much do you need to add/subtract. Is small enough (<= Y), then process 2 bits at once. Consider every possible values of X and Y and pick the shortest result. After that, observe that if we have numbers A and B, then we can obtain A with B.size() + 5 * abs(A-B) (by adding +/-1), which can be smaller than A.size() and get us below 200. After all of this, I had one number left which I couldn't get under 200 characters, but we had two people optimizing this and that specific string was below 200 in other implementation. So, yeah, definitely feel like this is a huge (although impressive, imho) overkill and we should've dropped it at some point and instead do something else, which would've been better, but this was quite fun, and fun is what IPSC is about. Thanks to the organizers for yet another wonderful contest!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +23 The binary thing worked for me without any problems. My solution was as follows: S(0) = +![] S(1) = +!![] S(2n) = [S(n)]*+[+!![]+!![]] S(2n+1) = S(2n)+!![] And everything fit into something like 189 or 190 characters.
•  » » » 7 years ago, # ^ |   0 Oh, thanks. You are using [x] to encapsulate x. We used [x][+[]].
 » 7 years ago, # |   +98 This contest was definitely not intended for a 1-person team, I didn't even get around to reading all the tasks :(It was fun anyway :)
 » 7 years ago, # |   0 How did you solve B2 (the hard input) ? Weren't the constraints too high? Even binary search didn't seem to help much .
•  » » 7 years ago, # ^ |   0 Store all possible sums of the 2nd and 3rd type of words in arr[] and sort it. By iterating i (each word of 1st type), binary search for total-V1[i] in arr[]. O(m^2)+O(n*m*log(m^2)) Take care that the same combination of words doesn't get repeated by incrementing inc[i][z] (i-index of 1st type of word, z-lowerbound of total-V1[i]) Took about 20 sec to get the solution. There must be a better solution.
 » 7 years ago, # | ← Rev. 2 →   +42 Very nice problemset! I have to admit that I especially enjoyed problem I (however coming up with that trolling observation in H about degrees and knapsack was also satisfying :P). Though I have to admit that I don't find model solution very insightful and fair :P. For those who didn't read booklet — organizers mentioned in statement that implementation of generator of big test may matter and it turned out that generated graph was surprisingly always DAG and model solution took a big advantage of that fact. Existence of solutions without assuming graph being DAG makes this sound like a lame excuse for organizers for not being able to solve their own problems :D. However as I mentioned above in that thread — I also took advantage of fact that this generator involves randomness (but I think that organizers also assumed this and I think that this may not be solvable in a reasonable time manner without it).Here is a sketch of my solution. We consider function T(p) which for particular p denotes length of a shortest path. We know that this function is convex and partially linear. What we need to find are points where this functions bends. What is crucial is that we can easily evaluate T(p) and its derivative for a fixed p just by running one simple Dijkstra (derivative is obviously summed for edges on a shortest path).We want to determine intervals on which our function is linear. Assume that we are given xl and xr which are points belonging to different intervals and that we already evaluated our function there. So we are given two lines denoting graph of T on those intervals. Let their intersection be (xm, ym). Evaluate T in xm. If it turns out to be ym then we know that those two intervals are adjacent and that xm is a point we should print. If not then we just discovered a point on an interval we weren't aware of and we should recursively call for (xl, xm) and (xm, xr) :). That is everything. Complexity of this solution is clearly dominated by running Dijkstra and we need to do this O(size of output) times. But since tests are random then size of output is very small. It didn't exceed 25 on given tests. So it is definitely a reasonable time :).
 » 7 years ago, # |   +26 Hi Xellos, would you add final standings (rank) on the team list in this blog? I think it would be nice :)
 » 7 years ago, # |   0 What would be the optimal time complexity for solving F hard?I used Union-Find along with some stl maps to get a time complexity of q*logn*logn, and the hard data-set ran in ~15 sec. on my PC.Any faster solution?
•  » » 7 years ago, # ^ |   +10 Quoting Coder "All solutions are here http://ipsc.ksp.sk/2015/real/solutions/booklet.pdf" Btw — there is anything wrong with solution running 15s on a contest where you're allowed to run it for 3h :P.
•  » » » 7 years ago, # ^ |   0 Thanks for the link, seems like it is quite similar to my solution :)I asked because i was curious to know how to remove the extra log(n) factor in time complexity
•  » » 7 years ago, # ^ |   0 can you explain your solution a little or post the source code for F hard?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 It is the same as explained in editorial. You can check from there.
 » 7 years ago, # |   +58 For me it is quite surprising that so many teams have solved J (at least J1). How have you come up with idea? Have you used disassembling or just played with executable?
•  » » 7 years ago, # ^ |   0 At least 30 people are still curious :)
•  » » 7 years ago, # ^ |   +5 It was quite easy to figure out what the file is (I knew it, but you could also google it or something).Then it's natural to see how it works. I remembered that one needs something like DOSBox to run 16-bit executables on Linux/64-bit Windows, so I installed it and ran the program. And when you see the program terminates after the first incorrect character, you immediately know what to do :)
•  » » 7 years ago, # ^ |   +17 I am closer to dinosaurs, having started programming back in 1990-ies, so I knew what the COM file is, that it is simple binary and starts executing from first byte on.I remember when F00F bug was discovered I was smart enough to show my friends how it works just by typing these four bytes in hex editor, renaming it into com and running — so back at that time, around 14 y.o. I knew how .com files work.Thing I didn't know is that it is loaded not starting from 0x0000, but starting from 0x0100, so all addresses were shifted by 256. It added confusion, but I figures it out.Noting that Windows 7 doesn't just run com files anymore, I downloaded DosBox. To be fair, J1 can be guessed — letter by letter, which is tedious, but after guessing Ari... you can guess that it must be somebody from the same epoch as Pythagoras.I used same online disassembler which Petr mentioned in his comment. I didn't have experience with i8086 assembler, but I did a lot of programming in Z80 assembler, so it was not too difficult to figure out apart from sad fact that online disassembler showed code in AT&T notation, not Intel notation. For those who don't know, in AT&T notation all operands are reversed, so MOV A, B moves A->B, while more natural to me was Intel notation, which is reverse. It puzzled me for another ten minutes.Then it gets easy with J2 — after you figure out the logic.I would say that this problem suited and was liked by two types of people programming dinosaurs, who started programming in 80-ies and early 90-ies real hackers, those who work with binaries writing nasty viruses working on top of operating system, cracking iOS releases and breaking game copy protection (and those fighting them), or those working with low-level micro controllers code and good with assembler. There was barely any algorithmic skill required, but I think from diversity point of view it was good. The chess problem also didn't require any algorithmic skill, but was fun to solve. And was very good for diversity. My understanding is that diversity of problems is one of IPSC trademarks.
•  » » » 7 years ago, # ^ |   +5 My understanding is that diversity of problems is one of IPSC trademarks. That's why we LOVE IPSC contests :)
 » 7 years ago, # |   0 When IPSC 2015 will be added to the Training Area?
•  » » 7 years ago, # ^ |   0 Mailing the organisers would be more productive than writing it here. But the inputs and outputs are already published, it's not hard to test your solution locally.