Codeforces Round #808

2 years ago, # |

Hopefully I don't lose expert.

→ Reply

2 years ago, # ^ |

Same! I also just recently got it, we are living on the edge here. Good luck!

→ Reply

2 years ago, # ^ |

yeah you too man.

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Well, that definitely didn't go very well... I'm lucky I won't drop to Pupil after this round.

Guess these will be my last words as an expert in the foreseeable future :/

→ Reply

2 years ago, # ^ |

Same man, I think I've got a valid sol for C (after the contest!) I got seriously unlucky lol.

→ Reply

2 years ago, # ^ |

I feel you. It's funny we fell down to very close ratings too. Better luck to us on #809 I guess. The journey back to expert begins!

→ Reply

2 years ago, # ^ |

yes imao. Time to start upsolving!

→ Reply

Imdie

2 years ago, # ^ |

Hopefully I don't lose CM

→ Reply

2 years ago, # ^ |

Another one bites the dust...

→ Reply

FairyWinx

2 years ago, # |

Respect smg23333!!!!

→ Reply

jjang36524

2 years ago, # |

← Rev. 2 →

+18

Wish you all wouldn't gain negative ratings in this round!

So this is unrated?

→ Reply

maintain0original

2 years ago, # |

One of my curious questions： How to become a Codeforces Round tester? Sounds interesting

→ Reply

Abito

2 years ago, # ^ |

You have to get invited by the writers

→ Reply

Azusamitsusa

2 years ago, # |

+28

I can't wait to see jiangly's performance!

→ Reply

784

2 years ago, # ^ |

I can't wait to see tourist's performance!

→ Reply

Hozifa-Abulyaman

2 years ago, # ^ |

← Rev. 2 →

+22

Spoiler

→ Reply

2 years ago, # ^ |

+13

In yesterday's contest it took me almost 2 hours to solve C. And then I looked at the scoreboard. tourist solved C in just 2 mins.

Man how!!! Is he not human???

→ Reply

EarthMessenger

2 years ago, # ^ |

-10

jiangly will take the first place!

→ Reply

badluck_1441

2 years ago, # |

+36

Today is my birthday. Hope this contest is as special as my birthday

→ Reply

2 years ago, # ^ |

All the best to you and to everyone else!!

→ Reply

Great_20

2 years ago, # ^ |

happy birthday dude

→ Reply

winterfire

2 years ago, # |

+10

respect++ for smg23333

You can take away my house, all my tricks and toys. One thing you can't take away, is my csgo time. ~ Iron Man

→ Reply

2 years ago, # |

It says it is theoretically possible that no one gets negative rating.

Someone knows how?

→ Reply

harshaa05

2 years ago, # ^ |

The scoreboard has participants with non-increasing order of rating.

→ Reply

i_d_o_n

2 years ago, # |

← Rev. 4 →

+72

→ Reply

2 years ago, # ^ |

He will reach 4000 before I reach 2000 XD

→ Reply

hbhz_zcy

2 years ago, # ^ |

before seeing tourist reaching 3979

→ Reply

2 years ago, # ^ |

yes

→ Reply

i_d_o_n

4 months ago, # ^ |

Finally it's fulfilled

→ Reply

018429

2 years ago, # |

wana to be a Specialist ... ovo ...

→ Reply

AboNageh

2 years ago, # |

← Rev. 3 →

-8

Deleted

→ Reply

AboNageh

2 years ago, # |

← Rev. 2 →

-8

Deleted

→ Reply

Petertromso

2 years ago, # |

Is there a way to find out if a specific user is registered for a contest (before the contest begins)?

→ Reply

BurningRaven

2 years ago, # ^ |

Add the user to your friends' list, and see all your registered friends. I don't know a better solution lol

→ Reply

Petertromso

2 years ago, # ^ |

Yes, thanks, I didn't know about the registrants page!

→ Reply

Jhin

2 years ago, # |

← Rev. 2 →

let's see how bad I'm going to do after solving only 100 problems this year and the last submission was more than 2 months ago and the only algorithm i still remember is implentation

Edit: Well I started with C and it was a bad plan

→ Reply

HaitangSuki

2 years ago, # |

+175

Is this div.0?

I've checked the title of this contest for 3 times, I think this is div.1 but the problems are more like div.0.

→ Reply

k1r1t0

2 years ago, # |

+89

→ Reply

SalmaHatem_

2 years ago, # |

+13

"Wish you all wouldn't gain negative ratings in this round!" Wow!! I think all will gain negative ratings in this round XDXD

→ Reply

2 years ago, # ^ |

Me for sure negative.

Sed

→ Reply

shifucracker

2 years ago, # |

It just feels bad when i am a second year CS university student and can't solve A.

→ Reply

alberth4n

2 years ago, # ^ |

oh, I thought I'm the only one who can't solve A problem, it's hard as """"

→ Reply

Aravind

2 years ago, # |

God, I felt so useless when I took that much time to solve A with solid proof, until I saw comments. Feeling so idle in this contest :)

→ Reply

shifucracker

2 years ago, # ^ |

-22

How'd you solve it?

→ Reply

2 years ago, # ^ |

That's cheating, my friend. Texting during the contest about problem solutions.

→ Reply

XG0000

2 years ago, # |

+22

Can't solve 2C. Lower rating :(

→ Reply

reeWorld

2 years ago, # ^ |

+11

me too :|

→ Reply

Individual

2 years ago, # ^ |

-8

Binary searching for the answer almost seems like a cheat to be honest.

→ Reply

baiABC

2 years ago, # ^ |

me too :(

→ Reply

proof_by_ac

2 years ago, # |

I don't know why my codes for A,B are WA

→ Reply

Omar_Hafez

2 years ago, # |

← Rev. 3 →

-11

One of my worst contests ever! I will never join Chinese contests again.

The contest is not balanced. The last Div2 round was very balanced but this contest is just a fast coding contest with some sh!t.

→ Reply

2 years ago, # ^ |

It doesn't mean all Chinese contests are like this one.

→ Reply

Omar_Hafez

2 years ago, # ^ |

-18

I hope so.

→ Reply

TheStrongest

2 years ago, # ^ |

What are you saying. If you solve the problems normally, the round will be cool. The problem is not in the round, but in you. It's not speedforce. I agree, maybe we need to swap A and B, but no more!!!

→ Reply

2 years ago, # ^ |

-10

Why do you think so? I also think this round is not good enough(Exactly last round too),but it is absolutely not a fast coding contest.

→ Reply

notstoppingever

2 years ago, # |

From Newbie to Pupil to Specialist to Pupil to Newbie. What a Journey :)

→ Reply

AdiMall

2 years ago, # ^ |

Lol, see mine

→ Reply

notstoppingever

2 years ago, # ^ |

Dont give me that Hope :P Hope my graph goes like your April 2022 Graph

→ Reply

AdiMall

2 years ago, # ^ |

Hope my graph goes like my April 2022 graph :(

→ Reply

cp-is-fun

2 years ago, # |

There is a big gap between B and C

→ Reply

Omar_Hafez

2 years ago, # ^ |

exactly. The contest is not balanced

→ Reply

harsh__h

2 years ago, # |

+26

I am that point when there is nothing left to think about A, B, C

→ Reply

callmepandey

2 years ago, # |

+36

Every time a problem with '0' and '1' appears in a contest,

→ Reply

2 years ago, # ^ |

I can say same thing for me, but with $$$l$$$ and $$$r$$$, even though I solved B today.

→ Reply

2 years ago, # ^ |

Also when there is bitwise XOR or something like that

→ Reply

_darkSide

2 years ago, # |

+29

I can feel what Doremy is going through :(

→ Reply

haochenkang

2 years ago, # |

Can someone give me a hint for Div2D?

→ Reply

2 years ago, # ^ |

Note that there are always a lot of duplicates in the array

→ Reply

haochenkang

2 years ago, # ^ |

Thanks

→ Reply

defiler123

2 years ago, # ^ |

The process converges very quickly to all zeros because the number of distinct differences is $$$O(\sqrt{M})$$$ where $$$M$$$ is the largest element in the current iteration.

→ Reply

haochenkang

2 years ago, # ^ |

Thanks

→ Reply

MrOtter

2 years ago, # ^ |

hint

→ Reply

2 years ago, # |

← Rev. 4 →

A) Prove by AC, somehow works. Spent 20 mins on it, thought about rage-quitting without making submissions because it seemed like I won't be able to solve even A or B :lol:

B) Until the very end of the round I was convinved all elements also have to be distinct, so had no idea how to approach it and solved it only at the very end

C) Prove by AC, no idea why it work and whether it really works or problem just has bad pretests

D) A bit of reasoning lead to solution convincing enough. Quite a cute problem. Logic seemes easier than A/B/C

→ Reply

shashankag

2 years ago, # ^ |

Can you please explain your reasoning for D. Thanks

→ Reply

2 years ago, # ^ |

← Rev. 2 →

It is pretty much above

Note there cannot be many unique values in the array

Think how to avoid useless computations, repeating values don't add much new. They add zeroes and further zeroes again produce zeroes

So you just keep track of the number zeroes and observe how the process quickly converges on all the other values

Well, that's the idea.

→ Reply

ExpensiveAC

2 years ago, # ^ |

Same lol for B

→ Reply

Nyaruko

2 years ago, # |

+23

D1B editorial. Also it's my only authored problem lol.

→ Reply

Xixika

2 years ago, # |

"Wish you all wouldn't gain negative ratings in this round! (This is theoretically possible XD)", That's when we should have known that the contest would have been a disaster.

→ Reply

ExplodingFreeze

2 years ago, # |

← Rev. 3 →

For Div1C, is this wrong or does my implementation just suck?

Let T be the MST of the graph. Since edge weights are not repeated T is the only MST.

Then a root R is good if and only if for all edges (u, v), at least one of the following hold:

(u, v) is in T
When T is rooted at R, u is an ancestor of v or v is an ancestor of u.

→ Reply

smax

2 years ago, # ^ |

+18

Your idea is correct.

→ Reply

koqo

2 years ago, # |

Pretty brutal contest. Very humbling, can't wait for the editorial.

→ Reply

dukhi_insaan

2 years ago, # |

Whats wrong with my code? am using PB_dS with reverse traversing and putting max value + 1 every time i check more than q

Code


//----------------------------------<https://lnkd.in/eSDbra2>--------------------------------------
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("popcnt")
typedef long long ll;
typedef unsigned long long ull;
ll mod = 1000000007;
#define YES cout<<"YES\n";
#define Yes cout<<"Yes\n";
#define No cout<<"No\n";
#define NO cout<<"NO\n";
#define INF 2e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define lcm(a,b) (a/gcd(a,b))*b
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>

//----------------------------------Real game starts here--------------------------------------




void solve()
{
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;
    ordered_set oset;
    vector<ll> ans(n);
    ll k = 0;
    ll ma = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        if (a[i] > q)
        {
            if (k < q)
            {
                ll wo = oset.order_of_key(q + 1);
                ll w = oset.order_of_key(q);
                if (w == wo)
                    ans[i] = 1, ++ma, oset.insert(ma), ++k;
                else
                    ans[i] = 0;
            }
            else
            {
                ans[i] = 0;
            }

        }
        else
        {
            ans[i] = 1;
            oset.insert(a[i]);
            ma = max(ma, a[i]);
        }
    }
    for (auto x : ans)
        cout << x;
    cout << "\n";

}




int main()
{
    fast_cin();
    ll t = 1;
    cin >> t;
    for (int it = 1; it <= t; it++)
    {
        //cout << "Case #" << it+1 << ": ";
        solve();
    }
    return 0;
}

→ Reply

2 years ago, # ^ |

I did smth similar with seg tree but got 2 WA's, smh.

→ Reply

variety-jones

2 years ago, # ^ |

Take a look at Ticket 15819 from CF Stress for a counter example.

→ Reply

introart

2 years ago, # |

-21

Div 2 A is trash

→ Reply

2 years ago, # ^ |

You are absolutely right.

→ Reply

feblokas

2 years ago, # ^ |

С too

→ Reply

hhremaker

2 years ago, # ^ |

it just use a small trick, i think it's interesting

→ Reply

2 years ago, # ^ |

Just because you didn't solve it?

→ Reply

11thCommandment

2 years ago, # |

POV: no one can feel my pain The pain: 8 wrong submissions in B

→ Reply

dukhi_insaan

2 years ago, # ^ |

maybe u were thinking like me to put diff values in diff places :( 1 wrong submisson

→ Reply

2 years ago, # ^ |

In Global Round 21 I did 12 WA on test 2 submissions.

→ Reply

LeXuanSech

2 years ago, # |

Problem C is just like my friend. His name is Long. \

→ Reply

chenyanlin

2 years ago, # |

How can I pass problem 3？

→ Reply

Jhin

2 years ago, # |

How wrong is my solution for C ?

    #include <bits/stdc++.h>

    using namespace std;

    using ll = long long;

    using pi =pair<int,int>;

    #define f first



    # define be(v) (v).begin(),(v).end()

    #define eb(v)  (v).begin(),(v).end(),greater<int>()


    void jaaa(){cout<<"YES\n";}
    void nein(){cout<<"NO\n";}


    ll t,m,n,x,y,z,k,mn=1e9,mx,ans,a[500003],b[500003],c[500003],sum;

    int cnt;
    string s;




    int main()
    {

     ios_base::sync_with_stdio(false);



        cin>>t;


        while(t--)
        {
            cin>>n>>x;
            
            map<int,int>mp;
            for(int i=0;i<n;i++)
            {
                cin>>a[i];
                mp[a[i]]++;
                if(a[i]<=x)y++;


            }
            
            for(int i=0;i<n;i++)
            {

                int res=n-i-y;
               if(x>0&&a[i]>x&&x>=y-mp[x]&&res<=x)
               {
                   y-=mp[x];
                   x--;
                   cout<<'1';
               }
               else if(a[i]<=x)cout<<'1',y--;
               else cout<<'0';
               mp[a[i]]--;


            }
            cout<<endl;
        }



        return 0;
    }

→ Reply

lis05

2 years ago, # |

+22

Dear authors, shouldn't it be said in B that numbers can be equal? I love you very much, kissing you for the great time!

→ Reply

lkjhgfertyul

2 years ago, # ^ |

or at least give a sample case where numbers are equal

→ Reply

lis05

2 years ago, # ^ |

Exactly!

→ Reply

2 years ago, # ^ |

Well, it is our fault in a sense that we don't read statements properly. But yeah, they could make it clearer.

Solved B only at the very end because of it

→ Reply

29logN

2 years ago, # ^ |

I got 2 WAs in problem B because of this :')

→ Reply

javad_asadi

2 years ago, # ^ |

I did not solve the problem because I thought the numbers should be distinct. But that is my fault since it was not stated that they should be distinct. Even the examples did not have any equal numbers to make it clear.

→ Reply

lexiyvv

2 years ago, # |

No more algorithm-reading problems plz No more algorithm-reading problems plz No more algorithm-reading problems plz

→ Reply

2 years ago, # |

Ouch, the power outage plus the problems were the final nail in the coffin for me.

→ Reply

krishna_0_9

2 years ago, # |

-22

Sorry to say but A, B and D are one of the worst problems I ever solved. C was pretty good though.

→ Reply

2 years ago, # ^ |

It could have been much better if the authors asked just to output the number of solved contests, because then a DP approach with segment tree/SQRT-decomposition on top of it could work without greedy approach.

→ Reply

jai6

2 years ago, # ^ |

Can you elaborate on the DP approach?

→ Reply

2 years ago, # ^ |

← Rev. 3 →

Yes, of course. Let dp[i][q] be the maximum number of tested contests if we consider only first $$$i$$$ contests and after testing or skipping $$$i$$$th we have IQ exactly $$$q$$$.

At first, let's solve in $$$O(n^2)$$$.

for each i:

$$$a_i \le q$$$. for each q, dp[i + 1][q] = dp[i][q] + 1.
$$$a_i > q$$$. for each q, dp[i + 1][q] = dp[i][q], dp[i + 1][q - 1] max= dp[i][q] + 1.

Let's note that in the second case dp[i][q] + 1 is always no less than dp[i + 1][q - 1], so we can replace max= with =.

Okay. Now let's maintain the difference array of dp[i]: diff[j] = dp[i][j] - dp[i][j - 1].

When we increase i, we simply need to

1) add 1 to diff[a[i]], substract 1 from the last element of diff (this is the case $$$a_i \le q$$$

2) set the prefix ending with a[i] to 1 (case $$$a_i > q$$$)

This could be done using a segment tree or SQRT-decomposition.

Because q cannot decrease more than $$$N$$$ times, we can keep just $$$N$$$ values of diff.

But I don't see a way how to recover the answer...

→ Reply

2 years ago, # ^ |

You can record the pos of the dp-ans,and then output answers according to this.

→ Reply

2 years ago, # ^ |

Could you please elaborate on that?

I've explained my solution here.

→ Reply

2 years ago, # ^ |

Will,my dp solution is diff from yours XD

→ Reply

2 years ago, # ^ |

Could you please explain yours?

→ Reply

2 years ago, # ^ |

OK I just realized my solution may be not dp(although it is from dp sol), sorry :(

I just do it from n to i.

make c[i]=(a[i]>q)

Notice that if c[i]=1 and i is picked,then all of c[i]=1 in i+1 to n must be picked. (When I didnt notice this I use simply dp to do it)

set dp[i] as the best answer when you deal with i to n,and c[i]=1,and dp[i] can be claced by dp[nxt[i]] (nxt means the next 1's pos)

Here we can use BIT or priority_queue to solve. Actually it is not dp eventually (I came up with it according to O(nq) dp sol).

→ Reply

Uzumaki_TheLoser

2 years ago, # |

div2c was binary search ?

→ Reply

MrOtter

2 years ago, # ^ |

it can be done linearly with reverse order

→ Reply

hhremaker

2 years ago, # ^ |

it's a greedy

→ Reply

Blinding_Lights

2 years ago, # |

← Rev. 4 →

what's wrong with this approach of Div2 C. Any counter testcase? It gives WA on TC 3

code


    for(int i = 0; i < n; ++ i){
        ost.erase(ost.lower_bound(arr[i] - 1)); // erase current element from pbds multiset

        if(arr[i] <= q){
            s[i] = '1';
        }
        else{
            int less = ost.order_of_key(q);
            int notless = (int)ost.size() - less;
            if(notless < q){
                s[i] = '1';
                --q;
                if(q == 0) break;
            }
        }
        
    }

upd: got it

testcase

→ Reply

songtianyi

2 years ago, # |

Did you guys use prime factors to solve problem B? Bruteforce just got a TLE

→ Reply

2 years ago, # ^ |

Used simple math for O(1)

→ Reply