kostka's blog

By kostka, 3 months ago, In English

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

 
 
 
 
  • Vote: I like it
  • +113
  • Vote: I do not like it

»
3 months ago, # |
Rev. 2   Vote: I like it +185 Vote: I do not like it

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?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +126 Vote: I do not like it

    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.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +22 Vote: I do not like it

      Not to mention that they are scheduled to organize IOI in 2024 as well.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +41 Vote: I do not like it

      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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    What do you mean? Do teams have to pay? I thought hotels are covered by ICPC (based on my experience).

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        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).

»
3 months ago, # |
  Vote: I like it +38 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +22 Vote: I do not like it

You better start saving some money to participate.

»
3 months ago, # |
  Vote: I like it +88 Vote: I do not like it

oh no

»
3 months ago, # |
  Vote: I like it +95 Vote: I do not like it

What the ....

ICPC is like : let's merge and host our two ICPCs in the region with the shittiest organizers.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Link to official announcement?

»
3 months ago, # |
  Vote: I like it +20 Vote: I do not like it

How you guys liked this year dhaka world final arranged by bangladesh? I just asking out of curiosity.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +130 Vote: I do not like it

    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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +107 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +86 Vote: I do not like it

    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 :)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +69 Vote: I do not like it

    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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +97 Vote: I do not like it

    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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +93 Vote: I do not like it

    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):
    Spoiler
    • 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).

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

      +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 retarded

      also, after 1.5h or so of speeches, asking ARE YOU READY for the fifth time felt like he was doing it on purpose xd

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +55 Vote: I do not like it

        If you didn't tune in to the ICPC Live stream, there are some highlights. For example...

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 :)

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Whaaaaaat. And my team has told me that their FFT solution worked very close to TL (despite their TRD FFT implementation being very efficient).

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          Two points:

          1. 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.

          2. 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.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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).

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              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

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it
            1. 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
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            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$$$.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          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})$$$

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +9 Vote: I do not like it

            Thanks _LeMur_ for very clever reducing positions method. I got all the idea!

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +12 Vote: I do not like it

            Thanks xiaowuc1! Do you know where can upsolve again WF final this year or when testcase are shared?. Because the mirror constest has ended.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +12 Vote: I do not like it

              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...

  • »
    »
    3 months ago, # ^ |
    Rev. 5   Vote: I like it +40 Vote: I do not like it

    My overall experience was fairly positive, with the most negative aspects out of ICPC's control given the host city of the contest.

    Good:

    Choice of hotels and venue. The hotels were great and the venue fitting for the contest. We got by far the best hotel though in Westin, it was by far the closest hotel both to the airport and contest venue, so I could see others having a less stellar experience. The WIFI connectivity at the venue was poor to nonexistent.

    In-person contest. This was my first in-person contest since 2018, so getting to meet other competitive programmers from around the world was great. The contest schedule did no good in this regard though, as before the contest you have other important things to focus on, and after it ended all teams already had to hurry to the airport. In the future, maybe placing an excursion day after the contest day would be nice.

    Neutral:

    The food. Anything with lentils in it was amazing, but the food available at the exhibition was very uninspiring with its poor imitation of US junk food. As a vegetarian, several times during the event I found myself eating just salad or steamed vegetables. Not only that, but during dress rehearsal the lunch provided was not the vegetarian option I had ordered, but tuna. Thankfully, this was fixed for contest day.

    Bad:

    TERRIBLE air quality. I wore two masks for most of the event, including the contest, and that actually didn't have anything to do with covid, it was just to make the air somewhat more tolerable to breathe. The top mask was visibly darker by the end of the event from all the smog caught in it. I am very surprised nobody else has mentioned this yet, as it in my opinion was by far the greatest drawback of the finals.

    Extremely unsafe traffic. When we left the airport, I couldn't find the seatbelt, and when I asked about it, I was shown not where the seatbelt is (it didn't exist) but how to adjust the seat. This was a regular 7-person van, and that trip to the hotel had us overtaking an ambulance with sirens on. I've never seen such disregard for safety in traffic before, and I am not eager to see it again.

    Covid safety. Many didn't follow the rules but nobody seemed to care. Not even hotel employees wore masks, and the elevator capacity limits were clearly impossible to fulfill with just 3 and no stairs available. I heard rumors of positive tests on the table of the testing room but no contestant tested positive. Overall seemed like they were going for illusion of safety rather than safety itself. The person doing the tests though did perhaps even too good of a job, that stick went very deep.

    Issues with the problemset. Not going to repeat what everyone else is saying about the problemset, but in short B TL is too weak and G input size change is unacceptable. I did like problem I though.

    Keyboard. Unlike the last three world finals, the keyboard available had the ANSI layout, not the international ISO one, and there was no opportunity to submit your own keyboard. This was a large issue for us, as the ANSI layout is missing the key used to write <>|, without which C++ is obviously impossible to use. In the end we got through with a dirty hack mapping caps lock to <> and using "or", "bitor" and "or_eq" in place of |.

    Technical issues. During the Huawei challenge, the VS code C++ extension did not exist, which made my teammate learn CLion overnight and spend much of the dress rehearsal figuring out how to configure it. Thankfully, it turned out that the extension was supposed to be there, and it was added in time for competition day.

    Mindnumbingly boring, repetitive and far too streched-out speeches. This seems like the standard now, but it would be nice if they would finally do something about it, especially with how many events went overtime. This issue was aggravated by the poor WIFI.