i_love_penguins's blog

By i_love_penguins, 8 months ago, translation, In English

Hello, Codeforces! 😇

We are glad to invite you to participate in Codeforces Round 932 (Div. 2), which will take place at Mar/05/2024 17:35 (Moscow time) 🔥 😱 🤩

The round has been fully prepared by students of the School CPM 💓 (School of the Pedagogical Skills Center): IzhtskiyTimofey, AndreyPavlov, and myself. The theme of all the problems will be our beloved school 😈

This round will be rated for participants with a rating below 2100 😊 Participants with a higher rating can take part out of competition 😋

We would like to thank 💕:

You will be offered 6 problems and 2 hours to solve them! We tried to make interesting, beautiful, NP-complete problems with strong pretests 😁

Score distribution: $$$500 - 1000 - 1500 - 1750 - 2500 - 3000$$$ ✨

We wish everyone good luck in the round, and we would also like to wish good luck to the participants of the upcoming Open Olympiad in Informatics and ROI! 🥇

UPD: Editorial

UPD 2: Congratulations to the winners!

Div. 2:

  1. Sakura_lenlen

  2. keeping_practicing

  3. INeedCarb

  4. LJL_T

  5. yyyz04

Div. 1:

  1. tourist

  2. jiangly

  3. BurnedChicken

  4. m_99

  5. Sugar_fan

We apologize for the disbalance in our problemset. However, we hope these problem fun and interesting!

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

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Another Div2 !! YAY!

»
8 months ago, # |
  Vote: I like it +52 Vote: I do not like it

As a tester, I can assure you that all tasks are interesting and worth trying to solve.

Also GL to all participants :)

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

    hey how do i become a tester for a cf round?

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +16 Vote: I do not like it

      i wish you the best in your testing career!

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

      It seems to me that the author of the round should know you and trust you, that should be enough.

»
8 months ago, # |
  Vote: I like it +24 Vote: I do not like it

As a school cpm student i recommend you to participate >.<

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

    Is CPM some sort of online school ?

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

      there are both online and offline classes

      i study offline

»
8 months ago, # |
  Vote: I like it +141 Vote: I do not like it

As a top -1 contributor and tester of this round, I recommend you to participate in this round!

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

    Bro posted only one blog and got the worst downwote damn! X_X

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Another red flag

    I feel it is gonna be negative delta day :'(

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

      downvoted rounds are always fun

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it -15 Vote: I do not like it

        Yeah you will certainly learn something! Rounds are definitely fun irrespective of Delta, but check the link in red flag, you'll get ma point

»
8 months ago, # |
  Vote: I like it +65 Vote: I do not like it

In my opinion, the round is high-quality and has pleasant tasks.

Good luck to all participants!

»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester I highly recommend you writing this round!

»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

As a tester, I have enjoyed solving problems, and I hope the participants will enjoy it too!

GL HF!!! (◕ω◕)

»
8 months ago, # |
  Vote: I like it -50 Vote: I do not like it

don't trust these guys

»
8 months ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

yo

»
8 months ago, # |
Rev. 4   Vote: I like it -15 Vote: I do not like it

.

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

As a tester, I think everyone should write this quality round

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

Hoping for the best Div.2 round!

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

Will the contest have interactive problems??

»
8 months ago, # |
  Vote: I like it +88 Vote: I do not like it

Hope Um_nik can solve problem C.

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

Why is this not on the home page yet? This post would definitely decorate the home page with all these cute emojis!

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

    I think it takes some time for the announcement posts to be added to home page

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hope to solve A and B in this round

Good Luck for every parcipicant!

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Omg! So many emojis!

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Dahm the post is so wholesome

»
8 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

One of the most beautiful announcement ever!

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

Hopefully i will back my Specialist rank

»
8 months ago, # |
  Vote: I like it +28 Vote: I do not like it

emojiforces

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted]

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

What is NP complete problems

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

    Easiest class of problems that can be solved by simple bruteforce

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I also love penguins UwU.

»
8 months ago, # |
  Vote: I like it -18 Vote: I do not like it

orz penguin round!!! 

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

Another Div2 !! YAY!

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

emojis;)

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

Hope to see myself cyan!!

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Seems like SpeedForces looking at the score distribution

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

Emojis spoiled a very good blog :(

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

    yeah, I think there was a bit too much of them.

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

as always hope for interesting and SHORT STATEMENT problems!

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

Excited for a thematic twist! With problems inspired by your school, this round promises to be both nostalgic and challenging.

»
8 months ago, # |
  Vote: I like it +29 Vote: I do not like it

As best pop singer in Russia, i recommend you to visit my concerts (and ofc participate in this round)

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

this post so cutee XD

»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Why the announcement looks like copy pasta of instagram's comment section

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

bro used all his recently "used" emojis from his phone

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Legends say you'll turn gay after this round :v

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

this guys are cool i know

»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

need to see authors' faces to know if this contest is reputable

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

no interactive?

»
8 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can you make it a dating contest(blog has some lovey dovey emojis ) aviralarpan3301 any suggestions?

»
8 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Please upvote, thanks.

»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Don't use emojis again , please.

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

Hoping to improve Problem solving skills.

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I hope to retrieve my rate :(

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I wish the authors made us some easy C problems this time

»
8 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I hope everyone gains some rating this round! (even if its impossible)

»
8 months ago, # |
  Vote: I like it -12 Vote: I do not like it

is it just me or have Div2 contests become harder ;-;

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I wish the problem-setters specified that messages can be sent in any order in problem C.

It took me an hour and 3 WAs to realize that I was solving a much more difficult version of the problem.

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

C and D should be swapped

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

    I am sorry that C was harder than D. From testers' feedback the problem was even too easy for C, my apologizes

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

      Maybe include more lower rated testers next time

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

      i guess implementation was easy but but grasping the underlying logic may be challenging.

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

Problem c seems like binary search..

any hints?

»
8 months ago, # |
  Vote: I like it +24 Vote: I do not like it

D <<< C

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

Thanks!

»
8 months ago, # |
  Vote: I like it +19 Vote: I do not like it

C>D for me..

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

    Is c a dp problem

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      C was greedy with heap. You can simplify the summation into sum(api) + max(bpi) — min(bpi) and brute force all pairs of bp, adding the smallest apis in the range of [min(bpi), max(bpi)] until you can't add anymore without going over l. It can be done with a max heap.

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

      There is a fairly straightforward greedy solution.

      Re-order the messages so the values of $$$b$$$ are sorted in ascending order.

      Then if you want to pick $$$k$$$ messages in the range $$$[i, j]$$$, the minimum cost is just $$$|b_j - b_i|$$$ + the $$$k$$$ smallest values of $$$a$$$ in the range. Note that for a fixed $$$i$$$, this cost increases as $$$j$$$ increases.

      So we can start from each $$$i$$$ and iterate on $$$j$$$ and putting the values of $$$a_j$$$ in a multiset $$$S$$$. Then just remove the largest values from the set as long as $$$\sum_{x \in S}{x} + |b_j - b_i| \leq l$$$ and your answer is just the maximum number of values remaining in the set for any $$$[i, j]$$$.

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Why are we not subtracting b when deducting a. Why not take k smallest b along with a in that range

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

    How to do B ?

    My idea was looking for first element which is less than two occurence in the array.

    If occurence is 1 then answer -1,

    If occurence is 0,then construct two part from 0 to this element first then another portion after that,if possible answer is yes or no.

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

      what i did :

      find mex of complete array = mex_complete now find the first index, say ind from left till which the mex is equal to mex_complete now you have two arrays from index 1 to ind and ind+1 to n; check if the second array's mex is equal to mex_complete. if no then -1 else print the indexes of above two arrays.

      Though I wasn't able to solve the same during the contest as I couldn't implement it well :(

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

    D is basically math where you can solve in O(1) memory limit.

    The key equation is: (c+1)(c+2)/2 — each pair that will kill a number + pairs that kill two numbers.

    To calculate each pair that will kill a number, you find the pairs you can put to its left + the difference between that number and c.

    x-y and x+y will be either both even or both odds, so to find the number of pairs that kill two numbers, record the number of even and odd numbers and the calculate the pair combinations of each: ans+=(ll)((even-1)*(even)/2); ans+=(ll)((odd-1)*(odd)/2);

    The overall math would be this ten line code 249815852

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

Can C be solved with greedy?

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

This may sound like an excuse, but I spent much time trying to login to facebook

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

Damn I got pranked hard by C xd

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

Can someone explain why n^2logn solution fails for C for the given submission? https://codeforces.net/contest/1935/submission/249797192

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

C > D

D is some high school mathematics and I worked it out within 10min after a lengthy, failed debugging session on C. Yes, I did read C and D at the same time. The reason why I didn't try D earlier was that I got an idea for C that works in O(n^2) but is very implementation-heavy, and eventually I did not get C.

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    EDIT: Just realised that the pi's are not necessarily in increasing order :|

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

    Also I'm posting my WA2 submission for C here. I'll appreciate it if anyone would read through my code and give me a simple counter case:

    249821298

    Idea: sort messages by a (in a[n]) and b (in b[n]). Iterate over the lower bound of b(b[i]): { Iterate over the higher bound of b(b[j]). Add the bounding elements to sum and greedily choose elements with the lowest a (a[k]) which is within the bounds. If vis[x]=1, a[x] is not strictly inside the bounds; if sel[x]=1, a[x] has been selected. K is not reset because the choices will remain optimal for each j. } Finally check if the answer is 1 or 0.

    I think this should work within O(n^2) and should be optimal.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Input:
      1
      1 1
      1 1
      
      Correct Output:
      1
      
      Your Output:
      0
      

      From the statement: "Note that the time to read a set of messages consisting of one message with number $$$p_1$$$ is equal to $$$a_{p_1}$$$."

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

        if(a[i].val.first < l)if(a[i].val.first <= l) WHAT A STUPID MISTAKE

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

    high school??? kindergarten mathematics.

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

      kindergarten??? my newborn cousin solved it with ease.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem F, how do you create a valid set of edges in the $$$cost = (degree - 1)$$$ case?

The $$$cost = degree$$$ case seems much easier since for each [min_node, max_node] subtree range you can just sort the ranges in increasing order of min and then for each range except the first add an edge from [min_node — 1, min_node] ([min_node — 2, min_node] for the edge over $$$v$$$) to produce a valid tree.

  • »
    »
    8 months ago, # ^ |
    Rev. 6   Vote: I like it +8 Vote: I do not like it

    I manage to solve these cases with $$$O(n)$$$ constructive method.

    The case with no subtree ranges $$$[min_{node}, max_{node}]$$$ that $$$min_{node} < v < max_{node}$$$ is simple, otherwise denote the maximum value of $$$max_{node}$$$ from such ranges by $$$MAX_{node}$$$.

    Then for each rage $$$[min_{node}, max_{node}]$$$ with $$$min_{node} < v$$$, add the edge $$$(min_{node} -1, min_{node})$$$ if possible. And for each range with $$$min_{node} > v$$$, add the edge $$$(max_{node}, max_{node}+1)$$$ if possible or otherwise add the edge $$$(MAX_{node}, MAX_{node}+1)$$$.

    The correctness can by roughly explained. The ranges with $$$min_{node} < v$$$ except for the leftmost one connect to a left one. The ranges with $$$min_{node} > v$$$ connect to a right one, or connect to a range that pass through $$$v$$$. Thus all the ranges head to the leftmost one and the result graph forms a tree.

    You can check my submission for more details.

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem C was harder than D. Spent most of the time in C.(T_T)

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

Super Fast Editorial!!

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

D >>> C (°0°)

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

In C, did we have to find total time needed to read all messages optimally and then remove messages which take maximum time until time is >= l? or is this approach incorrect?

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

I had trouble solving B even after getting the correct logic.

I thought the array can be divided in 2 parts always if there was an answer. I calculated the MEX of the whole array. Now I divided the array in two parts of size i(left array) and n-i(right array), where 1<i<n . I updated the MEX of the left and right array in each loop and if they were equal printed the indices. Here is my code, can someone help :

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

void solve(int tt)
{
    ll n,x;

    cin>>n;
    ll a[n];

    map<ll,ll>mp;

    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
        mp[a[i]]++;
    }

    ll mex=n;
    for(ll i=0;i<n;i++)
    {
        if(mp.find(i)==mp.end())
        {
            mex=i;
            break;
        }
    }

    ll mex2=0;
    for(ll i=0;i<n;i++)
    {
        if(a[i]==mex2)
        {
            mex2++;
        }

        mp[a[i]]--;
        if(mp[a[i]]==0 && a[i]<mex)
        {
            mex=a[i];
        }

        if(mex==mex2)
        {
            cout<<2<<endl;
            cout<<"1 "<<i+1<<endl;
            cout<<i+2<<" "<<n<<endl;
            return;
        }
    }
    cout<<-1<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int T=1;
    cin >> T;
    for(int tt=1; tt<=T; tt++)
    {
        solve(tt);
    }
    return 0;
}
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Input:
    1
    3
    1 0 0
    
    Correct Output:
    -1
    
    Your Output:
    2
    1 2
    3 3
    
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got it. I was wrongly updating my mex value of left array. Thanks :)

»
8 months ago, # |
Rev. 24   Vote: I like it 0 Vote: I do not like it

nvm idk how to prove shit

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

    You need to try add edges $$$(r, r + 1)$$$ too.

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

      I can't think of a case where my construction would fail. The only place where it would add an edge of the form $$$(r, r + 1)$$$ would be when $$$x$$$ is rightbound for some segment. Could you give me a counter example if you have any offhand, my brain is fried from sleep deprivation atp QAQ

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

        You can read editorial, in which proves why it enough to add $$$(l, l - 1)$$$ and $$$(r, r + 1)$$$ edges

»
8 months ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Too hard for C. I get stuck for more than half an hour, then I just solved it using two segment trees.

Update: no need for segment trees, because when you calculate the range from i to j, you only need to take k-st minimum value, no requirement it must contain the ends. (Since if it does not contains the end, all of them will also appear in the smallest range)

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

    I was stuck for 1 hr and solved D in less time.

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

    How did you solved it using segment trees?

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

      I did 2d dp with a lazy segment tree where dp[i][j] = minimum score to take i values and taking index j. I used segtree to query for the min value of dp[i-1][k] where k < j to get the best for dp[i][j]. I needed to update ranges to account for the differences in b values.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think you should have swapped D and C. Nevertheless, tasks were very interesting

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I think latest trend is difficulty of D is less than C in div2. And System testing just after contest. :)

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

is Div2 start getting harder ?

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

    Div2 stopped being speedforces. Previous few contests were awesome.

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

Thanks for fast editoral!

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

Thanks for the contest, enjoyed all the problems.

»
8 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Me after solving B:

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Common in recent contests :

  1. Fast editorial
  2. Fast system testing
  3. difficulty of D is less than C.
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

By By Expert

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think D is easier than C problem.

»
8 months ago, # |
Rev. 3   Vote: I like it +6 Vote: I do not like it

[Deleted]

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

    smh even appeal copied from ChatGPT

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

    Why go to such great lengths to try to convince people you're not a cheater when you clearly are one? Literally, if you put as much effort into practicing and studying as you put into cheating you could actually become good.

    "Please look into this matter". I did and lo and behold, you've actually already plagiarized from the same person once before in round 930. This is their solution for problem B: 248943799, and this is yours: 248959942. That time around it was way more obvious as you had the same variable names, and same syntax throughout the code. Are we to believe that this time now it was just a coincidence? lol

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

why is this round listed as unrated in my profile even though this post says rated? do i need a rating before this contest?

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Before delta rating is updated , it always shows unrated in your profile. In fact , it is a real rated round.

    You just need to wait for some hours for rating changing this round.

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

Terrible luck with C and didn't even care to read D which was apparently easier today somehow :( Good Bye positive delta.

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

strong pretests? lmao. my second question passed on the 5 pretests and i got wrong answer on test 6

very very strong pretests! thanku very much

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

Good round overall, but problem C was a bit harder than usual (both the idea and implementation)

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

Great contest! Thank you.

My only comments are

  • It was not very clear that $$$p$$$ doesn't have to be increasing in problem C
  • Problem D is easier than usual
»
8 months ago, # |
  Vote: I like it -8 Vote: I do not like it

C is harder than D, but the score of C is lower than D.

Maybe I will never become a Candidate Master. :(

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

It was a great contest. Problem D was a bit easier than C (even had more accepts) which was great because it teaches us to not get stuck on a problem and always remember to read the next ones. (and yes I made that mistake too) Thanks for the effort to make this great contest!

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

    I just made a mislook at D as C and solve it in 10mins lol.

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

Can anyone please elaborate the solution to Problem:C by using Dynamic Programming ..

DP[i][j] — Minimum time required to choose any subsequences of Messages in [0...i] such that the corresponding length is 'j'..

At the end , the final answer is to find the Maximum length (LEN) for which there exists atleast one 'i' such that it satisfies the inequality : DP[i][LEN] <=l .

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

    I didn't submit the solution myself, but I proved it theoretically, aggregated solutions of problemsetters as well as participants, so I'm fairly sure it's correct, but you might want to treat it with more suspicion

    At first we sort messages by $$$b$$$ in increasing order.

    Let's denote $$$dp[i][j]$$$ — minimum time needed to see $$$j$$$ messages and the last message was $$$i$$$. It can be calculated as $$$dp[i][j] = a[i] + b[i] + min_{p<i}dp[p][j - 1] - b[p]$$$, if $$$j > 1$$$, and $$$dp[i][j] = a[i]$$$ if $$$j = 1$$$. The $$$min_{p<i}dp[p][j - 1]$$$ can be precalculated for each new $$$j$$$ using prefix minimum array.

»
8 months ago, # |
  Vote: I like it +38 Vote: I do not like it

No more contests lined up after this, what am I supposed to do now lol? I knew there were an awful lot of contests in February, March is going to be dry.

I will try to touch some grass this month, and maybe go on a hike.

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

    Great contest though, I had 2 wa's in A because I was using n instead of s.length() in for loop, a force of habit lol.

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

Great problems. Enjoyed E the most.

»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

people found C harder than D, but I found D much harder.

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

No upcoming rated contests :-(

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

If it is kept swapping problem C with problem D, it will eventually increase the ability to solve problems with D difficulty during contest. Thanks for doing that.

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

Any idea why the problem ratings have not been updated in so long? I still have no idea if the problems I failed to solve were genuinely hard or I am just a noob.

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

..

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

I was able to solve only 2 questions and 2nd one being at the end, but i will surely do the 3rd also in the coming contests.

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

Hello, can someone please identify what is the mistake with my implementation in Problem C? Any help is appreciated.

https://codeforces.net/contest/1935/submission/250036154

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

You too? Hahaha, it can be easily done by swapping two variables