platelet's blog

CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)
By platelet, 18 months ago, In English

Note the unusual start time of the round.

Hello, Codeforces!

Now that Gaokao is over, we are very glad to invite you to participate in CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!), which will start at 24.06.2023 17:05 (Московское время). You will be given 9 problems and 3 hours to solve them. The round will be rated for everyone.

All problems are written and prepared by Gary2005, Asuka, Crying, sjcsjcsjc, MonkeyKing, DerekFeng, KbltQaQ, ShmilyTY and me.

Statements and editorials will be available in Chinese (Simplified) after the contest.

We would like to give our sincere thanks to:

The main character of the problems will be Tenzing Tsondu.

We hope that everyone can enjoy the round! As this round is sponsored, everyone will have an opportunity to win some prizes!

Good luck!

UPD1: Here is the score distribution:

250 — 500 — 1000 — 1500 — 2000 — 2500 — 3000 — 3750 — 5000

UPD2: Tutorial is available.

UPD3: Congratulations to the winners.

  1. tourist
  2. maroonrk
  3. hos.lyric
  4. cnnfls_csy
  5. Um_nik
  6. DearMargaret
  7. jiangly
  8. potato167
  9. kotatsugame
  10. noimi

UPD4: Congratulations to the first solver of each problem.

A: alexwice
B: ksun48
C: PinkieRabbit
D: Um_nik
E: Qingyu
F: amenotiomoi
G: tourist
H: rain_boy
I: maroonrk (after contest)

UPD5: Chinese statements

UPD6: Chinese editorials

Some information from our title sponsor:

Hello, Codeforces!

We, the Ton Foundation team, are pleased to support CodeTON Round 5.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 5 will receive valuable prizes.

The first 1,023 participants will receive prizes in TON cryptocurrency:

  • 1st place: 1,024 TON
  • 2–3 places: 512 TON each
  • 4–7 places: 256 TON each
  • 8–15 places: 128 TON each
  • …
  • 512–1,023 places: 2 TON each

We wish you good luck at CodeTON Round 5 and hope you enjoy the contest!

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

Comments Comments (237)
| Write comment?
»
18 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Hope to become cm

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

Do I get TON

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

platelet orz

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

As a first time tester I really liked the problems and highly recommend to read all the problems!

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

As a tester, give me TON.

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

As a writer, give me TON.

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

As a writer, Gary2005 orz

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

Requesting to involve div2 testers.

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

    Am I a joke to you????

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

      In terms of your rating — absolutely :)

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

        "Our eyes can also disguise us sometimes!!" ...What a beautiful line , isn't it :)

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

As a tester, I recommend participation

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

platelet orz

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

Good luck with your Gaokao results!

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

https://www.youtube.com/watch?v=kg5AMPZ5NUM

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

Let's gooo! My favourite type of rounds (combined) back after a long while!!

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

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

As a TON, give me participants!

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

I got you all my mind.

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

As a participant give me frequent contest.

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it -79 Vote: I do not like it

.

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

Only one tester below CM? bad idea

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

As the author mentioned Gaokao, Gaokao results will be published during the contest for many areas in China.

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

Why is the contest schedule so disoriented? Like we have 4 contests in a week(2 contests in a day) and then next contest is showing 3 weeks later :( ?

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

    Div. 1 (and Div. 1 + 2) contests usually appear on the schedule very early, unlike other contests. Like now, a Div. 1 + 2 has been announced 3 weeks into the future, but Div. 2, 3 and 4 contests usually appear on the contests page only 5 to 10 days before the contest. There is already an EDU round scheduled in 5 days after this contest and I am confident to say that there will be a lot more contests before that next Div. 1 + 2.

    → Reply
»
18 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Why can't Chinese statements be available during the contest :(

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

My unmatched perspicacity coupled with my sheer indefatigability makes me a feared opponent in any realm of human endeavor.

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

I will eat kebab before this round so I hope it will be tasty round

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

Can i get +53 this time? Or Will I fail again!!!

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

Please tell me what does "TON" mean?

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

    The Open Network (TON) represents an inclusive and decentralized internet platform, aiming to establish extensive cross-chain interoperability within a secure and scalable framework. It's primary objective is to process a very high TPS, ultimately catering to hundreds of millions of users in the future.

    Read their whitepaper for more!!

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

Which province are you from?

→ Reply
»
18 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I hope it is Mathforces! シ

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

I want to rating, o~.

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

A 5000 points problem! Sound scary.

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

As the main character of the problems,I wish you could get a positive delta.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    you're a liar. you're not a tester.

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

      I'm not a tester,but I appeared in the statements of the problems.That's the truth.

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

Interesting Score Distribution...

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

As a beginner, the score distribution seems pretty scary to me!! Looks like it would be a TON of fun.

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

I want to become Purple.Btw,score distribution is wild.

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

The first problem has 250 point. It does mean it is very very easy?

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

I hope this game won't be unrated and everyone can get good scores!

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

5000 score problem vs rainboy.

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

Hope to become expert!

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

TBH I got -50 or worse deltas at all of the previous 4 CodeTONs.
Now it's time to end this curse. GLHF!

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

For a moment, let me sum it up. It sums up to 1024*10 = 10240 TON approximately 1.2M Ruble/Rupee or 15k Euro or 100k Yuan every once or twice in a month! So much to support CF unconditionally. Ty Testers, setters and supporters!

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

    Might be even more if a lot of people are tied around 1023.

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

Do I get a ton of TON?

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

3 hrs is a bit large contest duration

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

Literally tourist is like gun machine every time I solve reload page tourist solves some problem tourist really a big orz i finished reading problem at the time tourist solve touxh problem

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

Aligaduo Tenzing Sang

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Too hard:(

ps: Didn't note the start time, so I started half an hour later:) No TON for me!

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

Thanks you for the contest, problem D and E were really amazing!

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

    Can you give a hint how to aolve E?

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 2   Vote: I like it -8 Vote: I do not like it

      Dp[i] equal to min cost to cover points in triangle with points (0;k), (i;0), (i, k-i). Answer equal to dp[0]. I used lazy segtree to update and query dp's values. You should think a little about dp transitions.

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

        And one more hint is that triangles in optimal solution don't intersect.

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

there's a different kick and nervousness getting hooked to the screen praying for NO FST, rank fall and being a CM after a long grind.

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

E is an amazing problem, I didn't expect the final dp to be so simple after reading the statement :)

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

In $$$E$$$. We have a line of $$$k + 1$$$ cells. We can paint some cells. Paint one cell costs $$$A$$$. There are segments $$$[l_i, r_i]$$$. For every segment, if we have not painted it whole, we pay additionally $$$c_i$$$.

How to solve it?

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

    Consider $$$N$$$ lines. One line needs a triangle with a minimum side equal to the length of it. This means the cost of type $$$1$$$ is (length*A), and it will erase all complete overlapping lines. The cost of the individual is 'c'.

    Then the segment tree and DP are enough where $$$Dp[i]$$$ represents the minimum cost to erase all lines in the $$$[0, i]$$$.

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

Is E just re-adjustment of points based on c[i], and merging the triangles after that? I hope it's not just that..

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

D was a bit hard to think about tbh.

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

    Hint?

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

    True, the statements pointed to a graph problem, but I couldn't find a proper conversion to a graph setup..

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

any hint for c.

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

How to solve G and H?

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +96 Vote: I do not like it

Orz hos.lyric

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

    Finally understand why this problem has a score of 5000. Orz hos.lyric

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

    I was just submitting stupid(?) heuristics, so I'd say orz problemsetters & testcases!

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

A and B were too easy but i really like C. It has been a while since i solved a dp problem

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

Good problems but for me D>E>F.

Maybe I'm Teasing GrandMaster Takagi-san now ^_^.

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

I liked the contest, but why was D worded so confusing :weary:

And now I fst... I love wasting 40min understanding statement that takes 10min to solve and 0 points in end.

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

    yeah same for me, and i don't know why i got fst, can anyone help me point out the mistake until tutorial is released. submission

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

How to solve F?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 4   Vote: I like it +24 Vote: I do not like it

    for an edge, if there are $$$s$$$ points on the left and $$$k - s$$$ on the right.

    $$$|k - s - s| = k - \min(s , k - s)\times 2$$$,which is because of $$$|a-b| = a+b-2\times \min(a,b)$$$.

    And $$$\sum \min(s,k-s)$$$ for the edges means the distance all the point gather at one point.

    You can enumerate the point and calculate the distance of nearest $$$k - 1$$$ points.

    Don't mind my broken English (:

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

can anyone help me with problem D?
3 4
11110 1
10110 1
10010 2

does not pass the first case

4 4
11110 1
10110 1
10010 1
10010 1

passes the first case

but both the answer are same.. just converted the last t from 2 to 1.. t can be unique for each set.. then what is the problem??

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    You reversed the two numbers in the first row. You should first output the total time, and then output the number of games.

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

    your printing order is wrong. First you have to print total time used in games and then the no. of games. you are printing in opposite order. It should be 4 3 11110 1 10110 1 10010 2

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

About problem $$$D$$$. It's "base" it nice. It was funny to notice after 10 minutes, that I'm just simulating dijkstra on paper.

Though, the format of problem is very bad. It was harder to understand, what am I asked to print, and how that $$$n^2$$$ is related to that. It would be better to just make something like $$$\sum_{i \in [1, n]} c_i \le 10^5$$$ and print in any format. Or print for everyone, how much time we can take him to set.

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

Video solutions A. Tenzing and Tsondu

B. Tenzing and Books

C. Tenzing and Balls

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can C be solved using recursive dp??

mine was giving tle https://mirror.codeforces.com/contest/1842/submission/210936974

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

Wonder how many people could prove the solution of A...

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

    Yeah, I tried around 15 minutes, then observed that sum seemed to be the decider, since it was A, just went with it without testing the logic because I was already quite late and it seemed like something that could be the logic of A. lol.

    → Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 4   Vote: I like it -9 Vote: I do not like it

    Ignore my dumb comment. should have checked carefully before posting. Understood that it indeed depends on the sum now.

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

      It depends on sums, and in if they are equal the game will be draw. In this example the arrays would look like this:

      Starting arrays:

      • 1 2 3
      • 2 2 2
      1. Move
      2. Move
      3. Move
      4. Move
      5. Move

      Because after every move the ability not only from weaker monster will be changed but also from stronger one.

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

    I think the "proof" is that any attack maintains the sum of strength on both sides. Since every attack the unit with smaller strength dies (that side loses that strength from their sum), and dishes out its strength in damage. So every attack both sides lose the same amount of strength.

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

    It’s actually pretty easy. After every move the total sum of each does not change. Therefore the final result can be determined solely based on total sum

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

I submitted problem B via codeforces.com and m3.codeforces.com and I got accepted in both, however the system subtract 50 points of my problem B' score

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

    because resumbitting substract 50 points too.

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

    You submitted in different languages so that's a different submission, even though the text is maybe the same.

    → Reply
»
18 months ago, # |
  Vote: I like it -28 Vote: I do not like it

feeling sad didn't get TON.

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

Problem C is somehow similar to: https://mirror.codeforces.com/problemset/problem/1788/E that I just need to modify a little bit.

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

    what was your approach to solve this problem

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

      Using dynamic programming. Let dp(i) is the maximum number of balls Tenzing could remove until i^th prefix. The transition is sinple. For the i^th ball, we can decide whether to choose it or not. Then dp(i) equals to maximum between dp(i — 1) if you don't choose the i^th ball, and max(i — j + 1 + dp(j — 1)) over all j < i, a[j] = a[i] if you choose it.

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

        how can you choose for all j < i , a[j] = a[i] ??? that will become N ^ 2 . You must have used some optimisation, in case your solution got accepted.

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

          As you're iterating over the array, for each value x, set $$$m[x]$$$ to be the maximum of $$$-j + 1 + dp[j-1]$$$ for $$$a_j = x$$$ seen so far. Because then for $$$dp[i]$$$, you can just say $$$dp[i] = \max(dp[i-1], i + m[a_i])$$$.

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

          Yeah, I didn't mention the optimization on purpose cause I just want to give a thorough dp idea. Of course, it's O(n^2) if you traverse all j, and you have to do something to find max(dp(j — 1) — j) efficiently. How people optimize it will be based on each one.

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

After this contest, Litang and tenzing's story will be much more popular than before.

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

When I read the statement about tenzing, I hope someone can give me a smoke.

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

The problem D without clarification was difficult to understand, but adding an explanation along with the problem statement would have been very helpful for many people.

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

What is orz ?

→ Reply
»
18 months ago, # |
  Vote: I like it -6 Vote: I do not like it

what is testcase 39 for D?

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

Finally CM (hopefully).

Well it seems like a long journey but probably it's even a longer path ahead. Here's what I learned in this journey.

  • Practice and consistency are your friend.
  • Not every contest would go same so stay ground yet avoid being demotivated
  • helping people out is one of the best ways to learn
  • Rome was not built in a day.
  • Path becomes easy when learning becomes joyful.

All the best everyone. wish you positive deltas in the future :)

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

tourist Orz

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

Some feedback on the problem set:

  • A: Great problem! Easy, still requires to notice something.
  • B: Standard, I did not really like it.
  • C: Nice problem (it feels like I met this exact problem in the past, but it might be a false memory). Initially I thought that some kind of data-structure would have been necessary, but it turns out to be just a few lines of implementation.
  • D: Cool problem again. I got stuck with the usual long long vs int bug.
  • E: Standard problem. I needed a sum/min segment tree and instead of implementing it I asked chatgpt to provide one (hopefully not violating any rule?). Then I lost 40 minutes because of an off-by-one in my part of the code. (which had less than 20 lines...). The issue was that I was not sure about the correctness of the segment-tree provided by chatgpt and thus I started debugging it even though it was perfect.
  • F: Loved this one. I got the correct idea after 20 minutes, then the implementation was straightforward.
  • G: The statement is not particularly interesting. I thought about this one for 40 minutes, without having any good idea. When I started thinking about it, I assumed that I would have solved it before the end of the contest... I was wrong.

Overall the problems were very nice and, even though my performance was underwhelming, I liked participating. Thanks to the authors.

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

    Thanks for your feedback!

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

    I don't know if you will agree, but I think H is the best problem in the contest. Please try it :)

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

      It is a fantastic problem indeed! Thank you for suggesting it.

      There is a bit of magic going on in problem H. After reading it I immediately thought "This must be a technical thing about computing the measure of an arbitrary polytope", I was wrong.

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

Did any one solve C using dp (recursively)?

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

    you can have a look https://mirror.codeforces.com/contest/1842/submission/210938852

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

    // you can solve this using 2 state dp


    ll recu(ll it,vector<vector<ll>>&v,vector<ll>&a,vector<vector<ll>>&dp,ll state){
    if(it<=0){
        return 0;
    }
    if(dp[it][state]!=-1){
        return dp[it][state];
    }
    ll ans=0;
    ll i1=lower_bound(v[a[it]].begin(),v[a[it]].end(),it)-v[a[it]].begin();
    if(state==0)
    {
        ans=max({ans,recu(it-1,v,a,dp,0)});
        if(i1!=0)
        ans=max(ans,recu(v[a[it]][i1-1],v,a,dp,1)+(it-v[a[it]][i1-1]+1));
    }
    else{
        ans=max(ans,recu(it-1,v,a,dp,0));
        if(i1!=0)
        ans=max(ans,recu(v[a[it]][i1-1],v,a,dp,1)+(it-v[a[it]][i1-1]));
    }
    return  dp[it][state]=ans;
}

void solve(){
        ll n;cin>>n;
        vector<ll> a(n);
        vector<vector<ll>>v(n+1);

        for(ll i=0;i<n;i++){
            cin>>a[i];
            if(v[a[i]].size()!=0){
                if(v[a[i]][v[a[i]].size()-1]!=i-1){
                    v[a[i]].push_back(i);
                }
            }
            else{
                    v[a[i]].push_back(i);
            }
        }

        vector<vector<ll>>dp(n+1,vector<ll>(2,-1));
        cout<<recu(n-1,v,a,dp,0)<<endl;

  
}


signed main(){
ll t;
cin>>t;
while(t--){
     solve();
  }
    return 0;
}
    → Reply
»
18 months ago, # |
  Vote: I like it +13 Vote: I do not like it

My python solution for D got accepted during contest, but during system testing it got stuck in TLE. My week is ruined now.

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

    Hey, sorry I didn't get to answering your question from before.

    It's on you to research/test how any code you didn't write will perform. Python is a lot of someone else's code, with their work, wins, but also their assumptions, mistakes, and tradeoffs... and there are multiple implementations (cpython vs. pypy) each with their own characteristics. If such research is beyond your level of motivation, then c++ might spare you some friction in cp, but a lot of the issues exist in every language -- some are just taken care of due to c++'s popularity in cp (like custom stack space for deep recursion) while others still need research anyway (fast IO copypasta)...

    I'd start at "just use pypy-64" and "substitute for input, input=sys.stdin.readline is a fine starting point but other options exist"

    Things to worry about down the line:

    • lack of sorted collection like std::map
    • upside-down codeforces meta which highlights esoterica like hash hacks on the lower/weaker divs
    • needing to outgrow recursion (or learn python-specific workarounds and tradeoffs)
    • once you do that: the lack of standard-but-technically-external python libraries that make nested-loops-on-a-multi-dimensional-array-named-dp less painful (due to layers of python indirection on top of the underlying indirection from using python itself)...

    Otherwise, congrats on recognizing what D was actually asking. Good luck with whatever choice you make, and hey, you don't need to pick only one, nor does your choice need to be permanent... otherwise I'd still be writing in ye old C and just not doing any hobby coding.

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

Could I have a hint for D and E?

I've noticed from people's code that D is something to do with shortest paths, but I don't see the connection. All I know is that if 1 and n are not in the same connected component you can play for infinity.

For E, I noticed that if two triangles overlap you can replace them with one big one but I didn't know what to do from there.

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

    Notice how a set 111...0 where only the last elenent is 0 is always a viable game. How many times can you play such game? Then try constructing a weighted graph. What are the weights of this graph?

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

    for a problem D: greedily play with every playable friend until there's noone playable

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

    I think a hint is that, if you have a path from 1 to n, any time you play a game, you have to decrease an edge on that path. Because 1 has to be included and n can't be included.

    → Reply
»
18 months ago, # |
  Vote: I like it -68 Vote: I do not like it

Since the language in problem D was a bit unclear, I request to consider those cases where time spent with animals is 0 to be not considered a game that is 1 should be in that constraints should be lifted.

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

I got the idea of F after about 25 minutes, but I tried solving it with dp on tree, ignoring that it can be calculated with bruteforce. I felt into a thinking trap that it must be difficult to implement because it is F.

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain question D? What do the restrictions exactly mean?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks. I think this was written in the notification we got during contest. Is there any way to look at a contest notification again after I close it?

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

        Yes, in the dashboard page, below the questions, all past notifications appear.

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

I did D with just straight forward greedy. The idea is that the order of the set doesn't matter. So you can just start from a set of friends of only 1, then remove the smallest edge out of the connected component and add the new friend into the CC. It should take at most N games to finish.

Got a small bug with edge of weight 0 and took a whole hour to find it. So sad.

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

Can anyone help me in problem C Code1 is accepted while Code2 is giving TLE?

Base logic for both are same the only difference in Code2 we are iterating for all occurrences but in Code1 101 occurrences from start and 101 from end.

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

    I had thought of using this solution, but it would have been a hack. this solution must be hacked.

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

In problem C, I saw some solutions using a global dp array and memset, still being accepted. I was wondering that since test cases are $$$10^3$$$ unlike conventional $$$10^4$$$, probably that is making them safe. But are the submissions not on the very edge, like $$$2 * 10 ^ 8$$$ computations in $$$1$$$ second ?

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

    Yeah Actually, I still couldn't understand the intuition behind iterating 100 times from front and back. Was it pure luck/ hit and trial or am I missing something here?

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

    memset is fast because it uses some optimizations under the hood. It is much faaster than a for loop

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

https://www.youtube.com/watch?v=JmQugCTIVgA My solution for C

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

How is the prize money distributed?

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

How can we receive the TONs?

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

    in the past, the wallet was requested later only from those who won something (cf message from system)

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

Any proofs why bfs from every vertex works for F?

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

    consider the most optimal group of K vertices, select the centroid V in it, when traversing, when we fix the vertex V as a centroid, after adding k vertices, we will find the same group because we choose the most optimal values for the centroid V

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

Can anyone prove or disprove/hack this solution for D:

I use the heuristic of picking the cut with the minimum number of edges. If an edge between two nodes goes to 0, I merge the two nodes into one node. Repeat until the graph is just 1 node.

My solution gets AC: https://mirror.codeforces.com/contest/1842/submission/210975963, but I personally think its incorrect.

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

Does G actually need formal power series/exponential generating functions? That was the only way I was able to make it make sense; it feels like there should be an easier way...

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

Got a runtime error (STATUS_ACCESS_VIOLATION) at D test 16. Does anyone know what STATUS_ACCESS_VIOLATION means? Is it the same as accessing out of range for array? The strange part is that the data range in 16 is the same as in previous tests.

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

    You are probably accessing lim_set.rbegin() when it is empty.

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

      Yeah. A stupid mistake T_T. Should check the boundaries more.

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

Hey I have an issue with my email, can i know how can i receive the prize if I don't have my email working. Can i get the prize through codeforces directly.

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

I got TON

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

When can we expect to get prize? Like what is the timeline of distribution since system testing is already over.

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

    Someone please mention whether they have received the prize or not.

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

    It takes a bit for them to reach out, maybe 1 or 2 weeks. I received prize in a previous round, it just takes a little bit.

    → Reply
»
18 months ago, # |
← Rev. 4   Vote: I like it +68 Vote: I do not like it

In fact, there is an $$$O(n)$$$ solution for problem E(submission). I have explained it in in the "Alternative Solution" section.

→ Reply
»
18 months ago, # |
← Rev. 3   Vote: I like it -13 Vote: I do not like it

My rating ...

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

Why are the ratings of this contest rolled back without notice.

→ Reply
»
18 months ago, # |
  Vote: I like it -13 Vote: I do not like it

why was this contest not rated, even though it is written it is rated? today i saw my rating and it dropped , and there is no update by organizers. please update!

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

    I was stunned after seeing such downvotes! even though my argument was correct. even Though Happy that ratings were rolled back.

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

      you said "why was the contest not rated", though it was and ratings usually get rolled back for sometime after the contest (I am not sure about the reason). Hence your comment got downvotes as you said something which was totally false, try asking questions next time when you are confused rather than jumping to conclusions, Maybe "why are the ratings rolled back" would've fetched correct responses :). Hope this helps.

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

why ratings of this are round taken away ? will they be returned?

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

Is the contest being reevaluated?

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

How will we receive the prizes won in this contest, that is, the TON cryptocurrency?

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

    I've heard they'll ask for wallet credentials in some time

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

The game added a lot of points and I'm very grateful for the game

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

I think I entered wallet correctly but I still not received TON in my wallet. When will the reward be received?

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

sus

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

.

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

Has anyone received their TON yet?

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

    Well. NO. Received msg from codeforces system before that I should update wallet address ahead of 7th July, but nothing received yet..

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

    I finally received it on August 11

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

Just noticed how similar problem C is to the N^2 DP solution of longest increasing subsequence!

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

When you're the $$$n$$$-th friend in 1842D - Tenzing and His Animal Friends :

→ Reply