ICPC Challenge 2021: Marathon (powered by Huawei)
By ICPCNews, 4 years ago, In English

text

text

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.

Join Challenge

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.

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

Comments Comments (32)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does this have rating?

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

Hoping for amazing problems:)

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

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

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

    i gave u +

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

      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

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

        The contribution system is not that bad once you get used to it. And while writing this, your contribution raised to positive ;)

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

          But why my contribution become -ve.... i just tried to help him.. :(

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

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?

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

Do we have no contest for 3 weeks

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

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.

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

    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.

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

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

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

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

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

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.

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

    Huawei : double or nothing XD

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

Will we not have a contest rated in 3 weeks?

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

waiting for a rated contest

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

when will we have rated contest?

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

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

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

why a lack of contests ?? i can't live without cf . please preapre a one"(

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

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?

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

This is a google hashcode like contest right? Not ICPC style?

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

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

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

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

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

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

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

NVAL, tourist could you please describe how you jump from 10k+ to 9k?

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

    How to achieve 10k?

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

      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

      • if V belong to cover then any full path (containing V) also contains all vertices from the basic region

      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.

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

    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.

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

Has anyone received prizes?

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

    Yeah, got mine a few days ago.

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

    Mine arrived last week. Took a while but no reminders from my side were necessary.

    → Reply