chromate00's blog

The 3rd Chromate Cup Algorithm Division
By chromate00, 11 months ago, In English

Hello, This is chromate00 (a.k.a. hjroh0315 on BOJ). The 3rd Chromate Cup Algorithm Division will be held soon! All tasks are developed by me, and all tasks will have statements both Korean and English.

  • Date: January 7th (Sun), 20:00 ~ 22:30 KST (2 hours, 30 mins)
  • Tasks: 11 tasks. Each task has a score given, and the tasks are sorted increasingly in order of score. The score is proportional to the expected difficulty evaluated by the problemsetter and testers. Still, we suggest you to read each task at least once, the perceived difficulty may vary.
  • Difficulty: Bronze ~ Ruby in solved.ac tier (*800 ~ *3000 expected in Codeforces rating)
  • Penalty: Uses the same rule as AtCoder. Formally, the penalty is calculated by (Last AC time)+(Sum of tries before AC)*5 mins.
  • Language bonus: Language bonus for TL/ML exists for specific languages. See (link; Korean text) for details.
  • Standings Freeze: None.
  • solved.ac Profile Badge & Background: Each is given to participants who scored at least 250/1500 correspondingly. Please understand that the production/distribution may take two weeks or more.
  • Specs: There are at least one interactive task(s). We suggest that you read the guide (link) before participating in the contest.
  • Do note that this contest is not held as solved.ac Arena.
  • Score Distribution: $$$250-500-1000-1000-1250-1500-2000-2000-3000-4000-4000$$$.

This contest could be held thanks to the testers biximo dhyang24 eggx50000 naeby Stygian_Nymph utilforever, and also to Startlink for great services Baekjoon Online Judge and BOJ Stack.

The contest's Overview tab also contains the same information as above. If the Overview tab and the announcement have different information, the Overview tab will be considered as more recent.

About the raffle:

A total of 13 people will get a Mom's Touch Thigh Burger voucher. The probability is proportional to the score squared. Please understand that only people who reside in Korea currently or can use the voucher are eligible for the raffle. If you cannot use the voucher please inform us in the raffle announcement after the contest ends.

For people new to Baekjoon Online Judge: You may refer to https://help.solved.ac/en/arena/getting-started/link-account (read until the second to last section) for creating a new account and linking the account to solved.ac.

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

update: the contest date was mistakenly written as 13th, it is actually the 7th (today or tomorrow based on timezone). the announcement is fixed now

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

    Please comment 30 minutes before start of the contest for the reminder.

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

friendly reminder: Contest starts in 30 minutes!

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't see the contest in the solve.ac Arena :|, where should I register?

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest has finished! While the editorial is being prepared (Korean editorial is almost finished, English editorial may take up to 24hrs), please use the comments section to freely discuss about the tasks.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to see failed tests after the contest? I wrote a stress test, but could not get runtime from it

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

    Due to the limitations of Baekjoon Online Judge, not on the site itself. I could check your solution on Polygon if you want, though.

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

      that would be nice, thanks

      → Reply
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Summary of the verdict on Polygon
        → Reply
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah, that makes much more sense, thank you

          → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problems! Thanks for making me feel like I'm still capable of solving decently hard problems :)

Problem G is cute, never thought of this funny complexity.

Is J something smarter than making a network with m + maxc * 100 edges and running Johnson's on it?

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

    The essential solution for J is the same, except the graph may contain negative cycles. Our team checked that these two algorithms in specific pass the task.

    Algorithms

    However, other algorithms may pass as well if it can deal with negative cycles nicely.

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

      tbh that was one of the easier problems in the contest — you just replace edges where a is not zero with c edges, and run min cost max flow

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

      Ok, thanks. I guess I'm not that well-versed in what works fast in MCMF and what doesn't... I believe my solution is about $$$O(nm + \mathit{flow} \cdot (n + m \log m))$$$, where $$$m$$$ is with extra edges included, but I understand that it might be not fast enough.

      → Reply