Следующий тур Интернетовского Соревнования Решения Задач (Internet Problem Solving Contest) приблизиться!
Задачи на IPSC имеют различные форматы, от стандартных алгоритмических до задач для взаимодействия с грейдером или поиска конкретного входа. Все задачи суть по английски.
Большинство задач иметь легкий вход (стоимость: 1 очко) и трудный вход (стоимость: 2 очки); положение вычислено как на ACM, только неправильный ответ на легкий вход дает пенальти 10 минут — не 20. Входные файлы доступны для скачивания перед соревнованием и вы только посылаете ваше выходное файлы (как на GCJ, только никакие дальше ограничение по времени нет).
Это есть соревнование для команд трех или менее людей. IPSC 2015 происходит 20го июня, от 11:00 UTC до 16:00 UTC. Регистрация доступна здесь.
СОРЕВНОВАНИЕ ЗАКОНЧЕНО!
| Зарегистрированние командьи для хендлов CF |
|---|
(если хотите вашу команду иметь добавленную здесь, напишите мне как-то или напишите название вашего команда и его состав в комментарии, но добавлена будет только по окончании соревнования)
| Место | Очков | Минут | Название команда | Членr 1 | Член 2 | Член 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 | Konijntje | 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 | sivukhin | 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 |
| 167 | 15 | 1042 | kraskevich_team | kraskevich | ||
| 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 |
| 366 | 10 | 1348 | Choker | riad | LinKin | jehad131 |
| 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 |
Anyone interested in posting team members here?
I'll go first:
Zenith:
(members are sorted in reversed alphabetical order).
Mhm, I'll make a table.
Dig:
(members are sorted in
reversedalphabetical order).In other words, in reversed reversed alphabetical order? :D
Bangladesh Avengers
Sorry guys due to some troubles we have changed the team please enter this instead
sorry_helli
(O) SaDDaS
(O) Reyna
(O) IloveGoodness
However they are sorted by rating (increasing).
please change the team Xellos
WTF? Everyone here knows that IloveGoodness is xtrome's fake handle and it's banned by administrators.
:| well he has to have at least one id
Well I didn't know. Time to make it more known (see edit history).
We're gossiping like housewives, dammit.
Choker : riad vai , LinKin , jehad131
12.0ngskar
If anybody need one more participant, I would like to join.
Tmcoteam:
The Deterministics:
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.
You should ask Sereja to join your team. He won't let it happen again :)
Team name: 2017 ACM ICPC absolute winners
participant №1 : T0RRES
participant №2 : ------------
participant №3 : ------------
Team Zabava
Hey Xellos, thanks for posting this! :)
We certainly have some fun problems in store for this year as well. Don't miss out!
Corridors of Time
Looking forward to some more "OMGPROVINGITISADISASTER" problem (like 2014G) :)
GD-PSP
- Jokser
- sweiss
- pvasilyev
Return of Celtic Warriors : Tanaeem , _sunny, dragoon
namelist.insert("দৌড়ের উপর"): enzam , VUAcoder , wasi.ahmed
Havka-papstvo:
What is the story behind your team's name?
Havka — papstvo, m'kay?
http://www.youtube.com/watch?v=hxHKGV4LY34
I didn't think that targets ever get high! Thanks for the video))
What is the english translation? I think I have the general idea :P
Saratov SU 1:
kuviman IlyaLos danilka.pro
Unpretired:
B-b-b-b-bones!
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
PAPFans:
M.Mahdi
PAP himself! :D
SeyedParsa
what???
change that team name please!!
sorry_PAP! :D
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 :)
Team: " Masr Islamia (╥‿╥) "
Members: KhaledKEE, ahmednaoum, Mohamed Al-Jamal.
Please write "br" to pass newline.
hmmm let me try br br br br br hmm br???? :o it doesn't work
Read about it here.
Too lazy to find a palm face picture.
Whatever:
ikbal
EMINAYAR
enesoncu
CodeFights:
Frozen Heart:
Team
ꓮꓡꓣꓰꓮꓓꓬ ꓧꓮꓦꓰ ꓓꓳꓠꓰ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.
Interesting team name. Reminds me of the time I got a mail starting with
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...
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.
Donkey Fly:
Istrebitel:
My Igloo Is Melting
We have changed since last year, so our team name also have changed:
unemployed, useless dropout & cute woman
(vadimmm, Rubanenko, baba_beda)
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:
Team Name: shockers
1) Ajay
2) Sundar
3) Karthik
You can link handles directly when writing comments (look for "User" in the comment box).
Cool I will do that from now.
Please explain why havka eto papstvo:
Team Name : 8-HD-720p-YIFY-Ganool.3gp
Team Members :
- azaky
- farisv
- makanbeling
kraskevich_team
kraskevich
85-85:
farzad.shbfn
shamir0xe
Team : 'hichzat'
- bayram98
- horojyk
- Kerim.K
Sandor team: - SandorGarcia
Never Slowdown
Team: Dodgers
Members: vlade087, balle, deinier
Team: ☺ I can't see plus-plus ☺
Member 1: tjandra
Member 2: -
Member 3: -
Team : BajaB
Shayan Hosseiny ShayanH
Amin Bahjati Lost
Ali Asadi aliasadiiii
Flawless:
Binam:
dolphin secret agents - stan - acherepanov - permin
Chega de saudades
ivanilos
sudo set-position rand()%N
Vypiem_za_Lubov
UHv6:
Team: Король, мудак и ржавая запчасть
Members: accidentallygivenfuck, bayram and osmanuss
EDIT: Respectively xD EDIT2: BTW Google Translate is not accurate lol
SPb SU 8/3 Dmitry_Egorov PavelKunyavskiy nk.karpov
yeputons ?
He will be not in St.Petersburg on that date.
Abdelkarim abdelkarim
DS & DP^2
besher DS
Alex7 DP
RedNextCentury DP
Alexander Udalov udalov
Team MooOOoOooOOOOoOooooP:
are team names case sensitive? :P
Team: ONU_Feuerbach - VVI - BronfenBova - illarionovam_onu
Team: j1k7_7 — j1k7_7
Team dpsd_team
rajat1603
sidhant
additya1998
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...
AOI2:
Team name : les apparences sont trompeuses members : Safrout KarimElSheikh MedoN11
Fast and Furious Transform: ed1d1a8d,Chilli,smurty
Team bambino : 1. 2shraaf 2. Badry 3. mohamed.mehany
NHSPC Juniors 1. ruhan.habib39 2. tasmeemreza 3. rubabredwan
KBTU Tarjan:
Look at the past results. Team R+T+J wins only in even years :)
Oops!
kvark161:
Dirsa
MSU Tashkent Old Coders
Team name : Samne Porikkha...Asen Contest Kori
Members :
Team "SPiromanii&Messi"
patrick.sava teoionescu george_stelian
Auto comment: topic has been updated by Xellos (previous revision, new revision, compare).
Warsaw Capybaras: mnbvmar, Swistakk, Errichto
milkyway ptnk_1215_panaka_13 touristv2 TiChuot97
GG izi commend me
jlr.terceiro
ronisds
thehandofgod : belowthebelt deepankarak pulkit_180894
Team name : Hot Tomato Sauce
Members : nirob_mh , shm0007
Team "Nemidunam"
— ArtinTD
— Alimol
cup_of_team: cup_of_tea
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.
http://ipsc.ksp.sk/2015/announcements
Do open s2gen.py and take a look :)
You may note that:
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.
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
You should install Cygwin instead.
One of the points of IPSC seems to be not catering to everyone's computers.
... 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"?
I know, but that doesn't prevent me from suggesting installing it.
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.
Installing Python is not that hard.. And you have 1 practice day to do it.
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!
Жми стрелочку вверх если ждёшь не дождёшься 20 июня, чтобы поскорее
повзаимодействовать с грейдероми поискатьконкретный входTeam Name : For the watch
Why negative votes ???? Its just a team name.
Maybe the people who have downvoted have started hating the night's watch after the finale :P
We had a semi-serious discussion whether to "kill" your team at some point during the contest :D
Even we had the same discussion considering our performance. =D
stigma: sugim48, evima, stqn
guptashvm: gupta_shvm
My team:
W4yneb0t
W4yneb0t
Knifeproof Tank
niyaznigmatul, VArtem, tourist
Lol, there's a team named "Sorry, tourist". In retrospect, they probably should've named themselves "Knife".
TeamUFRN
xyz222
Zailton
RailtonT
Team BK.Troll: farmerboy thomas
Ural FU Dandelion:
- mpivko
- sivukhin
- Um_nik
Team : code_phoenix
ajinkya1p3
yogeshg39
InnocentFool
Andromeda-express:
http://intro.andromeda-express.com/
itmo150216:
This is my first IPS . were will the problem statement appear ? :P
what was the answer to J — juicy . com ?
Just got the first one,
Try typing an upper case "A" and guess by yourself, you're entering a philosopher school by the way
How to solve B hard :(
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
Team Name: ThankYouMikeMirzRAYanovForYouCodeforceAndPolygonPlatforms
xxTastyHypeBeast666xx
JoeyWheeler
junkbot
I'm curious about how to solve H2 and M2
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.
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:
+. You don't need the "in-brackets" version of these.*, being careful to use bracket versions.+, 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.
couldn't get G2 accepted because of stack-overflow >_<
ulimit -s UNLIMITED
?
hmmm i don't know what that is :(
Lowercase needed :P
I wrote dfs non-recursive :-)
i didn't have much time to correct it sadly...
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.
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.
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
All solutions are here http://ipsc.ksp.sk/2015/real/solutions/booklet.pdf
But I would still like to hear how the teams approached this problem — what was the solving process like.
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. :)
I solved it several minutes after the contest end. Just disassembled it with
ndisasm, and was running it inDosBoxafter making changes. Regularndisasmthat comes withnasmin Ubuntu was able to disassemble it just fine.For me the process is less exciting, I did something like "loading them in IDA Pro, staring at the code for minutes, and solve"...
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:B.size() + 5 * abs(A-B)(by adding +/-1), which can be smaller thanA.size()and get us below 200.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!
The binary thing worked for me without any problems. My solution was as follows:
And everything fit into something like 189 or 190 characters.
Oh, thanks. You are using
[x]to encapsulatex. We used[x][+[]].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 :)
How did you solve B2 (the hard input) ? Weren't the constraints too high? Even binary search didn't seem to help much .
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.
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 :).
Hi Xellos, would you add final standings (rank) on the team list in this blog?
I think it would be nice :)
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?
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.
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
can you explain your solution a little or post the source code for F hard?
It is the same as explained in editorial. You can check from there.
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?
At least 30 people are still curious :)
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 :)
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
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.
That's why we LOVE IPSC contests :)
When IPSC 2015 will be added to the Training Area?
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.