ICPC 2022 Online Challenge powered by HUAWEI

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

text

Hello, Codeforces!

We are happy to invite you to an exciting online event: ICPC 2022 Online Challenge powered by HUAWEI，which will start on September 15, 2022, 00:00 UTC (UTC+0).

In this Challenge, you will have a unique chance:

to compete for 2 weeks online during the challenge
to solve 1 or 2 problems prepared by different business domains of HUAWEI
to win amazing prizes from HUAWEI!

As a special prize, HUAWEI together with ICPC Foundation will provide the travel trip to the 46th Annual ICPC World Finals in a guest role to the 2 winners (1 winner for each problem)!

Everyone is welcome to participate. It is an individual competition. ICPC 2022 Online Challenge powered by HUAWEI (open to the public): September 15 — September 30, 2022, 00:00 UTC (UTC+0)

This time HUAWEI has prepared 2 challenging tasks for you from different business domains – Data Communication and Cloud.

You are free to choose which problem you would like to solve, and you are also welcome to solve both problems, but please remember the total runtime of both rounds, which start simultaneously, is 15 days only. We hope you'll enjoy this complex yet very exciting Challenge!

Each problem will have its own scoreboard and its own prize fund, so this is a unique chance for you to win double prizes for two solved problems!

Problem No 1: Optimal graph partitioning for fast routing

This problem comes from HUAWEI’s Data Communication business domain, in which routing algorithms have always been a critical issue. In the future, as more and more communication devices are connected to networks, data communication will face an interconnected network formed by ultra-large-scale network devices.

In this challenge, data communication experts of HUAWEI will provide you several network topologies. By dividing them into abstract domains, you need to scale down these topologies and enable quick route calculation, so that fast route convergence can be implemented on large-scale networks. Domain division must address the optimal routing and network scale constraints, so a routing algorithm that effectively divides domains while also meeting these constraints is the core of the algorithm design.

Problem No 2: Topology-Aware VM Placement

This problem comes from another HUAWEI’s business domain – Huawei Cloud. To win the competition in cloud computing market, major cloud service providers are focusing on improving the utilization of cloud resources, as this will allow to reduce the cost of cloud services. It is estimated that even a 1% increase in cloud service resource utilization can save millions of dollars in costs. The optimization of resource utilization, in turn, requires the development of advanced algorithms and technologies for cloud resource management.

The virtual machine (VM) placement algorithm considered in this contest is one of these critical algorithms, which is used to select a physical machine for running a user VM. Since VM requests arrive dynamically, this algorithm works in online fashion. The main goal is to maximize the number of successfully placed VMs. As the algorithm runs on a resource pool of fixed size the more requests are allocated, the less resources are wasted and the more resource efficient is the algorithm. A secondary goal is to maximize the number of VMs placed without violation of additional soft constraints, as it improves the cloud user experience.

text

Prizes

Grand Prize (Rank 1):
Problem 1: 15,000 EUR + the travel trip to the 46th Annual ICPC World Finals in a guest role
Problem 2: 15,000 EUR + the travel trip to the 46th Annual ICPC World Finals in a guest role

First Prize (Rank 2- 6):
Problem 1: 8,000 EUR
Problem 2: 8,000 EUR

Second Prize (Rank 7- 16):
Problem 1: 3,000 EUR
Problem 2: 3,000 EUR

Third Prize (Rank 17 – 46):
Problem 1: HUAWEI FreeBuds
Problem 2: HUAWEI FreeBuds

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

Challenge Rules and Conditions

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

Good luck, we hope this will be fun!

Комментарии (142)

Показать архивные | Написать комментарий?

puneet_73

2 года назад, # |

Such a Big Prize Pool, Excited to see the problems, more excited to see the winners!

→ Ответить

bycicle

2 года назад, # ^ |

← Rev. 3 →

-99

As a participant, I will participate.

Spoiler for upvotes:

Satrpx

← Rev. 2 →

Can't believe I unfolded all the spoilers above.

Spoiler

lovelyaben

me too, but to tell the truth, this message is very useless and wastes time.

LawrenLang

Excellent cooperation! Can't wait to see the problem!

Tom66

Wow,2 weeks&2problems! Is it the same to AHC?

BULLMCHOW

It will probably be the same as last year, *special problem, i.e. AHC.

M.HasnatFarooq

Wow! Huge prizes.

naman2411

Shouldn't some lucky winners be decided so that everyone is motivated to do this

Karatinos

Interesting to see the problems

Corundum

I have never participated, how difficult are usually these kinds of optimization tasks?

Will it be rated??

Abito

BallBreaker

thanks

You're welcome my man Rick

ZloyNegr

Thanks, Huawei! I missed this format of competition.

SalmaHatem_

Note The Unusual Time

chromate00

Is it rated though?

I think it is unrated!

mayank_pathakk

Hey how can I study and prepare for these problems... Can someone please suggest the resources for the same. I don't know these topics but I do want to participate and try and solve the problems. Huge thanks in advance.

AlekseevaTanya

← Rev. 4 →

+26

Useful resources for graph partitioning and routing:

Useful resources for VM placement problem and data center network topology:

what big prices!

loser_complex

For someone relatively new to programming in general, should I attempt these or are they way out of my league? Because they look very tough

They aren't rated, and after all, it doesn't hurt to try. You might learn something while participating after all!

csegura

+17

"Only participants who entered a valid ICPC username (email address) during registration are eligible for recognition as a Challenge winner."

So, non-ICPC participants are not eligible for prizes? Can coaches participate for prizes?

sucks to be a non-ICPC participant (freshman next year)

ejfiji

We don't need to actually participate in the 2022 ICPC, right? Just need to have an ICPC account to be eligible?

ICPCNews

+19

Right! If you're not a participant yet — it's not a problem. You may need to just create an account here: https://icpc.global/register

All the best for the competition!

spdfghi

my codeforces email is also icpc user name, does it ok now? should i do some extra work to associate them?

-10

Please link your ICPC account to the Codeforces account here: https://mirror.codeforces.com/settings/general

chakred_namor

+85

Unfortunately, I can't find where I can link my ICPC account using this link.

Please check more details on your question in this comment https://mirror.codeforces.com/blog/entry/105097?#comment-956845

DonSilvio

So, will you respond to the unavailability of account linking?

NVAL

What is exact contest duration? 15 days (like in contests system) or 2 weeks (like in blog)?
One year ago contest duration was increased for 1 day in the last day. It was unexpected and a little bit unfair.

geranazavr555

+15

15 days. Blog has been fixed, thanks.

ashmelev

+11

Is there a way for unofficial (without prizes) participation for Huawei employees?

rurixx

Question about test cases of "Optimal Graph Partition for Fast Routing (GP1)".

Why is the graph divided into three subsets? As i understand, it should be divided into two subsets: $$$P=\lbrace \lbrace 0,1 \rbrace, \lbrace2,3 \rbrace \rbrace$$$. In this case $$$ RTsize = 2 + 2 - 1 = 3 $$$.

Also, not divided graph has $$$ RTsize = 4 $$$ and $$$ all $$$ edges are free. This score is more than test solution's score as well.

Saucemaster102

isn't it against the contest rules to ask questions about an ongoing contest?

The question is about condition, not solution. I suppose it isn't against rule.

The sample output may not be the best solution to the sample input, they are just valid output to demonstrate how score is calculated.

Is the output valid if it don't minimize $$$RTsize$$$?

yes. minimizing $$$RTsize$$$ is not a strict criterion for the validity of the output.

a_little_cute

can you add an explanation to the test 1??? or even a checker or even said the right answer

You can download the test and review your output, it is actually wrong.

21 месяц назад, # ^ |

LordVoIdebug

+18

How do you link your ICPC account to Codeforces? Or the only requirement is that the email addresses on Codeforces and icpc.global are the same?

I tried to google how to do it, found that there used to be an option in the account settings (and i vaguely recall that maybe i did something like this in the past) (https://mirror.codeforces.com/blog/entry/90185) but there is no such an option in the settings anymore.

Coder

Where did you see that message?

There is nothing in the rules about having ICPC username during registration.

reeWorld

There is a link in the bottom of the post.

29_2002

Will this be rated?

bashkort

akifpatel

The problems say 0.3*score1 + 0.7*score2 will be used for the rankings, but the scoreboard just seems to add them up. I'm not sure what's going on.

Gary2005

This is not final test data.

foreseeable

The total score on the scoreboard is already weighted sum. For example, if someone got 30 pts for GP1 and 140 pts for GP2 on scoreboard, that means the total sum of score he got on GP1 test cases is 30/0.3 = 100, for GP2 is 140/0.7=200. Hence the total score for ranking is 30+140 = 170.

Huah

but, there are some testcase in gp1 score is 99xxx，the n most 100000，after weighted, it most 30000

GrandSouris

+33

Is it available to provide a grader for problem 1, GP 2? Thanks.

Why the submissions were rejudged?

egor_bb

Are the current testing results that we see in the system final or will there be a separate testing after the competition ends?

SYury

-8

Problem 2 has no hidden tests, the scoreboard shows final scores.

Ahmed_AboRadwan

-12

Is it just me who keeps coming back every hour to see if any rated contest has been scheduled ?

M_bolshakov

Same lol

Rebelz

Why nobody answer my questions?

brunovsky

+80

It has been 48 hours and the ICPC account issue has still not been addressed. No one wants to spend 12 more days working on the problems under the possibility of being informed they are not eligible for the prizes because of some random technicality or unclear prerequisites they do not meet. Last year if I remember correctly there was an option during registration to link our ICPC account, this year I did not get any such option, yet it still seems to be required for everyone?

Please resolve this issue as soon as possible. Is it sufficient to have a personal account?

ELIGIBILITY: To be eligible to participate, Participant must: ... if requested, associate Participant’s Contest Account with Participant’s ICPC account.

+24

I wish MikeMirzayanov could solve this issue .

lycmd

+29

Sorry for the ping but ICPCNews please solve the issue ASAP.

+10

Survivor_winner

Rated or UnRated?

The rules of the challenge states that Participant’s Contest Account should be associated with Participant’s ICPC account. It is technically not possible now. Previous suggestion to use built-in Codeforces function to associate accounts was not correct.
To participate in ICPC Challenge it is not required to have ICPC account.
To be eligible for the official ICPC Certificate or Sponsor’s prizes it is required to create free account at https://icpc.global with the same username (email) as Codeforces username (email). The fact that the Participant confirms same email in both systems is assumed as confirmation that Participant is the owner of both accounts.
If Participant has already account in https://icpc.global it is allowed to change email in ICPC account to the email used for authentication in Codeforces.
All winners will be notified and additional week will be provided to correct ICPC account.

whyiseveryonesuccessful

What should I do if my email address is unavailable

Could you please elaborate? Which email address and where it is unavailable?

The email I used when I signed up for codeforces(3130558971@qq.com).I can't log in to this email anymore, but I used this email to register an account on https://icpc.global.

You can change your email address in Codeforces settings. If you have lost access to your mailbox and want to recover access to your ICPC account, please contact help@icpc.global.

__c_j_n__

deleted.

suncup224

Will the notification be sent via email or Codeforces messages? When will the notification be sent?

gultai4ukr

4. If Participant has already account in https://icpc.global it is allowed to change email in ICPC account to the email used for authentication in Codeforces.

Is it fine to do the opposite? I mean change Codeforces email to the one, which I used in ICPC account?

conexposys

← Rev. 5 →

All winners will be notified and additional week will be provided to correct ICPC account.

Has anyone been notified ?

eulerscheZahl

Not yet. For reference: last year the contest ended on October 14th, I received a message on October 19th. And by standards of other contests that's pretty fast. So no reason to get nervous ;)

LYC.

+35

When will the system test start？

Currently it says "final standings" on problem 1 and "system testing" on problem 2. Wasn't it announced the other way?

Where is system test? ICPCNews

MicroMaker

When will the P1's system test start？

Dd2dD2

Will it be evaluated as the last submission rather than the highest score?

Yes.

After the end of the coding phase, the last submission that scored a positive number of points on the pre-tests will be selected. It will be retested in the final tests. The rest of your submissions will be ignored. The final tests are secret and not available to the participants, they are mostly realistic. The result obtained on the final tests is your final official result for this problem.

I submitted the code for GP1 to GP2, and that's my last submission to GP2. It's so sad.

What a pity!

_TOBapNw_

When will the system test end?

mounir.bahtat

Does this rule only apply to Problem 1, or to both problems:

General announcement ***** When the contest is over, then for each participant the last submission will be selected (which scored non-zero points). This particular submission will be tested on the main test suite (other submissions will be ignored). ?

Problem 2 clearly states:

Your solution will be judged based on multiple tests. The test set is fixed during the whole contest, no retesting of solutions on extra tests will be made.

Yes, the test set is fixed, but which "solution" that will be tested? that's the question. The last submission or the best one?

To my understanding, there will be no re-testing at all for problem 2. That's also how it was handled last year at both Huawei contests, so problem 1 is more of an outliner.

For the problem 2 the best solution will be chosen because there is no hidden testset.

amethyst0

+31

How to get 800k+ score on Problem 2? Can someone share main ideas to do this? Do you have different solutions for different slices of cases, or your solution is universal for every case?

icecuber

+59

Here are some details about my 944k 1st place solution.

My baseline solution was greedily putting VMs the first place which satisfied the constraints. I experimented a bit with orders (like going through networks domains from least full to most full), and got about 650k points. This was surprisingly hard to beat.

My final approach, which was the first I found which beat the baseline, was based on knapsack. I gave VMs score equal to pow((vm_cpu+vm_memory)*vm_numas, 2) and precomputed for 2 numas the optimal knapsack scores. This gave me a O(1) function scorePM(cpu0,mem0,cpu1,mem1), it would be called twice if numas = 4. There were some tricks to fit it in the memory and time constraints.

I would then use [scorePM after placement] minus [scorePM before placement] to compute the cost of storing up to 5 of the current VM type at any position, making a [networks domains] x [racks per network] x [pms per rack] x 5 cost array. I would add two extra costs: the cost of having at least one VM in network #i, and the cost of having at least one VM in rack #ij. I would then place "cnt" VMs at once by running a knapsack-like DP for optimizing the total cost.

The extra costs would punish undesirable placements such as adding to a new rack if hard rack affinity was present, or punishing adding to a network which was almost full. All the constraints could be put into this framework. There were a bunch of parameters controlling the tradeoffs, and only after a bit of parameter tuning did this approach beat the greedy baseline.

After playing with the parameters I noticed that my solution was wildly unstable towards infinitesimal changes in the parameters. The cause was probably that I was comparing basically equal doubles in the final knapsack DP, which meant rounding was determining the outcome. I later replaced this by pseudorandom epsilons in the knapsack DP comparisons, which caused random decisions for equal choices, with a tunable seed. I submitted many solutions with different random seeds to increase my leaderboard score. This gave me my 774k solution.

I noticed that we were given the score for each test case, so we could optimize the seed separately for each test case. This felt a bit undesirable from the organizers' perspective, since it causes extreme overfitting to the leaderboards. However, I couldn't find anything in the rules disallowing it. I messaged the organizers on Sunday, explaining the strategy and asking them to verify that it was allowed. I got no response.

On the final day of the contest, I submitted my ensembling solution which used the first 10 queries to determine the test case number. It then used the test case number to pick the seed which worked best among 200 previous submissions. This gave me my final score of 944k.

Edit: changed <...> to [...] since <...> didn't show up in the comment.

+16

I thought about selecting parameters for each test independently, but decided that this is not fair. A little sad.

-18

For people who got 200k+ on both GP1 and GP2: How did you get such a score? Personally, I tried to minimize $$$RTSize$$$ by setting a limit on the component size to $$$\lfloor c \sqrt{N} \rfloor$$$ when $$$c$$$ is a constant marginally bigger than $$$1$$$. What was your approach?

+21

Choose one spanning tree of the graph , and do some greedy solution on the tree.

Noam527

If you fix some upperbound $$$B$$$ on the component size you allow, and fix some spanning tree, you can try to split the tree into minimum number of connected components of size upto $$$B$$$. This dp problem is solvable in $$$O(n)$$$, so you can try to fix multiple values of $$$B$$$ and take the best found. For instance I tried iterating on bounds starting from 1 to $$$n$$$, each time multiplying by 1.7. There isn't really any point in trying small bounds but it barely hurts (the actual useful attempts are those around $$$\sqrt{N}$$$).

You can independently try this on multiple spanning trees. This works well on GP1 since the weights don't matter, and on GP2 this is decent to try this on the MST (as a heuristic).

Actually your approach seems to be very similar to mine. The only difference is that instead of splitting the spanning tree, I tried to construct the components, just like how Kruskal works. With the size optimization on the DSU, we readily have information about the component size (so we can reject merging two components when the combined size exceed the bounds)

Well if I recall correctly, it's sufficient for 200k+ on both subproblems. Of course you need to use other approaches to nail more difficult cases (on GP2).

TheScrasse

Why do I get Judgement failed on my submission to problem 1?

yzc2005

Same but on problem 2

Send links for submissions please

stefanbalaz2

will we be able to submit additional solutions to the problem1 just to test out some other ideas on the full test data?

+39

I feel very sad. TLE has a set of test cases.

The final score is 507618*0.3+1350210*0.7=1097432.

After multiplying by the coefficient, everything may not be in vain.

In the future, I will not participate in such a competition with only one submission opportunity, because it is too risky. I don't want to waste a lot of time and get nothing.

#9: Time limit exceeded [4000 ms, 412 MB]

There are only two kinds of points in GP1: 60w or 65w. This is a huge difference but they have no any difference on pretest. It's totally random and I think it is really unfair. In addition, participants can't know whether they get RE/TLE/MLE on final test, which caused great uncertainty.

To some extent, P1 is a competition for luck. It's a huge mistake to participate in a contest like this.

+32

I'm sorry for your decrease in a single position, but I don't think it's unfair.

If anything, I think it was predictable that the final positioning is ought to have some deviation from the standings throughout the contest. In the "Scoring" section you can see it's stated to have additional secret tests (and furthermore, that the pretests are not counted to the final score). I don't want you to feel down, but it should be clear that overfitting solutions to the pretests (whether overfitting on time, memory or specific instances that appear on the pretests) is a bad idea.

It definitely, partially relied on luck, the point was to approximate your average position throughout the contest. 600k vs 650k is unfortunate but if you put yourself tight on the 5 seconds time limit on pretests, you can't expect to pass everything for sure.

I think it's an exaggeration to call this a "competition for luck" or a "huge mistake to participate", and you should be grateful for your 2nd position and considerable prize.

As a contestant, I can't agree with you because we spent a lot of time. The last one has too much uncertainty on the unknown test set. Someone may not get a good result because of this data set, but his method can be more valuable if slightly modified. The participant's method has certain value to the enterprise, but because of some uncertain factors, the participant did not get anything, which is unfair.

We should differentiate between what is unfair, and what the contest should have been.

I do agree that the contest would have been more valuable to Huawei, if there were no secret cases, and furthermore it would be more realistic to give us the entirety of the testcases and make the problem "output only", without a small time limit (yet this poses the problem of people with different computers).

Your case is extremely unfortunate and I'm sorry for that. But in my opinion, once all the contest rules have been set as they are (even if we disagree with them), no rules were changed and by participating you are knowledgable to all the outcomes, you can't call this unfair.

Therefore, I accept the present result under the rules. But I still think this rule is unreasonable. As a contestant, I have no way to change the rules. I can only choose to refuse to participate in competitions with such rules in the future.

Maybe it's an exaggeration for GP2, but for GP1, the score really depends on luck. The score in pretest literally has no correlation to the final score. It's nearly random.

I still think it's not worthy to participate in a contest like this. One of my friend also participated in this contest, and he was top 10 before the final testing. Because he got MLE on many testcases, he can't get any prize now. The rules of this contest greatly increase the uncertainty and make participants take risks of wasting a huge amount of time.

Your comment is more proper as a feedback to the people who prepared the competition, that they should have prepared it otherwise.

And the standings are nothing like "nearly random", the relative positioning did not change too much for most of the people. In fact it's similar to a usual CF round, with the exception of the duration. So in my opinion you don't present a proper complaint, as I mentioned in my other replies.

Edit: didn't see that you talked specifically on GP1 (thought you meant P1). In that case you're right, but idk how the authors could predict this (unless they really put unrealistic testcases, but I can't compare between them). Still, the MLE should be more predictable than simply "non-correlative testcases".

How to get my prize?

What does the question mark in the leaderboard mean?

aaaaawa

They're being retested. (Why some solutions are always being retested? They have been tested many times.)

Chinese_zjc_

Yeah, why some solutions are always being retested? They have been tested many times. If they use random until they get the best answer, it's unfair to other contestants!

Please consider ignoring my last submission for GP1 and judge pre last submission for GP1.

It is moodily that I sent solution intended for GP2 to GP1 and now I have score equal to 25 instead of 600k/650k. I didn`t notice this submission as I sent it on day 7 of the contest and I was fully concentrated on GP2 on day7.

I think I am not the only person with such (or similar) problem and standings table is misleading during contest in this regard.

I understand that rules are rules, but it is so unpleasant to spend 15 days solving problems all day/night long and have 25 score becouse of one missklick...

Hope for your understanding.

-70

Please evaluate all submissions. It's so unfriendly to only judge the last submission, as the final test is unavailable to participants.

+140

Many people used random solution.So it will be unfair to people with fewer submissions.

+12

Why are there so many REJUDGE for TLE code? This can make people who use uncertain random seeds score higher. I have seen some players lose their original rewards because of this.

Pub

UNFAIR.

Problem 2 was very nice. Unfortunately I did not have enough time to converge on a solution that can remain very tidy in the face of item deletions. Congratulations to the winners!

Are you planning to reopen submissions in the near future?

+42

Is the contest allowing any soon seeing codes of participants? It would be interesting to check the top solutions.

P.S. just curious, is the winner of Problem 1 really from North Korea? :) & Congrats to the winners!

Are these final standings? I found that scores didn't multiply by 0.3 and 0.7 for GP1 and GP2.

The final result on scoreboard is already multiplied by the 0.3/0.7 coefficient.

Still wondering, where exactly?

It is not multiplied in each test point, because there is a test point with a score of 90k+.

By the way, when will the rewards be distributed?

A score of 90k does not mean the coefficient is not multiplied~

As for rewards, pls be patient. It’s coming soon ^_^

Originally there was no multiplication coefficient, now it is rejudged.

MikeMirzayanov

Hey! Thank you for your attention. You were indeed right. I fixed this issue. Now everything is correct.

qwerty787788

+20

Thanks for organizing this contest! I enjoyed thinking about good solutions for problem 2, but as always, all "smart" ideas, which I had, end up working worse than simple greedy, which I implemented on the first day :(

Would be very interesting to know how people with high scores approached this task (cc icecuber, winger, Alex_2oo8, Sung.An).

Familiar feeling :)

I would also add to that list Mr_Eight and eulerscheZahl as they made the least amount of submissions among top 16 (significantly less than others). So I guess their solutions are less about tweaking seeds/constants and more about some interesting insights/strategies.

+28

I had no intentions of writing this, as I don't consider my ideas that interesting. But as I get mentioned by name: You can find my 707k score submission here: https://gist.github.com/eulerscheZahl/5af1141fab1b8ec785c50c55a30a5564 I realized too late that codeforces already has .net6, C# only got a priority queue very recently and I copied one from stackoverflow. I came a little late to the party and only started competing in the 2nd week of the contest, as there was a topcoder marathon match at the same time.

My basic idea is to use hard constraints to pre-filter the PMs where I can possibly place a VM. If there is a hard affinity and it's the first query for a placement group (no rack/network assigned yet), I always take the rack/network with the most space left. For each of the possible targets I compute a penalty for placing a VM on it (how many VMs of each type can I place before vs after using a PM for the current query, line 781 in my code). Each PM also adds a tiny bit of randomness to the penalty which causes the placements to split more evenly. I have 2 scoring functions for this: one that properly considers VMs with 2 NUBA nodes and is therefore significantly slower and another one that roughly estimates the penalty. I switch to the faster scoring at the 9-second mark, so it's not used for most testcases. For soft constraints there is an additional bonus added to the score for fulfilling it. When a PM is used, the score for placing another VM on it is updated and it's put back into the priority queue along with the other candidates. For partitions I try to fill one rack first, as no other partition of the same PG could use the space anyways. This is again done by adjusting the score (so I allow to start another rack instead and it will happen if I would otherwise make too many VMs impossible). When starting a new rack this also means updating the scores of all other PMs on the same rack (in this case I have the same PM in the queue twice, with different scores assigned).

I also considered hardcoding for different seeds like icecuber described but didn't feel brave enough to pull it off (not sure about the rules). Instead I submitted the same code a few times, ranking from ~680k to the lucky 707k. There was some frustration as nothing seemed to work, with occasional breakthroughs caused by new ideas or finding bugs. At some point the offline testcases didn't help that much anymore.

Swistakk

+48

Wow, you managed to understand the statement in less than one day? Respect, I was not able to :P

https://mirror.codeforces.com/blog/entry/105097?#comment-958999 You can find the solution of icecuber here. Unfortunately, it's not really fair and really interesting.

+13

I bet the overfitting problem is happening anyway at different degrees, as long as the data set is fixed. They had to do something like in Problem 1, where the final data set is unknown.

+23

But not in the same way as they did for problem 1. More like on atcoder or topcoder: There you get a testcase generator so you can try as many different testcases offline as you want. It takes a seed to initialize some random number generator. When you submit during the contest, they use a certain set of seeds. After the contest they rejudge on a different set (100 testcases for provisional scores, 2000 for final scores on topcoder). They will only disclose the seeds used for final evaluation after the contest ends. Therefore you don't know the exact testcases but can be pretty sure that you can cover all the corner cases there might be.

They also normalize the scores to make testcases about equally important (in this Huawei contest a large graph can give you a lot more points, so it's not that relevant how you perform on small graphs). Topcoder does that by finding the best score obtained by any participant (per testcase) and assigning the full 100 points to it. The rest gets less, depending on how far they are off from that best known answer. This brings its own problems, as the scores of everyone change when someone submits a better solution (might confuse those who didn't read how the ranking works), yet I like the idea. Atcoder would probably add a factor of 100 / N or something like that in order to weight every testcase approximately the same.

It is good idea to make test case generator. But it is impossible to do in case Huawei wants to use real-world data.

I think, in practice, it is better to extrapolate given test cases and make more generic algorithm, so you don't need to modify your algorithm every time you get new data.

Here is question to organizers, if they want algorithms that suit some abstract test generator or algorithms that suit real-world data.

-7

There is this part in the Conditions of Participation:

Winners Selection: Only participants who entered a valid ICPC username (email address) during registration are eligible for recognition as a Challenge winner. Assuming sufficient eligible entries are received, it is anticipated that potential Judged Winners will be selected based on their highest combined score. Organizer may, but without obligation, select more than the stated number of winners if found to be of exceptional quality in Organizer’s sole and absolute discretion. Organizer reserves the right to select fewer than the stated number of winners due to insufficient eligible and qualified entries/participants. By way of example only, Organizer reserves the absolute right in its sole discretion to disqualify as ineligible entries that do not provide (in Organizer’s sole determination) a credible or feasible use of the solution technologies, appear not to have been submitted honestly, in good faith, or are otherwise lacking or non-compliant. All prize awards are subject to Organizer’s verification of entrant/entry’s eligibility and compliance.

Of course this does not mean that they will definitely cancel the winner selection on overfitted solutions, but they very well could.

I haven't received any message from Huawei , how do I claim my prize?

Me too. I think it's ok, and we should wait more.

Macesuted-Moe

15 месяцев назад, # |

Can you allow contestants to submit solutions after the contest is over?

I participated in the ICPC Challenge Championship and got some nice ideas about problem 2 by communicating to other contestants. I really want to try some strategies now but I am not able to submit codes to these problem.

I think even two weeks is not long enough for contestants to think about these problems completely. It would be nice to reopen these problem after contest, so that contestants can try more solutions. And if our codes is benificial for Huawei, I think reopen these problem could both benifits contestants and Huawei.

Блог пользователя ICPCNews

Problem No 1: Optimal graph partitioning for fast routing

Problem No 2: Topology-Aware VM Placement

Prizes

Challenge Rules and Conditions