ICPC Communication Routing Challenge — powered by Huawei
By ICPCNews, 3 years ago, In English

text

Hello, Codeforces!

Welcome to the ICPC Communication Routing Challenge powered by Huawei!

This challenge edition is very special, as it will be happening in conjunction with the ICPC World Finals! For those who are not participating in the finals — ICPC and Codeforces are offering a unique chance to compete during a 5-day Challenge Marathon and win amazing prizes from Huawei!

ICPC Challenge Marathon (open to public, unrated): October 9-14, 2021, 00:00 UTC:

REGISTER

This time we’re delighted to provide you with a future-oriented topic – routing algorithms for next-generation communication. During this Challenge we will provide you with a super-large inter-satellite optical network to properly plan message paths, to reduce communication latency and improve resource utilization. However, finding the optimal path in a network with limited resources is an NP-hard problem. Considering the physical constraints of optics and circuits, our algorithm faces greater technical challenges:

  • How can we model and abstract device constraints and design algorithms in the most appropriate way?
  • Is there an algorithm that takes almost the same time to calculate routes as the network scale increases?
  • Is there any way to obtain the theoretical optimal solution in a short period for ultra-large networks?

We hope that these satellite communications challenge questions can help you understand the problems that Huawei's software algorithm researchers face every day. All the best!!!

Prizes

For 3-hours onsite ICPC World Finals Challenge Huawei will provide prizes to the winners in 2 groups of participants:

  • Group 1: TOP 30 ICPC World Finalists, who participate individually: text

    1st-10th place HUAWEI MATE 40 Pro
    11th-20th place HUAWEI MatePad Pro
    21st-30th place HUAWEI WATCH 3 Pro

  • Group 2: TOP 9 ICPC World Finals Coaches and Co-Coaches, who participate individually:

    1st-3rd place HUAWEI MATE 40 Pro
    4th-6th place HUAWEI MatePad Pro
    7th-9th place HUAWEI WATCH 3 Pro

For 5 days online Challenge Marathon, Huawei will provide prizes to TOP 30 individual participants:

1st place* HUAWEI MateBook X Pro + 5000 USD
2nd — 4th place HUAWEI MateBook X Pro
5th — 10th place HUAWEI MATE 40 Pro
11th — 16th place HUAWEI MatePad Pro
17th — 22nd place HUAWEI WATCH 3 Pro Classic
23rd — 30th place HUAWEI FreeBuds Studio

* The 1st place winner will get additional bonus in amount of 5000 USD. If the bonus cannot be transferred to the winner due to any reason, it may be replaced by a prize of the same value.

If the allocated Huawei Challenge prize cannot be delivered to your region for any reason it may be replaced by another prize of the same value (if no legal restrictions), at the discretion of the sponsor.

By participating in this Challenge, you agree to the Challenge Rules and Conditions of Participation

Good luck to all participants!

UPD: The contest duration has been extended to 5 days. The actual finish time is October 14, 2021, 00:00 UTC

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

Comments Comments (52)
| Write comment?
»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

dang, tourist is about to get so much stuff now...

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Hope Huawei will provide another fantastic contest like this

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

huawei sopports?!

i never heard a chinese company sopports any contests.

→ Reply
»
3 years ago, # |
  Vote: I like it -32 Vote: I do not like it

real funny, uses others as free labor forces and the top payment is HUAWEI MateBook X Pro + 5000 USD? No offense, but that is a smart move.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You do know that top solutions on such types of contests are completely unusable in their resulting form for business applications, right?

    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Is the problem for onsite event and for marathon different?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems so. There will be additional restrictions in the marathon.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -18 Vote: I do not like it

qpzc

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

how can i delete the comment??

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Any Huawei prize for US contestants would pretty much be useless anyways due to US and Google Play ban of Huawei

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      US propoganda that China will track and steal all your info. pfft like the US doesn't smh. Anyways, also, it was during the time that Huawei was doing really really good and the US was just jealous and wanted US companies to do better. Though I guess any country would want their own companies better than foreign ones

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The United States is afraid of Huawei，I could've died laughing.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then why does the United States need to find such a false reason to sanction Huawei？

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is ICPC username? Is it the email address of my account on https://icpc.global/?

→ Reply
»
3 years ago, # |
  Vote: I like it -18 Vote: I do not like it

rated only for naturals

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

My second challenge in codeforces. Best of luck to all!

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is it true that 3 hours contest and 4 days contest are same task and some contestants can cheating?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

(posting this here because i don't think clarifications work in marathons)

Does GFL limit the number of flows that can pass through a group or the total flow rate that can pass through a group?

edit: it's the number of flows

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can we have a checker log or something ? Like it is truly hard to know where we are wrong.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    Adding to this, could we also have time / memory usage if possible? The submit limits make it irritating to binary search on constants to maximize score without TLEing.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      A. Communication Routing Challenge
time limit per test 2 seconds
memory limit per test 512 megabytes

      Right at the top of the task

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +21 Vote: I do not like it

        Time / memory usage of a submission, not the problem constraints. As in is my submission running in 300ms or 1950ms. I know I can use a timer and make my soln stop at like 1.9s, but knowing the running times makes some stuff easier.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +35 Vote: I do not like it

          Oh, that. At least you can see the time, just go to the submissions tab of your profile page. Unfortunately it's only the worst time, no per-testcase resolution. Now that you mention it, I think I've seen this feature before at the veeroute contest.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +24 Vote: I do not like it

            Thats actually exactly what I needed, thanks!

            Though I expect that's unintentional and its not supposed to be visible on the profile lmao.

            → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +51 Vote: I do not like it

The contest duration has been extended to 5 days. The actual finish time is 14 Oct 2021, 00:00 UTC

This is a backstab move. Don't you think people have some plans?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    I apologize for that, but at some stage, there was a discrepancy in the duration of the contest. Even the post here talked about a 5-day marathon. I think it is better to unexpectedly extend for a part of the audience than unexpectedly shorten it by a day. The situation is unpleasant, I agree. Next time we will take a closer look at this. Sorry.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +41 Vote: I do not like it

      The thing is that a major part of the audience thought that the contest is going to end at midnight so the "unexpectedly shorten" argument is not very valid.

      → Reply
»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

The contest duration has been extended to 5 days. The actual finish time is October 14, 2021, 00:00 UTC**

What?! I planned my time with a duration of 4 days. It's not fair!

→ Reply
»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

What was the reason to extend the duration 13 hours before the end (according to all announcements (except video) duration equal to 4 days)? I understand that it is beneficial for people that can allocate more free time. But for me (and I guess some other people), it either completely ruins plans or a day of anxiety (watching how other people outrun you).

I would like to participate during all 5 days, but only if the contest duration was given correctly from the beginning.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

The video announcement always mentioned a "5 days marathon" (at 1:32). So was it just a bad communication (pun intended) between codeforces and Huawei? Anyways I agree with previous posters: I'm not very pleased about this late change, I made sure to allocate 4 days for the contest.

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

23rd place, 33662

I did a “smart” initial assignment and random optimisations afterward.

  • The distance everywhere onward is just the number of edges in the path (obviously, ignore the given distances). Usage of some custom edge weights significantly slowed down the search, as I needed to switch from BFS to Dijkstra and I did not come up with any cool 0-K edges.

  • I handle blocked edge pairs in the most straightforward way — I keep track of the parent edge for vertices in the BFS and do not go to edges which are blocked by the parent.

  • For the first part, I greedily add queries to the answer. I took queries with the shortest distance (in case of equality — smaller flow). Other metrics combining distance, flow, number of blocked edges, group sizes etc. performed worse.

  • I sorted edges for each node in the order of increasing capacity. It forced BFS to find path that takes smaller edges if possible, which seems to be beneficial.

  • Without randomisation, proper selection of the shortest query (rather than approximation) gives significant improvement. To do it fast, I initially precomputed distances between all the node pairs (without any restrictions on the capacity) and initialized query lengths with these values as a lower bound. Then I iteratively took the shortest candidate from a set, and if it had a precomputed path (and it was still passable) just added this query to the answer. Otherwise, I recomputed the path and returned it to the set. This way I processed all the queries in about a second and got something like 33200.

  • In the randomization part, I tried to delete 10 paths from the answer, random shuffle all the remaining queries and edges in each node, and then run queries in this order. If the answer do not improve this way, I rolled back the deleted paths.
  • Other random techniques like annealing over the described approach or removal of paths going through the particular edge did not give improvements.

Well, this is it. The rest is some tuning of constants, random seeds, and other meaningless stuff (I’ve got +20 points by adding a bunch of pragmas lol)

Since there are only 2 or 3 large tests and they are closed from us (unlike in HashCode for example) it was very hard to understand what are the weak parts of the current solution. I feel like I did dozens of optimisations that I believed should strongly impact the result, but they did not do anything. And after some cleaning, my best solution looks really straightforward which makes me feel sad as I could have implemented it right away.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro, how long has your 33200 solution been running? and the delete edge， Can the edge deletion strategy be improved by nearly 400 point?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    My solution is basically the same as yours, but I only got 29000+. (and I wrote 1k+ lines of code)

    First I tried floyd, but it was too slow, so I switched to dij to calculate the number of minimum number of edges. Next I went for a balance between the number of edges and the distance, and sorted the flow by rate.

    I wrote a simple undo operation, also tried randomization, i put the blocked flow in front,sort the blocked flow from the largest to the smallest, and then the last 4/5 sorted in ascending order (I think some large flows are more likely to block, but if too many large flows are put in front, it will reduce the overall answer)

    I feel that this is not too different from your algorithm, but the score is not good, so I also wrote a lot of optimization.

    I preprocessed some of the feasible paths for all flows, and roughly calculated the importance of each edge. If the flow through an edge is much larger than its capacity, or if a flow has to go through it, then it becomes very important. If possible, the importance of the edges a stream flows through should be as small as possible.

    Due to the limitations of edges and groups, I calculated the average flow rate that each node and group should pass through. The coefficient, importance, and difference between the flow and the average flow are multiplied to measure which edges a flow should pass through first. This avoids the possibility that a group with a large capacity only passes through some flows with a small rate.

    I don't know why my score is so low, if someone can tell me, thanks a lot. (My English is not very good, some sentences are translated)

    → Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Thank you for the interesting contest, I am a little disappointed that I didn’t get the prize, but the task is fascinating as always. The addition of an extra day was very upsetting, because it happened in my time zone before the night and because of this I could not plan the time normally. People who get this time in the morning obviously have an advantage.

All the same, marathon problems are my favorite type of competition, because it allows even being inferior in level to compete on an equal footing with participants who have constant competition practice.

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Will the submissions be open to public? It would be interesting to check the top scoring solutions

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +79 Vote: I do not like it

1st place, 34332

My solution is divided into three parts.

  1. I did a rather smart initial assignment. In this part, the flow rate of each flow is only to check whether an edge can be passed. And the distance is just the number of edges in the path. My BFS starts from both the start and the end simultaneously, which is much faster than starting from only the start. To handle the blocked edges inside a node, I just considered the first edge that comes to a node, although it may cause some unfound paths. The algorithm is to add the current shortest path greedily(use a priority queue to maintain it), which can get about 33280 in 250ms.

  2. I looked over all the unsatisfied flows and check whether there exists a path that only contains 0/1 illegal edge using BFS. If no edge is illegal, I just add the path. If only one edge is illegal, I delete a flow that goes through that edge, then add the path just found and try to re-add the flow just deleted. Repeatedly running this algorithm until 500ms can lead to 33750.

  3. Do the following algorithm repeatedly until the end:

  • Choose 5 satisfied flows to delete.
  • Choose 50 unsatisfied flows and try to add them.
  • Try to re-add the 5 flows just deleted.
  • If it becomes worse, roll back to the beginning.

This can raise the score from 33750 to 34332.

There are several other optimizations in my solution:

  • Sort the edges.
  • Check the flows in a certain order.
  • Change the random seed.
  • Store the information in a clever form with a very small time constant.

These will certainly improve the result, but I can't evaluate their effect. So that's all my solution. The third part of it seems not very effective but it really improves much. I still don't get why it is that helpful. Actually I tried lots of optimizations during the contests, but most of them are difficult to implement and founded useless after spending much time. That made me very painful. :(

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    simpler is better)) good job!

    Can you please share your code? Really want to see how you implemented first part to run in 250ms

    → Reply