okwedook's blog

Codeforces Round #870 (Div. 2)
By okwedook, 12 months 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 wsyear
F triple__a
  • Vote: I like it
  • +136
  • Vote: I do not like it

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

div2 round witih more div1 testers. not good.

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

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

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

Looking forward towards a positive delta! Wish Every body good luck.

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

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

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

As a participant, I will appreciate the work of authors and testers. Thank you for the contest!

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

I hope being able to write short code for short statements , cuz short statement do not mean short code or being easy. However short statements is always good , good luck to everyone ! Thanks for authors )

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

Short statements -----> Good contest o(*^ w ^*)o

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

Good luck everyone!

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

.

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

The author asked us to read all problems. we will do. Good luck everyone!

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

No tester comment? Bad round.

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

No 'As a tester' comment, interesting

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

okwedook Orz

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

hoping for easy A this time ;)

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

          Welcome to pupils mate

          → Reply
          • »
            »
            »
            »
            »
            »
            12 months 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
            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it +4 Vote: I do not like it

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

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

      jinxed lol, A was too hard

      → Reply
      • »
        »
        »
        »
        12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck or everyone

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

thanks for this "....to create some good problems and clear short statements"

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

Wish i could do will in this Round

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

All the best for all participants

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

Good luck for all of us

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

Let's See How It Goes

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

Looking forward to be sad like him

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

Again hard 'A' :(

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

Div √2

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

Thanks for the toughest contest I have ever seen.

→ Reply
  • »
    »
    12 months 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
    • »
      »
      »
      12 months 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
      • »
        »
        »
        »
        12 months 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
      • »
        »
        »
        »
        12 months 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
        • »
          »
          »
          »
          »
          12 months 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
»
12 months ago, # |
  Vote: I like it -26 Vote: I do not like it

In B, if 'x' can be infinitely large print 0. anything divided by infinity will give remainder 0. So why can't infinity be answer for each case?

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

Yeah True! Trust Noone Even the contest.

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

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

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

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

Toughest A or Easiest C?

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

    C and D are like leetcode mediums

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

      exactly, Leetcode standard DP problem.

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

        Umm, which problem are you referring to ? is it about problem D? How exaclty dp works here, please explain!

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

          refer this

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

            Great solution bro, i really didn't ever think of this problem this way, like when taken == 0 we add current_index and when taken == 2 we subtract current_index beacuse (a_l + l) + a_mid + (a_r — r) , so yeah after coming to the equation above the problem looks quite simple.

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

    how to do B ?

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

      a ≡ b mod x if (a — b ) = multiply of x so for every i from 0 to n / 2 the value of x is a factor of arr[i] — arr[ n — i + 1 ] now you need a common factor between all (arr[i] — arr[ n — i + 1 ] ) values so take gcd

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

    Where can I get the solution please

    → Reply
  • »
    »
    12 months 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
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      The submission code is all public in fact. Just click on other's submission.

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

how to solve E?

→ Reply
  • »
    »
    12 months 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
    • »
      »
      »
      12 months 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
      • »
        »
        »
        »
        12 months 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
    • »
      »
      »
      12 months 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
      • »
        »
        »
        »
        12 months 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
        • »
          »
          »
          »
          »
          12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

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

How to optimize in Problem E

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

    use bitset

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

      Could you please explain further?

      → Reply
      • »
        »
        »
        »
        12 months 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
»
12 months 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
»
12 months 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    A looks cool isnt it?

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

      Honestly, it's absolutely disgusting :/

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

        Pupil Logic.

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

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

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

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

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

                  Thank you senpai

                  → Reply
  • »
    »
    12 months 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
»
12 months 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I think it's quite balanced for div2

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

Brutal Div2A

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

Any hints for C and D

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

          Ya thats what I meant , but later i realized it is not necesarily convex

          → Reply
  • »
    »
    12 months 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
»
12 months ago, # |
  Vote: I like it +6 Vote: I do not like it

great contest! thanks

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

Codeforces Round 657 vibes

→ Reply
»
12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it +107 Vote: I do not like it

Very cool problem

2023-05-05-192456

→ Reply
  • »
    »
    12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please give hints for problem E.

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

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

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

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

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

    Well it's less complicated than DP.

    Hint: look from middle.

    → Reply
  • »
    »
    12 months 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
  • »
    »
    12 months 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
»
12 months 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
  • »
    »
    12 months 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
  • »
    »
    12 months 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.com/contest/1826/submission/204635985

    → Reply
    • »
      »
      »
      12 months 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
      • »
        »
        »
        »
        12 months 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
  • »
    »
    12 months 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
  • »
    »
    12 months 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
»
12 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem B is from past contests.

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

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

      but i got WA while i found primes upto 1000 and got AC upto 1010 why this happened can you explain or i made mistake somewhere ?

      → Reply
»
12 months 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
»
12 months 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
  • »
    »
    12 months 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
  • »
    »
    12 months 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
  • »
    »
    12 months 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
»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Problem B was exanctly this problem

→ Reply
»
12 months 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
»
12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it -7 Vote: I do not like it

I hate E

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

good luck whoever is participating.

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

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

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

    really？ OAO

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

      Yes, I did the problem last month.

      → Reply
      • »
        »
        »
        »
        12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can problem B be solved using binary search ?

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

    can anyone tell what is wrong in my solution for problem b

    as we have to find max x the value of mod will always be between min and max of the array and if we take x greater than the Max element of the array then it will return same array itself so our domain of x is restricted to min and max of the array and now we can apply binary search and the checker function will check if the array that we have formed is pallindrome or not

    but

    3

    100 1 1000000000

    this Tc is giving wrong output

    can anybody tell what is wrong in my logic part ?

    https://codeforces.com/contest/1826/submission/204660439

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

It says it's rated but when I open my account it's viewed as unrated what's going on? (this is my first contest in a long time so idk how these work.)

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

My E solution with bitset took 2800 ms :(

→ Reply
»
12 months 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
»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Problem B was written in GYM before:

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

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

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

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

problem A so bad statement

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

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

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

Problem A.. Uff..

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

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

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

I can't solve some problem during contest, but after contest I had solve.

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

All problems are Good. I loved it.

→ Reply