div2 round witih more div1 testers. not good.

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

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

Ha felt like forever since the last contest.

Excited to take part in this contest.

No 'As a tester' comment, interesting

hoping for easy A this time ;)

Good luck for all of us

Looking forward to be sad like him

Div √2

Thanks for the toughest contest I have ever seen.

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

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

Toughest A or Easiest C?

• 13 minutes for D
• 26 minutes for C
• 10 minutes for B
• 45 minutes and 5 wrong answers for A.

Weirdest contest for me.

how to solve E?

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

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

How to optimize in Problem E

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

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?

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

Any hints for C and D

great contest! thanks

Codeforces Round 657 vibes

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

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

Very cool problem

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

can anyone please give hints for problem E.

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

Хотелось бы поменьше задач вида А-С и побольше вида Д-Е. Вцелом контест понравился, спасибо за труд)

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

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.

Problem B is from past contests.

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

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...

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.

Problem B was exanctly this problem

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.

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"

870A — Trust Nobody with Explanation

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

I hate E

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.

Accepted 1872 ms submission

Optimization 5 for getting 1200 ms

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

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

For E), I had the following DP recurrence:

and I think it runs in

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

because it looked suspiciously similar to longest increasing sequence.

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

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!

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

My E solution with bitset took 2800 ms :(

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.

Problem B was written in GYM before:

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

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

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

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

Problem A.. Uff..

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

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