Codeforces Round #808

2 года назад, # |

Hopefully I don't lose expert.

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

yeah you too man.

→ Ответить

2 года назад, # ^ |

← 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 :/

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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!

→ Ответить

2 года назад, # ^ |

yes imao. Time to start upsolving!

→ Ответить

Imdie

2 года назад, # ^ |

Hopefully I don't lose CM

→ Ответить

2 года назад, # ^ |

Another one bites the dust...

→ Ответить

FairyWinx

2 года назад, # |

Respect smg23333!!!!

→ Ответить

jjang36524

2 года назад, # |

← Rev. 2 →

+18

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

So this is unrated?

→ Ответить

maintain0original

2 года назад, # |

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

→ Ответить

Abito

2 года назад, # ^ |

You have to get invited by the writers

→ Ответить

Azusamitsusa

2 года назад, # |

+28

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

→ Ответить

784

2 года назад, # ^ |

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

→ Ответить

Hozifa-Abulyaman

2 года назад, # ^ |

← Rev. 2 →

+22

Spoiler

→ Ответить

2 года назад, # ^ |

+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???

→ Ответить

EarthMessenger

2 года назад, # ^ |

-10

jiangly will take the first place!

→ Ответить

badluck_1441

2 года назад, # |

+36

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

→ Ответить

2 года назад, # ^ |

All the best to you and to everyone else!!

→ Ответить

Great_20

2 года назад, # ^ |

happy birthday dude

→ Ответить

winterfire

2 года назад, # |

+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

→ Ответить

2 года назад, # |

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

Someone knows how?

→ Ответить

harshaa05

2 года назад, # ^ |

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

→ Ответить

i_d_o_n

2 года назад, # |

← Rev. 4 →

+72

→ Ответить

2 года назад, # ^ |

He will reach 4000 before I reach 2000 XD

→ Ответить

2 года назад, # ^ |

yes

→ Ответить

i_d_o_n

2 месяца назад, # ^ |

Finally it's fulfilled

→ Ответить

018429

2 года назад, # |

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

→ Ответить

AboNageh

2 года назад, # |

← Rev. 3 →

-8

Deleted

→ Ответить

AboNageh

2 года назад, # |

← Rev. 2 →

-8

Deleted

→ Ответить

petertromso

2 года назад, # |

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

→ Ответить

BurningRaven

2 года назад, # ^ |

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

→ Ответить

petertromso

2 года назад, # ^ |

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

→ Ответить

Jhin

2 года назад, # |

← 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

→ Ответить

HaitangSuki

2 года назад, # |

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

→ Ответить

k1r1t0

2 года назад, # |

+89

→ Ответить

SalmaHatem_

2 года назад, # |

+13

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

→ Ответить

2 года назад, # ^ |

Me for sure negative.

Sed

→ Ответить

shifucracker

2 года назад, # |

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

→ Ответить

b16a

2 года назад, # ^ |

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

→ Ответить

Aravind

2 года назад, # |

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 :)

→ Ответить

shifucracker

2 года назад, # ^ |

-22

How'd you solve it?

→ Ответить

2 года назад, # ^ |

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

→ Ответить

XG0000

2 года назад, # |

+22

Can't solve 2C. Lower rating :(

→ Ответить

reeWorld

2 года назад, # ^ |

+11

me too :|

→ Ответить

Individual

2 года назад, # ^ |

-8

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

→ Ответить

baiABC

2 года назад, # ^ |

me too :(

→ Ответить

TheStrongest

2 года назад, # |

Капец, C легче A. Люди, как такое возможно?????

→ Ответить

proof_by_ac

2 года назад, # |

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

→ Ответить

Omar_Hafez

2 года назад, # |

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

→ Ответить

2 года назад, # ^ |

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

→ Ответить

Omar_Hafez

2 года назад, # ^ |

-18

I hope so.

→ Ответить

TheStrongest

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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

→ Ответить

notstoppingever

2 года назад, # |

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

→ Ответить

AdiMall

2 года назад, # ^ |

Lol, see mine

→ Ответить

notstoppingever

2 года назад, # ^ |

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

→ Ответить

AdiMall

2 года назад, # ^ |

Hope my graph goes like my April 2022 graph :(

→ Ответить

cp-is-fun

2 года назад, # |

There is a big gap between B and C

→ Ответить

Omar_Hafez

2 года назад, # ^ |

exactly. The contest is not balanced

→ Ответить

harsh__h

2 года назад, # |

+26

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

→ Ответить

callmepandey

2 года назад, # |

+36

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

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

Also when there is bitwise XOR or something like that

→ Ответить

_darkSide

2 года назад, # |

+29

I can feel what Doremy is going through :(

→ Ответить

haochenkang

2 года назад, # |

Can someone give me a hint for Div2D?

→ Ответить

2 года назад, # ^ |

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

→ Ответить

haochenkang

2 года назад, # ^ |

Thanks

→ Ответить

defiler123

2 года назад, # ^ |

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.

→ Ответить

haochenkang

2 года назад, # ^ |

Thanks

→ Ответить

MrOtter

2 года назад, # ^ |

hint

→ Ответить

2 года назад, # |

← 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

→ Ответить

shashankag

2 года назад, # ^ |

Can you please explain your reasoning for D. Thanks

→ Ответить

2 года назад, # ^ |

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

→ Ответить

ExpensiveAC

2 года назад, # ^ |

Same lol for B

→ Ответить

Nyaruko

2 года назад, # |

+23

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

→ Ответить

Xixika

2 года назад, # |

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

→ Ответить

ExplodingFreeze

2 года назад, # |

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

→ Ответить

smax

2 года назад, # ^ |

+18

Your idea is correct.

→ Ответить

koqo

2 года назад, # |

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

→ Ответить

dukhi_insaan

2 года назад, # |

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;
}

→ Ответить

2 года назад, # ^ |

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

→ Ответить

variety-jones

2 года назад, # ^ |

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

→ Ответить

introart

2 года назад, # |

-21

Div 2 A is trash

→ Ответить

2 года назад, # ^ |

You are absolutely right.

→ Ответить

feblokas

2 года назад, # ^ |

С too

→ Ответить

hhremaker

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

Just because you didn't solve it?

→ Ответить

11thCommandment

2 года назад, # |

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

→ Ответить

dukhi_insaan

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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

→ Ответить

LeXuanSech

2 года назад, # |

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

→ Ответить

chenyanlin

2 года назад, # |

How can I pass problem 3？

→ Ответить

Jhin

2 года назад, # |

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;
    }

→ Ответить

lis05

2 года назад, # |

+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!

→ Ответить

lkjhgfertyul

2 года назад, # ^ |

or at least give a sample case where numbers are equal

→ Ответить

lis05

2 года назад, # ^ |

Exactly!

→ Ответить

2 года назад, # ^ |

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

→ Ответить

29logN

2 года назад, # ^ |

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

→ Ответить

javad_asadi

2 года назад, # ^ |

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.

→ Ответить

lexiyvv

2 года назад, # |

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

→ Ответить

2 года назад, # |

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

→ Ответить

krishna_0_9

2 года назад, # |

-22

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

→ Ответить

2 года назад, # ^ |

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.

→ Ответить

jai6

2 года назад, # ^ |

Can you elaborate on the DP approach?

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

Could you please elaborate on that?

I've explained my solution here.

→ Ответить

2 года назад, # ^ |

Will,my dp solution is diff from yours XD

→ Ответить

2 года назад, # ^ |

Could you please explain yours?

→ Ответить

2 года назад, # ^ |

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

→ Ответить

Uzumaki_TheLoser

2 года назад, # |

div2c was binary search ?

→ Ответить

MrOtter

2 года назад, # ^ |

it can be done linearly with reverse order

→ Ответить

hhremaker

2 года назад, # ^ |

it's a greedy

→ Ответить

Blinding_Lights

2 года назад, # |

← 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

→ Ответить

songtianyi

2 года назад, # |

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

→ Ответить

2 года назад, # ^ |

Used simple math for O(1)

→ Ответить