ICPCNews's blog

By ICPCNews, 5 months ago,

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.

REGISTER

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.

REGISTER

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!

• +260

 » 5 months ago, # |   0 Such a Big Prize Pool, Excited to see the problems, more excited to see the winners!
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +8 Can't believe I unfolded all the spoilers above. SpoilerNow I feel like an idiot.
•  » » » » 5 months ago, # ^ |   0 me too, but to tell the truth, this message is very useless and wastes time.
 » 5 months ago, # |   0 Excellent cooperation! Can't wait to see the problem!
 » 5 months ago, # |   0 Wow,2 weeks&2problems! Is it the same to AHC?
•  » » 5 months ago, # ^ |   0 It will probably be the same as last year, *special problem, i.e. AHC.
 » 5 months ago, # |   +5 Wow! Huge prizes.
 » 5 months ago, # |   0 Shouldn't some lucky winners be decided so that everyone is motivated to do this
 » 5 months ago, # |   +5 Interesting to see the problems
 » 5 months ago, # |   +6 I have never participated, how difficult are usually these kinds of optimization tasks?
 » 5 months ago, # |   0 Will it be rated??
•  » » 5 months ago, # ^ |   0 No
•  » » » 5 months ago, # ^ |   0 thanks
•  » » » » 5 months ago, # ^ |   0 You're welcome my man Rick
•  » » 5 months ago, # ^ |   0 No it is unrated
 » 5 months ago, # |   +5 Thanks, Huawei! I missed this format of competition.
 » 5 months ago, # |   0 So interested in this challenge, maybe difficulty is more cause only 2 problems, and a lot of prizes, very excited
 » 5 months ago, # |   +3 Note The Unusual Time
•  » » 5 months ago, # ^ |   0 Is it rated though?
•  » » » 5 months ago, # ^ |   +3 I think it is unrated!
•  » » » 5 months ago, # ^ |   0 NO
 » 5 months ago, # |   0 Challenges are high so the prizes also.Best of luck who will be participate on this.
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ | ← Rev. 4 →   +26 Useful resources for graph partitioning and routing: Useful resources for VM placement problem and data center network topology:
•  » » 5 months ago, # ^ |   0 aap bahut badhiya kaam karte hai
 » 5 months ago, # |   0 Wow, so many prizes.
 » 5 months ago, # |   0 what big prices!
 » 5 months ago, # |   0 We are waiting!
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   0 They aren't rated, and after all, it doesn't hurt to try. You might learn something while participating after all!
•  » » » 5 months ago, # ^ |   0 Yes thats true.. Thanks i will try
 » 5 months ago, # |   0 Is the Registration finished because I can't participate
 » 5 months ago, # |   +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?
•  » » 5 months ago, # ^ |   0 sucks to be a non-ICPC participant (freshman next year)
•  » » 5 months ago, # ^ |   +3 We don't need to actually participate in the 2022 ICPC, right? Just need to have an ICPC account to be eligible?
•  » » » 5 months ago, # ^ |   +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/registerAll the best for the competition!
•  » » » » 5 months ago, # ^ |   0 my codeforces email is also icpc user name, does it ok now? should i do some extra work to associate them?
•  » » » » » 4 months ago, # ^ |   -10 Please link your ICPC account to the Codeforces account here: https://codeforces.com/settings/general
•  » » » » » » 4 months ago, # ^ |   +85 Unfortunately, I can't find where I can link my ICPC account using this link.
•  » » » » » » » 4 months ago, # ^ |   +1 Please check more details on your question in this comment https://codeforces.com/blog/entry/105097?#comment-956845
•  » » » » » » 4 months ago, # ^ |   +1 So, will you respond to the unavailability of account linking?
 » 5 months ago, # |   0 Wooow! The prices are very very interesting!
 » 5 months ago, # | ← Rev. 2 →   +26 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.
•  » » 5 months ago, # ^ |   +15 15 days. Blog has been fixed, thanks.
 » 5 months ago, # |   0 ..
 » 5 months ago, # |   +11 Is there a way for unofficial (without prizes) participation for Huawei employees?
•  » » 4 months ago, # ^ |   0 Yes, Huawei employees can participate without prizes!
 » 4 months ago, # | ← Rev. 4 →   0 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.
•  » » 4 months ago, # ^ |   +4 isn't it against the contest rules to ask questions about an ongoing contest?
•  » » » 4 months ago, # ^ |   +1 The question is about condition, not solution. I suppose it isn't against rule.
•  » » 4 months ago, # ^ |   +1 The sample output may not be the best solution to the sample input, they are just valid output to demonstrate how score is calculated.
•  » » » 4 months ago, # ^ |   0 Is the output valid if it don't minimize $RTsize$?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 yes. minimizing $RTsize$ is not a strict criterion for the validity of the output.
 » 4 months ago, # |   -25 Hey .. Can u give me down vote ? : )
 » 4 months ago, # |   0 can you add an explanation to the test 1??? or even a checker or even said the right answer
•  » » 4 months ago, # ^ |   0 You can download the test and review your output, it is actually wrong.
 » 4 months ago, # |   +18 "Only participants who entered a valid ICPC username (email address) during registration are eligible for recognition as a Challenge winner."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://codeforces.com/blog/entry/90185) but there is no such an option in the settings anymore.
•  » » 4 months ago, # ^ |   0 Where did you see that message? There is nothing in the rules about having ICPC username during registration.
•  » » » 4 months ago, # ^ |   +4 There is a link in the bottom of the post.
•  » » 4 months ago, # ^ |   0 Please check more details on your question in this comment https://codeforces.com/blog/entry/105097?#comment-956845
 » 4 months ago, # |   0 Will this be rated?
•  » » 4 months ago, # ^ |   0 No
•  » » 4 months ago, # ^ |   0 No unfortunately
 » 4 months ago, # |   0 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.
•  » » 4 months ago, # ^ |   0 This is not final test data.
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 but, there are some testcase in gp1 score is 99xxx，the n most 100000，after weighted, it most 30000
 » 4 months ago, # |   +33 Is it available to provide a grader for problem 1, GP 2? Thanks.
 » 4 months ago, # |   +26 Why the submissions were rejudged?
 » 4 months ago, # | ← Rev. 2 →   0 Are the current testing results that we see in the system final or will there be a separate testing after the competition ends?
•  » » 4 months ago, # ^ |   -8 Problem 2 has no hidden tests, the scoreboard shows final scores.
 » 4 months ago, # |   -12 Is it just me who keeps coming back every hour to see if any rated contest has been scheduled ?
•  » » 4 months ago, # ^ |   +3 Same lol
•  » » » 4 months ago, # ^ |   0 literally LoL """
 » 4 months ago, # |   0 Why nobody answer my questions?
 » 4 months ago, # |   +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.
•  » » 4 months ago, # ^ |   +24 I wish MikeMirzayanov could solve this issue .
•  » » 4 months ago, # ^ |   +29 Sorry for the ping but ICPCNews please solve the issue ASAP.
•  » » 4 months ago, # ^ |   +10 Please check more details on your question in this comment https://codeforces.com/blog/entry/105097?#comment-956845
 » 4 months ago, # |   0 it's great
 » 4 months ago, # |   -8 Rated or UnRated?
 » 4 months ago, # |   +29 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.
•  » » 4 months ago, # ^ |   0 What should I do if my email address is unavailable
•  » » » 4 months ago, # ^ |   0 Could you please elaborate? Which email address and where it is unavailable?
•  » » » » 4 months ago, # ^ |   0 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.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 deleted.
•  » » 4 months ago, # ^ |   +11 Will the notification be sent via email or Codeforces messages? When will the notification be sent?
•  » » 4 months ago, # ^ |   0 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?
•  » » 4 months ago, # ^ | ← Rev. 5 →   +18 All winners will be notified and additional week will be provided to correct ICPC account.Has anyone been notified ?
•  » » » 4 months ago, # ^ |   +11 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 ;)
•  » » » » 4 months ago, # ^ |   0 thanks
 » 4 months ago, # | ← Rev. 3 →   +35 When will the system test start？
•  » » 4 months ago, # ^ |   +15 Currently it says "final standings" on problem 1 and "system testing" on problem 2. Wasn't it announced the other way?
 » 4 months ago, # | ← Rev. 2 →   +11 Where is system test? ICPCNews
 » 4 months ago, # |   +11 When will the system test start？
 » 4 months ago, # |   +8 When will the P1's system test start？
 » 4 months ago, # |   0 Will it be evaluated as the last submission rather than the highest score?
•  » » 4 months ago, # ^ |   0 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.
•  » » » 4 months ago, # ^ |   0 I submitted the code for GP1 to GP2, and that's my last submission to GP2. It's so sad.
•  » » » » 4 months ago, # ^ |   0 What a pity!
 » 4 months ago, # | ← Rev. 2 →   +9 When will the system test end?
 » 4 months ago, # | ← Rev. 2 →   0 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). ?
•  » » 4 months ago, # ^ |   0 The same question! This is the first time I see this rule
•  » » 4 months ago, # ^ |   +3 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.
•  » » » 4 months ago, # ^ |   0 Yes, the test set is fixed, but which "solution" that will be tested? that's the question. The last submission or the best one?
•  » » » » 4 months ago, # ^ |   +3 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.
•  » » » » 4 months ago, # ^ |   +3 For the problem 2 the best solution will be chosen because there is no hidden testset.
 » 4 months ago, # |   +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?
•  » » 4 months ago, # ^ |   0 Could you also share your solution idea? Your score is also quite high :)
•  » » 4 months ago, # ^ | ← Rev. 2 →   +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.
•  » » » 4 months ago, # ^ |   +16 I thought about selecting parameters for each test independently, but decided that this is not fair. A little sad.
 » 4 months ago, # | ← Rev. 2 →   -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?
•  » » 4 months ago, # ^ |   +21 Choose one spanning tree of the graph , and do some greedy solution on the tree.
•  » » 4 months ago, # ^ |   0 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).
•  » » » 4 months ago, # ^ |   -8 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)
•  » » » » 4 months ago, # ^ |   0 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).
 » 4 months ago, # |   +18 Why do I get Judgement failed on my submission to problem 1?
•  » » 4 months ago, # ^ |   +10 Same but on problem 2
•  » » » 4 months ago, # ^ |   +3 Send links for submissions please
 » 4 months ago, # |   0 will we be able to submit additional solutions to the problem1 just to test out some other ideas on the full test data?
 » 4 months ago, # | ← Rev. 4 →   +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]
 » 4 months ago, # |   +33 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.
•  » » 4 months ago, # ^ |   0 I am thinking the same. As these are approximate algorithms, longer the time it can be run larger points can be produced. Running additional testcases after contest doesn't make sense for me as one cannot know the right balance whether to get larger points by running algorithm close to time limit or to sacrifice some points just not to get time limit exceeded after contest.
•  » » 4 months ago, # ^ |   +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.
•  » » » 4 months ago, # ^ |   +8 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.
•  » » » » 4 months ago, # ^ |   0 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.
•  » » » » » 4 months ago, # ^ |   +18 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.
•  » » » 4 months ago, # ^ |   +16 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.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 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".
 » 4 months ago, # |   +10 How to get my prize?
 » 4 months ago, # |   +2 What does the question mark in the leaderboard mean?
•  » » 4 months ago, # ^ |   +10 They're being retested. (Why some solutions are always being retested? They have been tested many times.)
•  » » » 4 months ago, # ^ |   0 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!
 » 4 months ago, # |   +10 ICPCNewsPlease 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.
 » 4 months ago, # |   -70 Please evaluate all submissions. It's so unfriendly to only judge the last submission, as the final test is unavailable to participants.
•  » » 4 months ago, # ^ |   +140 Many people used random solution.So it will be unfair to people with fewer submissions.
 » 4 months ago, # |   +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.
•  » » 4 months ago, # ^ |   +12 UNFAIR.
 » 4 months ago, # |   +2 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?
 » 4 months ago, # |   +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!
 » 4 months ago, # |   +16 Are these final standings? I found that scores didn't multiply by 0.3 and 0.7 for GP1 and GP2.
•  » » 4 months ago, # ^ |   0 The final result on scoreboard is already multiplied by the 0.3/0.7 coefficient.
•  » » » 4 months ago, # ^ |   0 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?
•  » » » » 4 months ago, # ^ |   0 A score of 90k does not mean the coefficient is not multiplied~As for rewards, pls be patient. It’s coming soon ^_^
•  » » » » » 4 months ago, # ^ |   0 Originally there was no multiplication coefficient, now it is rejudged.
•  » » 4 months ago, # ^ |   +3 Hey! Thank you for your attention. You were indeed right. I fixed this issue. Now everything is correct.
 » 4 months ago, # |   +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).
•  » » 4 months ago, # ^ |   +5 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.
•  » » » 4 months ago, # ^ |   +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.
•  » » 4 months ago, # ^ |   +48 Wow, you managed to understand the statement in less than one day? Respect, I was not able to :P
•  » » 4 months ago, # ^ |   +8 https://codeforces.com/blog/entry/105097?#comment-958999 You can find the solution of icecuber here. Unfortunately, it's not really fair and really interesting.
•  » » » 4 months ago, # ^ |   +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.
•  » » » » 4 months ago, # ^ |   +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.
•  » » » » » 4 months ago, # ^ |   +3 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.
•  » » » » » » 4 months ago, # ^ |   -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.
 » 4 months ago, # |   +31 I haven't received any message from Huawei , how do I claim my prize?
•  » » 4 months ago, # ^ |   +11 Me too. I think it's ok, and we should wait more.