platelet's blog

CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)
By platelet, 3 years 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 Jun/24/2023 17:05 (Moscow time). 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?
»
3 years ago, hide # |
 
Vote: I like it -28 Vote: I do not like it

Hope to become cm

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

Do I get TON

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

platelet orz

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +118 Vote: I do not like it

As a tester, give me TON.

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

As a writer, give me TON.

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

As a writer, Gary2005 orz

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

Requesting to involve div2 testers.

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

As a tester, I recommend participation

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

platelet orz

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

Good luck with your Gaokao results!

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

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

.

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

As a TON, give me participants!

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

I got you all my mind.

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

As a participant give me frequent contest.

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

.

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

Only one tester below CM? bad idea

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

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

Please tell me what does "TON" mean?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +25 Vote: I do not like it

Which province are you from?

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

I hope it is Mathforces! シ

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

I want to rating, o~.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Interesting Score Distribution...

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +117 Vote: I do not like it

5000 score problem vs rainboy.

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

Hope to become expert!

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Do I get a ton of TON?

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

3 hrs is a bit large contest duration

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

Aligaduo Tenzing Sang

→ Reply
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

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

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

    Can you give a hint how to aolve E?

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

D was a bit hard to think about tbh.

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

any hint for c.

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

How to solve G and H?

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

Orz hos.lyric

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +41 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it -28 Vote: I do not like it

feeling sad didn't get TON.

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    what was your approach to solve this problem

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← 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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        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
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          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
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What is orz ?

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

what is testcase 39 for D?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

tourist Orz

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +25 Vote: I do not like it

    Thanks for your feedback!

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Did any one solve C using dp (recursively)?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +2 Vote: I do not like it
    Spoiler
    → Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

How is the prize money distributed?

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

How can we receive the TONs?

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

Any proofs why bfs from every vertex works for F?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

I got TON

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it -13 Vote: I do not like it

My rating ...

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

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

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
»
3 years ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

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

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

Is the contest being reevaluated?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

sus

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

.

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

Has anyone received their TON yet?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +10 Vote: I do not like it

When you're the $$$n$$$-th friend in 1842D - Тенцинг и его друзья животные:

→ Reply