### kostka's blog

By kostka, 4 months ago,

In Sharm El Sheikh. It was announced on the stream.

• +113

 » 4 months ago, # | ← Rev. 2 →   +185 Personal note: What the bloody hell? Will all the teams have to pay \$2500 to stay in ridiculously expensive hotels? Is this another cash grab by ICPC?
•  » » 4 months ago, # ^ |   +126 Yet, every year, the Egyptian informatics teams make blogs asking for funding because their own people wont even give them the (relatively insignificant) amount of money needed to participate in IOI, EGOI, etc.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +22 Not to mention that they are scheduled to organize IOI in 2024 as well.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +41 As an Egyptian, I can't tell you how much I am embarrassed because of the decisions my organizers take, and the incompetency of some people in charge over here.
•  » » 4 months ago, # ^ |   +12 What do you mean? Do teams have to pay? I thought hotels are covered by ICPC (based on my experience).
•  » » » 4 months ago, # ^ |   -10 Hotels aren't covered for regional participants in Egypt, hopefully they'll cover hotels for the WF though. No official information on this yet as far as I know.
•  » » » » 4 months ago, # ^ |   +35 In my experience, hotels were always covered at the finals, I don't understand why this could be different next year (at the same, regional contests are different and the hotels are not covered).
 » 4 months ago, # |   +38 LOL, All the Arabs participate in the ICPC to getout from the Arab World and now it will host in Egypt , I mean what the hell
 » 4 months ago, # |   +22 You better start saving some money to participate.
 » 4 months ago, # |   +88 oh no
 » 4 months ago, # |   +95 What the ....ICPC is like : let's merge and host our two ICPCs in the region with the shittiest organizers.
 » 4 months ago, # |   0 Link to official announcement?
•  » » 4 months ago, # ^ |   0 It was announced during the last World Finals (Dhaka): link.
 » 4 months ago, # |   +20 How you guys liked this year dhaka world final arranged by bangladesh? I just asking out of curiosity.
•  » » 4 months ago, # ^ |   +130 I thought they did a great job organizing it. The volunteers from Asia Pacific were super kind and thoughtful. They had ICPC posters on practically every single streetlight for miles, and held events in 3 different halls, with much of the main contest hall essentially built within a few days.That said, personally I did have some safety concerns with just the way transportation works in general there. Roads rarely have lane lines, traffic rules are essentially "if you think you'll fit, step on the gas", and the amount of time it takes to get somewhere is essentially inversely proportional to how aggressive of a driver you are, with what felt like no limit. Unlike Porto and Moscow, I didn't feel inclined to tour the city or go for morning runs, and unfortunately if you were in a different hotel from the contestants, it was difficult to spend much time with them. The hotels were far apart and transportation was difficult, scary, and [imo] necessary.
•  » » 4 months ago, # ^ |   +107 I thought almost everything was good : hotel, organization, contest, food... The only problem I had was that we didn't have a single opportunity to visit the city. I find it quite sad to take the plane and travel to the other side of the planet just for a programming competition I could've done at home. On the other hand in Moscow we could visit pretty much every day which was great.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +3 If you had the opportunity or time to visit the city, you would have become very disappointed. The commuting time here in BD is very high. If the event were to be held outside dhaka near some tourist spots like Cox Bazar you guys might have some more fun. But it's really sad. So many talents came in our country but couldn't see anything special.
•  » » 4 months ago, # ^ |   +86 Honestly, I loved it! Comparing the Moscow finals and the Dhaka one, the former looks just half-assed (although I guess it's understandable given that icpc was willing to spend around the same amount of money). It felt like the organizers put their heart and soul into the event. I loved the concert with the local bands. The convention centre for the event was convenient enough (albeit missing wifi at times, which is a pretty minor issue :) ). Loved how passionate and hospitable the volunteers were, big props to them!We explored the hotel surroundings for a couple of evenings, and that experience was truly priceless. I won't forget the traffic on the roads for a long time. Found a cute park nearby, went to a mall, to a market and to the poor area across the river :grimacing: Shocking but unique experience. I agree with nweeks that I wish we had more free time to explore, but at least we did have enough time to socialize. Was very happy to finally meet up with my online friends :ghosthug:I'm out of attempts at this point, but these finals really made me wanna become a coach and attend some finals in the future in that role :)
•  » » 4 months ago, # ^ |   +69 Good: You can meet online friends. The event was well organized, especially if you consider the number of people. The covid-testing system was smooth. There were no issues with food and transport. It shows that the organizers are very experienced.Bad:1) Volunteers at the airport were the opposite of helpful. They kept telling everybody to "wait here", e.g. standing in the visa-on-arrival queues even if somebody didn't need it. I think that they actually didn't speak English. Departure from the hotel was bad too.2) As always, extremely boring opening & closing speeches.3) Loud traffic, audible even in a hotel room.Neutral: It's a huge and expensive event where you stay at 5-star hotels. The splendor is arguably unnecessary.
•  » » 4 months ago, # ^ |   +97 Pros: The hotel we were in (Sheraton Dhaka) is honestly one of the best I've ever stayed at. The food served in the hotel is 10/10, the food served at the contest sites maybe 7/10, but overall, the food was more than alright. It is my first ICPCWF, so I was pretty amazed by the size of the event overall -- including the posters around the city, different halls it has been organized in, and generally the number of people, including volunteers, that were there to make this event as good as it was. The judge system (DOMJudge). It just worked flawlessly for the entire duration of the contest. Volunteers (apart from the ones at the airport), were very kind and respective, and they solved most of the queries we had. Cons: Dhaka traffic. Honestly, I don't have a single good word to say about the buses that we have been driving around in, as well as for the overall state of the traffic. I know that this is not something ICPC can change, but they might take that into account while deciding where to organize the WF. Also, we did not get to explore the city at all, mostly as we had really no free time apart from the night time where the streets didn't look that safe. Arriving to Dhaka. The volunteers were opposite of useful, giving wrong information, making us wait in the queues we weren't really supposed to wait in, and their way of collecting the passports is, in easiest words, a bit shady. Also, leading us through the airport and finding our luggage was also something else. The funniest thing is that the volunteers, after a horrible services, asked for tips for their help throughout the airport. The contest itself honestly, there were just too many flaws for a competition that is that prestigious (it kinda lowers the value of all the organisation around it). In my opinion, there were $9$ problems that were doable by any decent team and the only thing making the difference is the speed -- which is not bad on its own, but what makes it bad is that most of the teams wasted lots of their time on one of the three non-minor flaws that the problems had: Problem B: the complexity thing is just something that shouldn't be present at a WF -- if all the teams knew that the problem is solvable in $\mathcal{O}(QN)$, I bet that the number of solves would have at least been twice as high. The complexity needed to solve the problem should be easy to extract from the constraints, unless it's one of the problems where that is not the case (where that bit is actually the key of the problem). Many teams I've talked to were thinking of a better solution that the one that actually passes, which basically made them waste much more time (and maybe not solve the problem at all). Problem G: we luckily didn't fall into this pit, but the important statement change was awfully announced to all the contestants. One more thing that must not happen at that high level. Problem J: I don't know how many people fell here, but the samples with the statement combined is like if someone tried to intentionally screw with some teams, I have no other explanation for that. The speeches. It's insane how long and boring they were, in my honest opinion. That, along with some other stuff, made the 'whole day at the contest site', instead of giving us some more time to rest in the hotel, which I think that most of the contestants would have preferred.
•  » » 4 months ago, # ^ |   +93 Good: The volunteers, which were very helpful. Some other participants write that the ones at the airport were the opposite of that, but I didn't see anything wrong with them. Maybe we arrived at different times, and they were unfortunate to get bad volunteers? The concert on 7th — it was simply amazing. I've never been to concerts before, and this was one of the best events in my life A lot of opportunities to socialize with the other teams and staff Hotels — they were very good, and the food selection was just flawless (although it didn't stop me from going to the local KFC just to try it out) Huawei Challenge — in my opinion, this one was far more interesting than the strange neural network training in Porto Chill zone with more opportunities to socialize/play/solve some Kotlin tasks from JetBrains. The only thing that I felt missing is some big quest related to programming, like the way a Yandex Quest is organized during NERC — but I doubt we would have enough time to do that Bad, but impossible to fix from the organizers' point of view: Traffic — it's just a giant clusterf**k, and I was almost run over by a vehicle twice Bad and could be fixed, in increasing order of significance: Lack of sockets, especially in the hall where we wait for the contest and in the spectator zone during the contest itself PCR testing. I think the medic at Renaissance was just sadistic, it almost felt as if he was trying to reach my brain through the nose with the medical equipment. At least the queues for testing were very short, unlike in Moscow The contest itself (spoiler alert for those who are going to solve it, I will discuss the details of some problems): SpoilerI didn't participate in it (I am a coach), but I really think that it was far from being the real World Finals contest. Problem H should not have been there at all (I do think that classical problems are acceptable, but only if they are very easy warm-up problems, like A at Morocco World Finals — and this H was far from being a warm-up problem). The issue in problem G was handled very poorly, and the problem itself is very meh (it's a problem on just some specific knowledge that requires zero thinking and very difficult if you don't know 2D FFT or substring search with wildcards). There were also TL issues in problem B Incredibly long speeches during the Opening/Closing Ceremony, which even lead to them not fitting in the schedule Mohamed Fouad. At least he wasn't as prevalent as during the Moscow World Finals Overall, it was a very nice experience for me, despite the not-so-short list of things I didn't like (some of them weren't really significant).
•  » » » 4 months ago, # ^ |   +37 +1 for Fouad lol, why give such elevated speeches just to let this guy on the stage so he can scream and wave his hands like we are all retardedalso, after 1.5h or so of speeches, asking ARE YOU READY for the fifth time felt like he was doing it on purpose xd
•  » » » » 4 months ago, # ^ |   +55 If you didn't tune in to the ICPC Live stream, there are some highlights. For example...
•  » » » 4 months ago, # ^ |   +3 We solved the problem $G$ using only bitsets (we participated in the mirror), and I listened to 2D FFT solution from my friend and was surprised :)So, The problem has a solution in which you don't need some knowledge about 2D FFT :)
•  » » » » 4 months ago, # ^ |   +3 Whaaaaaat. And my team has told me that their FFT solution worked very close to TL (despite their TRD FFT implementation being very efficient).
•  » » » » » 4 months ago, # ^ |   +13 Two points: The two-dimensional FFT is not necessary in this problem. I am not even sure that 2D FFT would be faster in this problem by any significant degree. Usually, you can't replace 2D FFT by normal, one-dimensional FFT without some padding that increases the size of the problem by several times. However, in this problem, no non-trivial padding is required. Did your team make a logarithmic number of polynomial multiplications / FFT calls by any chance? I am pretty sure that the intended solution uses either exactly one complex polynomial multiplication, or 1-2 multiplications done modulo a FFT-friendly prime.
•  » » » » » » 4 months ago, # ^ |   +3 What a true 2D FFT even is? I always thought that all natural formulations of 2D FFT-like problems are easily reducible to 1D (by putting $m_1-m_2$ zeros between each pair of rows when flattening the pattern matrix, where $m_1$ and $m_2$ are widths of text and pattern matrices).
•  » » » » » » » 4 months ago, # ^ |   +3 Given $P(x, y) = \sum_i\sum_j a_{i,j}x^iy^j$, return the table of $(i, j)\mapsto P(\omega^i, \omega^j)$, where $\omega$ is the $n$-th root
•  » » » » » » 4 months ago, # ^ |   +3 If you do 2D FFT of an $n\times n$ array by doing $2n$ 1D FFTs (one for each row and then one for each column), then it seems to work in about the same time as a 1D FFT. I may have even verified it in the past, but not entirely sure
•  » » » » » » 4 months ago, # ^ |   +4 We are that team, and yeah, I guess our solution is slightly slower than what authors intended. We did 3 1D complex-valued multiplications (6 convolutions), while calculating $s \cdot t^3 - 2 \cdot s^2 \cdot t^2 + s^3 \cdot t$.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   +4 Have tried bitset but couldn't passed the TimeLimit. Can you share how do you handle with bitset? Did you use bitset lib or just pure bitwise operation?
•  » » » » » 4 months ago, # ^ |   +15 First, let's denote the size of the first matrix with $h × w$, and the size of the second as with $H × W$. Let's denote the number of different colors in the first matrix as $C$.For each color $c$ which occurs at least once in the first matrix, let's do the following thing: For each row in both matrices let's keep a bitset of the color $c$. More formal: $bitset_x[i][j] = (mat_x[i][j] == c)$, where $1 \leq x \leq 2$ (first or second matrix), $i$ is for rows, $j$ is for columns. Let's iterate the position in the second matrix, where we want to check whether it's possible to put the first matrix on it. There is $(H - h + 1) × (W - w + 1)$ valid positions. So, now we need to understand how to check it using precalculated bitsets. We can iterate over $h$ and for each row check whether it's valid for the following color or not (this part is easy, so I will let it as an exercise, two operations on bitset) After all of this, we get the solution with complexity $O(\frac{C(H - h + 1)(W - w + 1)hW}{64})$. This is a little bit slow, so we should understand how to do it a little bit faster.Let's understand that we can reduce the number of valid positions where we should check correctness to $\frac{(H - h + 1)(W - w + 1)}{C}$. How to do this? Initially, for each color $c$ you can take one field from the first matrix (where $mat_1[pos_x][pos_y]=c$) and for that $pox_x, pos_y$ find all the positions in the second matrix that the field in the position $pos_x, pos_y$ will be correct. Since it should be correct for each color, so you need to take the intersection of the positions of all colors or you can take the minimal one (since it's guaranteed is at most $\frac{(H - h + 1)(W - w + 1)}{C}$).So, the final complexity of the solution will be $O(\frac{(H - h + 1)(W - w + 1)}{C} × C × \frac{hW}{64})$=$O(\frac{(H - h + 1)(W - w + 1)hW}{64})$
•  » » » » » » 4 months ago, # ^ |   +9 Thanks _LeMur_ for very clever reducing positions method. I got all the idea!
•  » » » » » 4 months ago, # ^ |   +5 SnapDragon's judge solution uses bitsets too, for reference.Tangentially, I had access to all judge solutions prior to preparing the solution video for G and decided to go the route of presenting only the 1D FFT solution. I don't have particularly strong opinions about the existence of a bitset solution among the intended solutions, since this problem isn't entirely original. It was not intended to AC with 7 convolutions, so maybe it's fitting that it was also possible to AC without knowledge of FFT yet again.
•  » » » » » » 4 months ago, # ^ |   +12 Thanks xiaowuc1! Do you know where can upsolve again WF final this year or when testcase are shared?. Because the mirror constest has ended.
•  » » » » » » » 4 months ago, # ^ |   +12 When I talked with the Kattis folks, they said they would try to have it uploaded within a week.It has been roughly a week and they are not uploaded yet to my knowledge, but I know many folks are still recovering and I have heard no updated estimate for when they will be uploaded. I would hope in the next week but the Kattis folks may be busy getting other regional contests up and running...