okwedook's blog

Codeforces Round #870 (Div. 2)
By okwedook, 21 month(s) ago, In English

Hi, Codeforces!

I am glad to invite you to take part in Codeforces Round #870 (Div. 2), which will take place on May/05/2023 17:35 (Moscow time). The round will be rated for the participants with rating lower than 2100. Participants from the first division are also welcomed to take part out of competition.

You will be given 2 hours to solve 6 problems. All the problems were authored and prepared by me. One of the problems is interactive, please read the guide of interactive problems before the contest.

I would also like to thank:

Scoring: $$$500-1000-1500-2000-2750-3250$$$.

Don't forget to read ALL the problems. I wish you good luck and high ratings!

I tried my best to create some good problems and clear short statements, so I hope you'll enjoy the round and find a problem you like :)

UPD: Editorial

UPD: Winners and First-to-solve

Div1 + Div2

Place Participant
1 A_G
2 Rubikun
3 kotatsugame
4 244mhq
5 risujiroh

Div2

Place Participant
1 Perfectt
2 Hovery
3 UmajiHidakata
4 ivatopuria
5 wrihapcod

First-to-solve

Task Participant
A arvindf232
B A_G
C ksun48
D kaiboy
E NetSpeed1
F triple__a
  • Vote: I like it
  • +136
  • Vote: I do not like it

Comments Comments (134)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it -69 Vote: I do not like it

div2 round witih more div1 testers. not good.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    As a not tester and not participant and shin chan supremacist, gimme downvotes.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Contest with short statements. I hope we'll enjoy.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

Div.2 round with "3250" point's problem, quite interesting.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +25 Vote: I do not like it

Ha felt like forever since the last contest.

Excited to take part in this contest.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

No 'As a tester' comment, interesting

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

hoping for easy A this time ;)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    Don't hope for easy A. Hope for surviving hard A's. Hope for becoming strong.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      buddy if there will no easy A then the number of people participating in contest will be less (people just leave just by seeing A)eventually affecting the ranking

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Yeah. That's also a valid point. But I don't care tbh.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Welcome to pupils mate

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            I was planning for that. Now I will be rated for tomorrow's contest. Hahaha. I will see you guys on Div4. I will try to solve all problems within 1 hour 30 min.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it +4 Vote: I do not like it

              Well, all I can say is best of luck tomorrow :)

              → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      jinxed lol, A was too hard

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        At least I solved it and learned from it. that's what matters to me.

        I survived it lol.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck for all of us

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Looking forward to be sad like him

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +28 Vote: I do not like it

Div √2

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the toughest contest I have ever seen.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That definitely not the toughest. But yeah it was on the harder side for sure.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah 10 WA on A and for sure it is not a tough contest.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have seen harder A's than this. You just started in mid 2022. I am here since 2020. There was a contest in 2020, I don't remember both A and B were the 1500s and non-trival.

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Who said it was not tough? Maybe your English is broken. Read my comment again sir.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't have much to fix anything broken but you might need as you missed the line where I mentioned "I have ever seen." So please save your time and stop replying anymore you LOSER..

          → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Hardest A, A took me longer than B and C combined.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem E — F ratings are different from the blog post. Neither that it matters to me. xD ... cos I solved none of it.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Toughest A or Easiest C?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it
  • 13 minutes for D
  • 26 minutes for C
  • 10 minutes for B
  • 45 minutes and 5 wrong answers for A.

Weirdest contest for me.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    C and D are like leetcode mediums

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to do B ?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if it is already palindrome then answer will be 0 because you can take mod with any infinite value and thus answer will be zero in this case.

      Now check the pairs from start and end and store the absolute difference of these numbers in a vector or array. now print the GCD of all the values. Because gcd will give the same modulus to all pairs.

      Spoiler

      here you can refer my code

      Code
      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Where can I get the solution please

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do you mind sending me code for A,B,C? can you do that or that will violent the rules?

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Let's say there is an edge from $$$x$$$ to $$$y$$$ iff $$$a[i][x] < a[i][y]$$$ for all $$$1 \leq i \leq m$$$

    Building the graph can take $$$O(mn^2)$$$ time, but we can optimize it with bitset $$$O(\frac{mn^2}{64})$$$.

    The graph we have is DAG, so you can do dp.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Can you explain a bit more about how are you going to use bitset to optimize it?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        For each show, sort the models by their ratings.

        Now for each model $$$v$$$, we know all models $$$u$$$ (which form some prefix and can be kept in bitset) for whom there is no edge from $$$v$$$ to $$$u$$$. Delete those models from your adjacency list.

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Mine gets OOM when allocating bitset<5001>[501][5001]. I guess we need sqrt-decomp here?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You dont need to store bitset of all shows, you can create bitset<5001> [5001] for each show separately

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ooooooops! I think you are right. bitset<5001> [5001] is enough and I can do city-by-city.

          → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

RIP my rating. That first problem was brutal and then I struggled on the second after :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

1826B - Lunatic Never Content copied from https://codeforces.me/gym/102035/problem/I

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to optimize in Problem E

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use bitset

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain further?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        You sort the ratings of each city, for each city you start with a bitset full of zeroes, then you go from right to left updating the bitset and the adjacency list of the model you currently are updates g[model] &= city

        → Reply
»
21 month(s) ago, # |
  Vote: I like it -38 Vote: I do not like it

include <bits/stdc++.h>

using namespace std;

define int long long int

int32_t main() { int t; cin>>t; while(t--) { int n; cin>>n; int a[n]; for(int i=0;i<n;i++)cin>>a[i]; vectorv; for(int i=0;i<((n+1)/2);i++) { int k= abs(a[i]-a[n-i-1]); if(k==0)v.push_back(-1); else v.push_back(k); }

int ans=-1;
    int cnt=0;
    for(auto x:v)if(x!=-1)cnt=1;
    if(cnt==0)
    {
    ans=0;
    cout<<ans<<endl;
    }
    else if(cnt!=0)
     {
         vector<int>v1;
         for(auto x:v)if(x!=-1)v1.push_back(x);
        int ans=v1[0];
        for(int i=1;i<v1.size();i++)ans=__gcd(ans,v[i]); 
        cout<<ans<<endl;
     }

}

}

I am getting WA at 4 testcase please help me asap

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

So apparently every single one of the testers saw A and solved it and though that it's a good idea to put something like that in the contest?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    A looks cool isnt it?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Honestly, it's absolutely disgusting :/

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Pupil Logic.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You literally dropped to pupil 2 days ago bro, what are you on about xD

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            wait for today will become cyan again(i am quite confident).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh well in that case you're a big boy !

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                The more experienced you become, the better you realize no problem is bad, it's you who is not capable enough to tackle it.

                And yes no problem is disgusting sir. You are seriously denying all the efforts the author has put into making that problem. Believe me, I am working as a problem setter intern and it's not a cup of cake to come up with unique ideas, write test cases, handle exceptions, and handle wrong code. Authors should be praised more. At least they deserve constructive criticism.

                → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    actually, A was a different task when i tested, and probably a harder one.

    I feel both are fine for div2A though....

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

Difficulty jump from D to E is too much. Up till task D it feels like div 3

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I think it's quite balanced for div2

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for C and D

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A lot of testcases with big n, m should hint to you to think of a math solution. if m == 1, we can just print("YES"), otherwise,

    Notice that if n can divide any number from 2 to m, the worst strategy is to always choose the number of boxes that divide n, that way it will repeat forever. If not, you can never choose suitable boxes as they will all not divide with n.

    Therefore, we can just check if the prime divisors of n are all > m, if so, we print "YES" else print "NO"

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For C, do casework for m and n.

    For D, try to write the answer function in a different way.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is D can be solved using ternary search ?

      Isnt it f(len) = max1+max2+max3+len for all length a convex function

      I tried during contest but couldnt do. Can somebody let me know whether i am correct or not

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think it's max1+max2+max3**-**len. Not plus the length.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    C: how to make a tie? when it's possile to tie?

    D: Look from middle to both left/right sides.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

great contest! thanks

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Codeforces Round 657 vibes

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell where can I find some similar problem to practice :(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

F is an absolute joke. Just query y=0, x=0, y=240x

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +107 Vote: I do not like it

Very cool problem

2023-05-05-192456

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And just after that you got TLE on the same test. Really cool.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem A is very hard for me and i can't even solve A in the contest...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please give hints for problem E.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

C is easier than A,,,Hardest A ever...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Was D a dp problem ? Hope to become specialist this time.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well it's less complicated than DP.

    Hint: look from middle.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes it is dp problem.

    Till index i, suppose u have taken 2 values, what is the best you can do, => dp[i][2]

    and suppose till index i, u have taken one value, what is the best you can do => dp[i][1]

    fill in the DP from above state.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved i5 using DP, let dp[i][j] be the max sum that can be made using the first i light where we have picked j lights till now. j can be 1,2 or 3. Code

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

As a newbie, I started doubting myself when I was unable to solve A, but looks like it is really a tough problem. Now waiting for someone to post it's solution.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Enumerate possible answers and verify them one by one.

    Bonus: you can do better than pure brutal-force. Although it's not needed given the data scale.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can brute force on the number of liars. lets call this number x. We go from x = 0 to n

    So lets check, is 0 liars possible? 1 liar possible? is 2 liars possible? and so on. We run through the array, checking if arr[i] > x, that person is lying for that value of x, because they are saying that there are at least arr[i] liars. We increase the liar count

    Now, if the liar count == our projected value of liars x, we print x. Otherwise, we cannot determine the liars, so we print -1.

    https://codeforces.me/contest/1826/submission/204635985

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks for such a simple solution. I often do this mistake of over optimizing the first problems of contests instead of trying out bruteforce :(

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I kinda made that mistake as well, I kept trying to see a pattern and how to best determine the number of liars and so on.

        This is a good learning point for me as well, because next time if I cannot think of the optimal solution for A I will just bruteforce it if the constraints are good

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yea this A was a complete shitshow. Since it's been solved by less than 5000 people, I think this problem A takes the reward for the hardest A since America was discovered.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    after spending more than hour and 3 Wa the solution is very easy , you can just brute force all possible number of liars from i = 0 to i = n and count every one who said that there is a bigger number of liars as a liar(cnt++) if the counter of liars == i then thats your answer

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem B is from past contests.

Problem Link: https://codeforces.me/gym/102035/problem/I

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone have the same problem as me in C? I figured it out pretty quickly and tried using a sieve to implement it. Kept on getting TLE on 4. preset tho...

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I looked at your submission and you found primes up to $$$10^6$$$ when you only need to find primes up to $$$10^3$$$.

    This is because you only need to find the lowest prime factor, and the lowest prime factor of a number $$$n$$$ is at most $$$\sqrt{n}$$$

    As a result, in the worst case, you need to check every single prime up to $$$10^6$$$ for each test case. And there are roughly $$$8\times 10^4$$$ primes that you need to check in that case. Given that there are $$$10^5$$$ testcases, this is far too slow.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Yay, Pupil!!!

For me, A was quite impossible, I think I had a decent idea, but couldn't implement it. Spent at least forty-five minutes attempting it just to get nowhere. Similar to the last contest, A was really difficult to understand resulting in A being difficult for me and I ended up spending >15 minutes re-reading it over and over. Although, both B and C were far easier, all A, B, and C seemed to be fairly tricky.

Anyways, thanks for the contest, the problems were really enjoyable. I need to think about A more!

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

A: Brute force for all possible numbers of liars from 0 to n.

B: To make a[1]%x==a[n]%x we must have x is a divisor of abs(a[1]-a[n]). So the answer is the gcd of abs(a[i]-a[n+1-i]) for 1<=i<=n/2.

C: If m is a divisor of n, m can remain the same after voting, otherwise m must be decreased. So if m < the minimal prime factor of n, m will be decreased to 1.

D: Let the indexes of sights we pick are i, j, k from left to right, then definately we will let L=i, R=k. So we just need to find the minimum of b[i]+b[j]+b[k]-(k-i)=(b[i]+i) + (b[k]-k) + b[j], where i<j<k. We can do this by pre-calculating the prefix-maximum of (b[i]+i) and the suffix-maximum of (b[k]-k).

E: If model u can be ordered before model v, for all i we have r[i][u]<r[i][v]. So we can build a DAG (directed acyclic graph) in O(m*n^2), and we can solve the problem by toposort and dp. Naive approach will get TLE and we can optimize this solution to O(m*n^2/w) by bitset, which could pass the pretest (and hopefully system test).

PS: Is there any O(m*n) solution of E? I think there must be something faster than O(m*n^2) but I can't come up with it.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What I tried was, first sort all people by the first city. Now we have permutation [0,1,...N]. I sort this permutation by every city, while ensuring that inversions are always created and never destroyed. This is because for some person X > person Y, this should hold in every city. So inversion created in any one city always stays. After sorting by every city we can simply take LIS. But I didn't get AC

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I mis-implement the biset so it OOM for me... rather than solve the OOM issue, I chose to sqrt-decomp it but failed to finish before deadline. With sqrt-decomp it should get O(mnlogn, n^2, m*n*sqrt(n))~=O(m*n*sqrt(n)).

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It may seem obvious, but in problem A you can get non-brut force solution if you sort all numbers in non-ascending order and without loss of generality assume that liars told the first k numbers, and try to find maximum possible k.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

Problem B was exanctly this problem

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Is there any solution for problem E that is faster than O(n^2*m/w), like O(mn+n^2) ? I tried to find a O(m*n) solution to compute all pairs of i,j that j can go after i, but failed.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

B was google-able, solved it after finding this which is the first link when you google "largest number that gives same modulo for 2 numbers"

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

870A — Trust Nobody with Explanation

https://codeforcer.blogspot.com/2023/05/trust-nobody-870a-solution-in-cpp.html

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

I hate E

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

You can solve problem 1826E - Walk the Runway in $$$O\left(n^2 \times m\right)$$$ in C++ without bitsets. Based on naive $$$O\left(n^2 \times m\right)$$$ approach, you need to apply next optimizations one-by-one for getting 1872 ms.

Optimization 1
Optimization 2
Optimization 3
Optimization 4

Accepted 1872 ms submission

Optimization 5 for getting 1200 ms

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem C is copied from https://codeforces.me/gym/433264/problem/F

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    really？ OAO

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I did the problem last month.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please take a screenshot or something? cuz I am not in that group.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +27 Vote: I do not like it

I'm stupid and had to do a bunch of random tests for B to find out the set of possible answers for a mod x = b mod x are the factors of abs(a-b). From there, I didn't realize that it's literally just equivalent to GCD XD

Got TLE 8 on that sadge

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

For E), I had the following DP recurrence:

$$$\text{dp}[i] = \text{p}[i] + \max(\text{dp}[j] \; \forall j > i \land r[t][i] < r[t][j] \; \forall t < m)$$$

and I think it runs in

$$$O(mn^2)$$$

Never would have thought to use bitsets though, I was trying to optimize it to either

$$$O(n^2) \text{ or } O(mn \log n)$$$

because it looked suspiciously similar to longest increasing sequence.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

10134 — 6367 = 3767 participants (37.2%) can't solve a single problem!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem D, I made this 204647760 during the contest and after about 20 minutes I realized that it can be hacked with a test case like this:

1

100000

1 1 2 3 4 5 6 7 .....

The reason is that I use -1 to check if I visited a state in dp or not and the above test produces -1 a lot which mean the dp will recompute states which was computed before, so I made another submission to avoid this mistake.

But after the contest, I submitted the first solution again and it passed the tests of the problem with about 46 ms , I think that this test should be added to main tests!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked the contest, it was nice. But E is so bad

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

My E solution with bitset took 2800 ms :(

→ Reply
»
21 month(s) ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I found a tricky way to exclude those pairs without ordering fast: if a[i]<b[i] for evety i, then sum(a)<sum(b), min(a)<min(b), max(a)<max(b). Problem E, a 592 ms solution without using bitsets.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem B was written in GYM before:

B- https://codeforces.me/problemset/gymProblem/102035/I

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Ratings updated preliminary, it will be recalculated after removing the cheaters.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can D be done using ternary search https://codeforces.me/contest/1826/submission/204648453 Or binary search https://codeforces.me/contest/1826/submission/204631760

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

good contest, problems were quite interesting, i am able to prove my solutions of a b and c!

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem A.. Uff..

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone come up with a dp solution for problem d？

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

My code can pass the example on my computer but failed when testing. Can somebody help me ? My code

→ Reply