Codeforces Round #945 (Div. 2)

2 years ago, hide # |

+15

Anyone proved the validity of C?

I thought of a greedy solution, check if it's possible to maximize at indices $$$(3, 5, \dots, n-1)$$$ or $$$(2, 4, \dots, n-2)$$$, then take the case with better score.

→ Reply

daud04

2 years ago, hide # ^ |

I skipped the sequence having a[i]=1

→ Reply

mohamedeltair

2 years ago, hide # ^ |

← Rev. 2 →

+11

As long as $$$1$$$ is not one of the chosen elements to be local maximums, then such construction will lead to values $$$\geq n+2$$$ for local maximums and $$$\leq n+1$$$ for other values.

→ Reply

2 years ago, hide # ^ |

I see. This claim seems to assure that my solution is correct (yet slightly redundant as excluding $$$1$$$ is done only at the final comparison). Thank you.

→ Reply

Borhan

2 years ago, hide # ^ |

Just choose the case that ignore 1 cuz for example if n=8

a-> ..8 1 7.. p-> ..1 8 2.. res -> ..9 9 9 ..

which not valid solution..

→ Reply

DuongNeverAlone

2 years ago, hide # ^ |

← Rev. 2 →

If one of them have better score, then the smaller-score one will have the element '1' inside it. The fact is that every elements will be at least n + 1 after the transformation. So if the we try to maximize the position having the element 1, it couldn't be the local maximum.

→ Reply

2 years ago, hide # ^ |

Take the one with n or if n is on the edge, take the one that is further away from n.

If you take the one with n, worst case, you have to maximize 1, 2, 3, ... n in order. To 1 let's match up n in ans permutation and to 2 let's match up n — 1 and so on and so on. The minimum sum we can get is n + 1, n + 1, n + 1 ...

To be sure they are the local maximums, the worst case scenario of the neighbors are that they are n — 1, n — 2, n — 3 ... to n — 1 let's match up 1 in our ans permutation, to n — 2 let's match up 2 to n — 3, 3 ... and we see that our neighbors are n, n, n in the worst case. Since n + 1 > n, this works.

There is similar logic when n is on the edge.

→ Reply

0npata

2 years ago, hide # ^ |

Since it is even you can always achieve the optimal number of local maximums in an array. The only thing you need to watch out for is to make element N, a local maximum, and if you do that it can be proven that every element that is supposed to be a local maximum will be >= N+1 and every other element < N+1. Just add 1, 2, 3, 4.... to local mins in increasing order so at worse that would be (N-1)+1, (N-2)+2 ... you can see that each is at most N, and do the reverse for local maxs 1+N, 2+(N-1) ... each is >= N+1.

→ Reply

Bald1nD

2 years ago, hide # |

good round

→ Reply

2 years ago, hide # |

-10

is it just me or was C kinda tough to implement?

→ Reply

nichke

2 years ago, hide # ^ |

+19

It was very easy to implement, the observation was the difficult part imo.

→ Reply

2 years ago, hide # ^ |

dang I must've overcomplicated it then

→ Reply

nichke

2 years ago, hide # ^ |

← Rev. 2 →

Take a look at my submission, I see your code got very messy. 261386987

→ Reply

2 years ago, hide # ^ |

Thanks broski. It seems like we had the same greedy strat but this one is much more concise.

→ Reply

physics0523

2 years ago, hide # |

+96

Almost toughest Div2. BCD are too hard for their positions and D is the strangest problem of my CP journey...

→ Reply

2 years ago, hide # ^ |

+23

Lol I thought I was the only one thinking B was odd. Counting prefixes bit-by-bit should be C at least.

→ Reply

_HUECTRUM_

2 years ago, hide # ^ |

I didn't count prefixes. I just split the numbers into bits and found the length of the longest sequence of zeroes in the resulting arrays.

→ Reply

nichke

2 years ago, hide # ^ |

Exactly, just sort the indices of elements with each bit and take the max difference between them, no need for prefixes or binary search or anything similar.

→ Reply

2 years ago, hide # ^ |

Ah, I see. I must have done dumb things under pressure. XD

Still, bitworking for B does seem overboard a little bit. Maybe 1250 is a more proper score for it.

→ Reply

_HUECTRUM_

2 years ago, hide # ^ |

I get what you're saying, but nothing compares to having an incorrect russian A statement to me. Wasted 10 mins because of it, more than i spent on B.

→ Reply

2 years ago, hide # ^ |

That part, I could empathize with (though I escaped it since the English ver did justice). Kinda sorry for your bad luck there.

→ Reply

Itachi_Uchiha13

2 years ago, hide # ^ |

+18

Same lol, I used Sparse Table and Binary Search. Ig I really over killed it.

→ Reply

ExplodingFreeze

2 years ago, hide # ^ |

+32

Out of curiosity, what makes D so strange in your opinion?

It feels fairly normal for a CF interactive problem to me.

→ Reply

peti1234

2 years ago, hide # ^ |

← Rev. 2 →

+25

The interaction and the output format is very weird. What I expected: I can ask $$$l, r$$$ and the answer will be $$$f(l, r)$$$. (I know that's not interesting because $$$f(l, l)=$$$ $$$a_l$$$) And the output should be the array or some natural proterty of that.

By the way nice problem.

→ Reply

physics0523

2 years ago, hide # ^ |

← Rev. 2 →

-14

Straightforward thinking leads $$$O(n \log n)$$$ (but maybe with small constant) queries, and try to cut down into $$$O(n)$$$ leads back-to-back wrong ideas.
And splitting $$$2n$$$ into $$$n+n$$$ feels bad because asking $$$?$$$ $$$1$$$ $$$m \times i$$$ ( $$$1 \le i \le n$$$ , $$$m$$$ is a (fixed) integer) leads easily shortage of one of $$$n$$$. The actual solution is finding maximum and bruteforcing with some upperbounds, but later one costs $$$\le n$$$ queries is very unnatural I feel.

Maybe the unnatural situation of the problem also calls my feeling.

→ Reply

2 years ago, hide # ^ |

I think so too, i would say the less number of solves is partly due to the un intuitive solution and setting of the problem

→ Reply

desist

2 years ago, hide # ^ |

Why does it feel unnatural to try and split the latter $$$n$$$ into checking $$$\frac{n}{k}$$$ options that each require $$$k$$$ queries? Or did I misunderstand something?

→ Reply

physics0523

2 years ago, hide # ^ |

When I don't know the solution, fixed $$$k$$$ looks like shackle rather than advantage so I get lost, and I found the fact your figured almost after write my code. (Noticing after is easy but solve from $$$n/k \times k = n$$$ is hard and I feel the solution is just happened to work well or something that)

→ Reply

qwerlty123

2 years ago, hide # |

How to solve C?

→ Reply

2 years ago, hide # ^ |

1.Divide the array into halves based on even and odd index.

Find which half has 1 (this is the half without maxes), you could do half that has n is maxes, alse.
Sort both halves.
Sort sides with peaks. Put n/2 + 1 to n in this half. Smallest number in OG array gets largest number in new array.
Same as above with array without peaks but with 1 to n/2.
Print

→ Reply

qwerlty123

2 years ago, hide # ^ |

I understand it. The peaks are all taken as>=n+2, and the rest are taken as<=n+1,is it?.

→ Reply

2 years ago, hide # ^ |

yes

→ Reply

qwerlty123

2 years ago, hide # ^ |

ok,thank you for your explanation

→ Reply

DuongNeverAlone

2 years ago, hide # |

+31

Proud of myself by solving C with proving its validity, not by guessing

→ Reply

kintisnikita

2 years ago, hide # |

how problem B was solved?

→ Reply

prashant51102

2 years ago, hide # |

my hardest div.2 till now

→ Reply

prashant51102

2 years ago, hide # |

can anyone explain the approach for problem-C ?

→ Reply

2 years ago, hide # ^ |

1.Divide the array into halves based on even and odd index.

Find which half has 1 (this is the half without maxes), you could do half that has n is maxes, alse.
Sort both halves.
Sort sides with peaks. Put n/2 + 1 to n in this half. Smallest number in OG array gets largest number in new array.
Same as above with array without peaks but with 1 to n/2.
Print

→ Reply

alpha1215

2 years ago, hide # |

← Rev. 2 →

please don't give spoiler

in problem D.
we can find max element a_max in n queries 
the ans m will be some multiple of a_max there will be n such possible values of m but don't how to check them all in rest n queries

please tell me if im in correct direction and need some more observations
or im too far from the soln. Thanks!

upd : got AC, we only need check first n / k multiples of a_max

→ Reply

ExplodingFreeze

2 years ago, hide # ^ |

← Rev. 2 →

You're going in the correct direction.

If you want a (somewhat spoiler-ish) hint:

Hint

→ Reply

alpha1215

2 years ago, hide # ^ |

+11

Thank's! will see the hint after AC :)

→ Reply

cseshamim47

2 years ago, hide # |

Worst A ever!!! A > B

→ Reply

ComeAlone

2 years ago, hide # |

← Rev. 3 →

+11

A: I guessed we should greedily remove (1, 1) from 2 highest score until there is 0/1 positive score left.

B: I guessed it's binary searchable.

C: I guessed only considering position 2 and 3 is sufficient.

D: What should I guess? XD

→ Reply

DuongNeverAlone

2 years ago, hide # ^ |

First I thought D is binary search, but it's actually not. Ad-hoc seems fit to D.

→ Reply

ExplodingFreeze

2 years ago, hide # ^ |

D: Guess that finding the max is important and then think how to use it :P

→ Reply

2 years ago, hide # ^ |

I guessed that we needed to reduce the amount of values i needed to check

→ Reply

Leonardo_Paes

2 years ago, hide # ^ |

-15

If you try solving B in O(n log n) the solution is very pretty, no guesses needed.

You can take a look at my solution https://codeforces.me/contest/1973/submission/261355440

You just look for the maximum distance between numbers with the i-th bit on, for every bit.

→ Reply

Think_Only_Once

2 years ago, hide # |

Author please tell me why interactor not giving maximum element in the array for sample test case 3 for the following code.

code

...

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int main(){
    fast;
    ll t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;
        ll maxi=0;
        for(ll i=1;i<=n;i++){
            cout<<"? "<<1<<" "<<(i*n)<<endl;
            ll r;
            cin>>r;
            if(r==n) maxi=max(maxi,i);
        }
        vector<ll> v((n/k));
        for(ll i=0;i<(n/k);i++){
            v[i]=(i+1)*maxi;
        }
        ll ans=-1;
        for(ll i=0;i<(n/k);i++){
            bool ok=true;
            ll cnt=0,l=1;
            while(l<=n){
                cnt++;
                cout<<"? "<<l<<" "<<v[i]<<endl;
                ll r;
                cin>>r;
                if(r>n || cnt>k){
                    ok=false;
                    break;
                }
                l=r+1;
            }
            if(ok && cnt==k) ans=max(ans,v[i]);
        }
        cout<<"! "<<ans<<endl;
    }
}

→ Reply

Think_Only_Once

2 years ago, hide # ^ |

Every time it's giving 0 as maximum, but surely it will give some positive

→ Reply

cwz2024

2 years ago, hide # ^ |

I think that you may need to read something after you give an answer, because the interactor in this problem will return 1 or -1 after you give an answer. I also WA in pretest 1 and got confuse but after I figure it out and read one more thing after giving my answer, I passed the pretest.

→ Reply

Think_Only_Once

2 years ago, hide # ^ |

Shit, due to this missed AC

→ Reply

Karthik28

2 years ago, hide # |

got TLE for problem B

→ Reply

dub-otrezkov

2 years ago, hide # |

how to solve D?

→ Reply

2 years ago, hide # ^ |

← Rev. 2 →

Use n guesses to find largest element in array. Can be done by guessing ? n s*n for s in range n to 1. s is the largest number in array
If m exists m must be a multiple of s. m must also be a maximum of s/k, because anything greater cannot exist as m=s/k, divide array into k equal parts if all elements in array are s.
Can brute force with those 2 observations. n/k solutions to check. Each solution takes at most k queries.

→ Reply

bananasaur

2 years ago, hide # ^ |

+19

Find the maximum element $$$mx$$$ in $$$a$$$ by making queries $$$(1,n*n), (1,n*(n-1)),\dots$$$. If you get $$$r=n$$$ on query $$$(1,n*b)$$$ then $$$mx=b$$$.

Now since this maximum element is present in at least one of the $$$k$$$ subarrays, $$$mx$$$ must divide $$$m$$$. Also, if $$$m=b*mx$$$, every subarray must have length at least $$$b$$$. So we only need to check multiples of $$$mx$$$ upto $$$\frac{n}{k}mx$$$. In each candidate for $$$m$$$, just query $$$k$$$ segments starting from position $$$1$$$ and check if these segments cover the array.

This takes $$$n$$$ queries to find $$$mx$$$ and another $$$n$$$ queries to check all values of $$$m$$$.

→ Reply

Vladosiya

2 years ago, hide # ^ |

Damn, I figured this one out during contest but forgot to replace $$$m$$$ with $$$b \cdot mx$$$ and thought it's $$$O(n^2)$$$ queries :(

→ Reply

Rubikun

2 years ago, hide # |

+63

It was the most fun Div.2 ever, thank you!

→ Reply

TimDee

2 years ago, hide # ^ |

-35

Happy you liked!

→ Reply

prvocislo

2 years ago, hide # ^ |

thanks a lot! I'm really glad you enjoyed the problems!

→ Reply

rasesh_shetty

2 years ago, hide # |

-7

Mannn.. wasted 20 min on a corner case in problem A. and wasted almost 1 hr on a simple mistake in problem C.. as well as 4 wrong submissions, giving a heavy penalty... But overall the questions were amazing.

→ Reply

awesome_idiot

2 years ago, hide # |

C is too bad

→ Reply

n0sk1ll

2 years ago, hide # ^ |

Why do you think so?

→ Reply

2 years ago, hide # |

+20

Finally i have reached master

→ Reply

2 years ago, hide # ^ |

I would also appreciate if anyone could give me some advice on how to grow from here. I am looking for things like something that you felt you had to change in order to go from M to GM and really anything except for just practice.

→ Reply

happy_new_year_2022

2 years ago, hide # ^ |

Can I be your slave? Plz?

→ Reply

2 years ago, hide # ^ |

Would you be so kind to enlighten me on what that entails?

→ Reply

pikachu1010

2 years ago, hide # ^ |

Nice reaching master in less than 2 years, any advice for us newbies, kiyotaka?

→ Reply

2 years ago, hide # ^ |

Just enjoy cp

→ Reply

dp_practise

2 years ago, hide # ^ |

"and really anything except for just practice."

→ Reply

vinhdangquoc729

2 years ago, hide # |

My easy solution for A:

Spoiler

→ Reply

Karthik28

2 years ago, hide # ^ |

how does it always work

→ Reply

vinhdangquoc729

2 years ago, hide # ^ |

There can be at most $$$\frac{p1 + p2 + p3}{2}$$$ draws between 3 players. But if the total score of any two people smaller than $$$\frac{p1 + p2 + p3}{2}$$$ (for example, $$$p1 + p2 \lt \frac{p1 + p2 + p3}{2}$$$) then there can only be at most $$$p1 + p2$$$ draws between player 3 and (player 1 & player 2).

I don't know how to explain it more clearly :(

→ Reply

avighnakc

2 years ago, hide # ^ |

Your explanation was pretty clear! Very nice solution.

→ Reply

people_plus_plus

2 years ago, hide # ^ |

You can apply standart algorithm: $$$s=a+b+c$$$ and answer is $$$\left\lfloor \frac{s}{2} \right\rfloor$$$ or $$$s-c$$$ if $$$s-c\leq c$$$

→ Reply

SuperMo

2 years ago, hide # ^ |

(p2+p3) and (p3+p1) makes no sense since the numbers are sorted (p1+p2) makes sense if C was bigger than(a+b) but how did you come up with (p1+p2+p3)/2 can you please tell ?

→ Reply

2 years ago, hide # ^ |

(p1+p2+p3)/2 is literally the case when every match ends with a draw.

→ Reply

vinhdangquoc729

2 years ago, hide # ^ |

← Rev. 3 →

Oh, I didn't notice that the numbers are sorted. Each game increases $$$(p1+p2+p3)$$$ by $$$2$$$, which means the maximum number of games played is $$$\frac{p1+p2+p3}{2}$$$.

→ Reply

Saivishwas

2 years ago, hide # ^ |

← Rev. 2 →

How can we write math variables and equations with special font and symbols in our comment?

→ Reply

2 years ago, hide # ^ |

The expressions use LaTeX. You can check out this quick guide.

It's best to press "Preview" before commenting to make sure that your written syntax is correctly rendered.

→ Reply

619

2 years ago, hide # |

-39

Terrible problems.

→ Reply

S_Neal

2 years ago, hide # |

The assumption of finding the maximum value of the array in problem D was nice.

→ Reply

nxsang1611

2 years ago, hide # |

-51

Terrible contest...

→ Reply

cwz2024

2 years ago, hide # |

Finally I find my lucky contest lol :>

Waiting for another even luckier contest to push me to CM :>

→ Reply

titanium_syrup

2 years ago, hide # ^ |

hey can u please reply to dm

→ Reply

D-ice

2 years ago, hide # |

← Rev. 2 →

I'm newbie in here, can someone explain why in the problem A test case 1 => 3, 4, 5 the answer is 6. If i count manually i just can make the max of draw is 5. With the following operation:

A & C draw so 1, 0, 1
A & C draw so 2, 0, 2
A & C draw so 3, 0, 3
B & C draw so 3, 1, 4
B & C draw so 3, 2, 5
then B win so 3, 4, 5

I cant find if the max draw is 6 T_T

→ Reply