Hello everyone!
We invite you to participate in the ICPC Challenge powered by Huawei that will run from 12pm CST May 26 — 12pm CST May 30, 2021. The Challenge problem is based on a real-world industrial topic, providing participants the opportunity to learn about cutting-edge technologies, and is open to the global community.
The Challenge problem will be given in a pure graph-theory form and is part of an algorithm for compiler/runtime co-operative optimizations crucial for high throughput of Big Data analysis frameworks running on multi-node clusters.
Technical support during the Challenge will be offered throughout the duration of the Marathon. The technical team will be reading all comments/questions and will be providing answers and support as soon as possible.
Prizes for the top 20 Global Challenge performers are as follows:
- 1-4: Huawei MateBook X
- 5-8: Huawei P40 Pro
- 9-12: Huawei Matepad Pro
- 13-20: Huawei Watch GT 2 Pro
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, at the discretion of the sponsor.
All participants with an ICPC username will receive a Challenge completion certificate. If you don’t already have an ICPC username, you can register for one here. Please link your ICPC account to the Codeforces account here: https://mirror.codeforces.com/settings/general
By participating in this Challenge, you agree to the Challenge Rules and Conditions of Participation
About the ICPC Training Camp hosted by Huawei
The ICPC Training Camp powered by Huawei is an international program initiated by the International Collegiate Programming Contest University Commons (ICPCU) and proudly supported by Huawei. Structured in 3 distinct phases that began in Jan 2020, the program has offered a series of multi-regional training activities with the main goal of providing an open environment and continuous learning opportunities for existing competitors through the best academic and industry practices. The training program has included lectures and analysis from ICPC community membership, including coaches from ICPC World Finals championship teams, a variety of computational problems to solve, and Industrial Challenges.
The ICPC Training Camp series has been offered free of charge for all registered participants, thanks to Huawei’s generous support.
Contact Us: If you have any questions regarding the challenge or training camp, please contact challenge@icpc.global.
Does this have rating?
Hoping for amazing problems:)
I cant understand the contribution system. Why am i -4 here.Its so demotivating out for a new person starting with codeforces. There should be a proper system for it. Make me more negative
i gave u +
Thankyou so much.But i think i need a lot of ton to get back to 0 and i swear i will never comment from that point
The contribution system is not that bad once you get used to it. And while writing this, your contribution raised to positive ;)
But why my contribution become -ve.... i just tried to help him.. :(
Can a usual contestant like me participate in this contest?
I am not familiar with this type of contest. How can I prepare for this contest If I need to learn something especially for this contest?
Do we have no contest for 3 weeks
I wish Huawei kept their promise the last time they did a Marathon. The last one was for ICPC world finalists. I can't say for everyone, but at least for me and many other contestants. We didn't get the watch prize although we achieved the needed rank. We weren't even contacted by Huawei!
I'm disappointed for being completely ignored and expected a company like Huawei to still deliver its prizes, or at least contact participants regarding any delays.
I got mine but the process is very chaotic. A local Huawei office sent me an e-mail and I needed to go there myself to collect the prize.
The only hope I had left was that they were planning to give the prizes at the world finals. Now, I can rest in peace knowing that it's not gonna happen :)
I think it depends a lot on the local Huawei office. My friends and I won quite a few prizes from Huawei. They were delivered on time by the Ukrainian office. But, yeah, not everybody is as lucky as we are :(
I'm one of the last year Marathon winners results and before doing a new Marathon, I will suggest Huawei to send last year prizes (for me Huawei Watch). I wrote about it several comments and they don't even respond.
Huawei : double or nothing XD
Will we not have a contest rated in 3 weeks?
waiting for a rated contest
when will we have rated contest?
Is it just me who keeps coming back every hour to see if any rated contest has been scheduled ?
why a lack of contests ?? i can't live without cf . please preapre a one"(
Will the submissions be in text, where we submit just the solution, like the previous Huawei ICPC Challenge? Or would we need to submit source code that will get judged with a time limit?
This is a google hashcode like contest right? Not ICPC style?
So we dont have direct access to the test cases? But we do have access to the feedback of it? IMO that is weird because one could try to get the hidden test case by checking the verdict of the submission, then running the problem locally, and then just submitting the best answer found
the heuristics contest at atcoder do a better job at it by only showing the final results on the hidden test case after the contest is over
I can hardly understand how do you do that? Yes, you can get the number of vertices and edges using bin search, but how do you get a full test (without sending 10000 submissions)?
I'm curious of what some of contestants' approaches to the problem. Can anyone share?
I can give you mine and they are in Youtube videos: https://www.youtube.com/watch?v=PIAThHyjwOY https://www.youtube.com/watch?v=pATUTEnjxAI
NVAL, tourist could you please describe how you jump from 10k+ to 9k?
How to achieve 10k?
1) Make a basic solution for 22100 points. Collect into one basic region all vertices that are always together on a full path (or together not on a full path).
2) Next, let "delete" all regions that consist of one vertex (so we can add them later to bigger regions). Let define cover of the basic region as all vertices with next property
Cover consist of several parents of the first vertex from basic region, some vertices between first and last vertices (from basic region) and children of last vertex (from basic region).
3) Now, find solution for the problem with balance equal 0.7. Simply go from smaller to bigger basic region (sorted by cover size), sort all free vertices from cover by weight and try to add free vertices to the region if it does not corrupt balance condition.
4) Finally, go from solution for 0.7 to solution for 0.9 balance. Again, go from smaller region to bigger. While balance < 0.9, delete vertex that contributes the most to the difference between min and max weight of full paths. It may require some optimization to get in TL.
This gives about 10500 points.
You can also try to add pairs of free vertices or add some randomization or use 2^n brute-force for small covers to get ~10200 score.
Main points:
1) Use brute-force for small regions (I did it for <= 18 elements).
2) Otherwise use greedy-algorithm for regions with less than 150 vertices (very important for final score):
- Firstly add all possible vertices in region.
- Remove or add vertex which change balance (shortest/longest) better than other variants. Do it while balance < 0.9 (including decreasing of balance too).
- Add vertex which change balance better than other. Do it while balance stayed >= 0.9. For that greedy-algorithm we must check possible balance for changing all vertices on each iteration.
- After that algorithm we can add some vertices by random swapping.
3) Use another more simple greedy-algorithm based on weights for regions more than 150 vertices. I have some problems with rational description for that part. When I tried to improve algorithm I got worst result (about 100-150 points). May be solution with local maximum for big regions degrade final solution.
4) We must make regions in the some order. On each step try to make region from maximum possible vertices (without looking to weights/balance).
5) Don't see on first x elements from step 4. I chose x=7 and jumped from ~9550 to ~9050 points after that improvement. I think that very big regions can degrade answer for a lot of small regions. Firstly I tried exclude only first biggest candidate and it gave me ~250 points. It was surprising.
Important hints:
- We must calculate shortest/longest paths very effective. I did it with O(N + M) with small constant , when N and M is number of vertices and edges in subgraph. Subgraph is vertices only in possible region (marked vertices with candidates).
- We can get some points with random and other magic constants. I think that value about 100-200 points.
Has anyone received prizes?
Yeah, got mine a few days ago.
Mine arrived last week. Took a while but no reminders from my side were necessary.