Codeforces Round #945 (Div. 2)

6 месяцев назад, # |

Today's contest in "Calendar" was scheduled: 15:05. I got ready and saw that: 20:35. Anyway I'm ready!!!

→ Ответить

Tsovak

6 месяцев назад, # |

+25

Codeforces Round 941 (Div. 1)
Codeforces Round 942 (Div. 2)
Codeforces Round 943 (Div. 3)
Codeforces Round 944 (Div. 4)
Any guesses?

→ Ответить

Borhan

6 месяцев назад, # |

A > B,C

→ Ответить

SuperMo

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

-10

A for me was in reading the constrain after 2 hours of trying to casework it

→ Ответить

Borhan

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

-10

Sad

→ Ответить

_HUECTRUM_

6 месяцев назад, # |

← Rev. 2 →

+21

Receiving clarifications for A about 7-9 mins into the contest after 1 failed attempt to answer the "original" problem is pretty underwhelming.

Bonus points for MASSIVE confusion after the first submission failed on pretest 1.

→ Ответить

mushfiq_nehal

6 месяцев назад, # |

← Rev. 2 →

-25

→ Ответить

6 месяцев назад, # |

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

→ Ответить

daud04

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

I skipped the sequence having a[i]=1

→ Ответить

mohamedeltair

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

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

→ Ответить

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

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.

→ Ответить

Borhan

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

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

→ Ответить

DuongForeverAlone

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

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

→ Ответить

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

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.

→ Ответить

0npata

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

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.

→ Ответить

DaniilBaldinMain

6 месяцев назад, # |

good round

→ Ответить

6 месяцев назад, # |

-10

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

→ Ответить

nichke

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

+19

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

→ Ответить

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

dang I must've overcomplicated it then

→ Ответить

nichke

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

← Rev. 2 →

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

→ Ответить

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

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

→ Ответить

Minerva2005

6 месяцев назад, # |

PTSD

→ Ответить

physics0523

6 месяцев назад, # |

+96

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

→ Ответить

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

+23

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

→ Ответить

_HUECTRUM_

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

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.

→ Ответить

nichke

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

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.

→ Ответить

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

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.

→ Ответить

_HUECTRUM_

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

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.

→ Ответить

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

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

→ Ответить

Itachi_Uchiha13

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

+18

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

→ Ответить

ExplodingFreeze

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

+32

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

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

→ Ответить

peti1234

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

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

→ Ответить

physics0523

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

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

→ Ответить

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

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

→ Ответить

desist

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

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?

→ Ответить

physics0523

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

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)

→ Ответить

qwerlty123

6 месяцев назад, # |

How to solve C?

→ Ответить

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

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

→ Ответить

qwerlty123

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

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

→ Ответить

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

yes

→ Ответить

qwerlty123

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

ok,thank you for your explanation

→ Ответить

DuongForeverAlone

6 месяцев назад, # |

+31

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

→ Ответить

kintisnikita

6 месяцев назад, # |

how problem B was solved?

→ Ответить

Wasif_Shahzad

6 месяцев назад, # |

got 180 score on A. couldn't solve anything else. bye bye pupil! :sob:sob:sob

→ Ответить

randombernie

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

Same. I'm yet to come up with a solution to it, in fact :(

→ Ответить

prashant51102

6 месяцев назад, # |

my hardest div.2 till now

→ Ответить

devu007

6 месяцев назад, # |

Happy to solve B, BS op!

→ Ответить

prashant51102

6 месяцев назад, # |

can anyone explain the approach for problem-C ?

→ Ответить

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

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

→ Ответить

alpha1215

6 месяцев назад, # |

← 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

→ Ответить

ExplodingFreeze

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

← Rev. 2 →

You're going in the correct direction.

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

Hint

→ Ответить

alpha1215

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

+11

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

→ Ответить

cseshamim47

6 месяцев назад, # |

Worst A ever!!! A > B

→ Ответить

Citypop

6 месяцев назад, # |

← 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

→ Ответить

DuongForeverAlone

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

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

→ Ответить

ExplodingFreeze

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

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

→ Ответить

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

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

→ Ответить

Leonardo_Paes

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

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

→ Ответить

Yugandhar_Master

6 месяцев назад, # |

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

→ Ответить

Yugandhar_Master

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

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

→ Ответить

cwz2024

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

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.

→ Ответить

Yugandhar_Master

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

Shit, due to this missed AC

→ Ответить

Karthik28

6 месяцев назад, # |

got TLE for problem B

→ Ответить

-dub-otrezkov-

6 месяцев назад, # |

how to solve D?

→ Ответить

Nvm I got it now. We have to ignore the last element in odd case and first element in even case.

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

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

→ Ответить

bananasaur

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

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

→ Ответить

Vladosiya

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

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

→ Ответить

harsh-apcr

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

← Rev. 2 →

you'll need to find the max, it is easy to find in $$$n-1$$$ queries (iterate over multiples of n)

once, you've got max (call it $$$a_{max}$$$) then iterate over multiples of $$$a_{max}$$$, note that $$$m \leq a_{max} \times n$$$, candidate $$$m$$$ is a multiple of $$$a_{max}$$$

→ Ответить

wibulord

6 месяцев назад, # |

Problem C, I've tried some special case line n = 6 Assumpt P = {6 1 4 2 3 5} so optimal Q should be = {1 4 5 3 6 2} but not Q = {1 6 3 5 4 2}

and otherwise with P = {6 3 2 4 1 5} So i come up with solving two case but my idea seems to be wrong somehow idk. Can sb help me with this 261394519

→ Ответить

Rubikun

6 месяцев назад, # |

+63

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

→ Ответить

TimDee

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

-35

Happy you liked!

→ Ответить

prvocislo

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

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

→ Ответить

Astroflexx

6 месяцев назад, # |

Man, this was a hard contest. Took 51 minutes to solve AB.

Also, why is this wrong for C? I did the same idea as everyone else. Calculate max score for odd indices (3, 5, ..., n — 1) and for even indices (2, 4, ..., n — 2) and then take max.

→ Ответить

Astroflexx

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

← Rev. 2 →

→ Ответить

Hasib.Nabid

6 месяцев назад, # |

-17

-1e9 downvotes loading

→ Ответить

rasesh_shetty

6 месяцев назад, # |

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

→ Ответить

lakshya_rocks

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

I hope you learned from this contest...

→ Ответить

awesome_idiot

6 месяцев назад, # |

C is too bad

→ Ответить

n0sk1ll

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

Why do you think so?

→ Ответить

6 месяцев назад, # |

+20

Finally i have reached master

→ Ответить

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

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.

→ Ответить

happy_new_year_2022

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

Can I be your slave? Plz?

→ Ответить

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

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

→ Ответить

pikachu1010

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

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

→ Ответить

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

Just enjoy cp

→ Ответить

dp_practise

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

"and really anything except for just practice."

→ Ответить

vinhdangquoc729

6 месяцев назад, # |

My easy solution for A:

Spoiler

→ Ответить

Karthik28

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

how does it always work

→ Ответить

vinhdangquoc729

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

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 < \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 :(

→ Ответить

avighnakc

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

Your explanation was pretty clear! Very nice solution.

→ Ответить

people_plus_plus

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

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

→ Ответить

SuperMo

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

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

→ Ответить

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

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

→ Ответить

vinhdangquoc729

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

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

→ Ответить

Saivishwas

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

← Rev. 2 →

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

→ Ответить

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

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.

→ Ответить

Saivishwas

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

$$$Thanks$$$ $$$a$$$ $$$lot$$$

→ Ответить

619

6 месяцев назад, # |

-39

Terrible problems.

→ Ответить

S_Neal

6 месяцев назад, # |

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

→ Ответить

nxsang1611

6 месяцев назад, # |

-51

Terrible contest...

→ Ответить

cwz2024

6 месяцев назад, # |

Finally I find my lucky contest lol :>

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

→ Ответить

titanium_syrup

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

hey can u please reply to dm

→ Ответить

The_Dice

6 месяцев назад, # |

← 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

→ Ответить

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

A & C draw $$$2$$$ times, B & C draw $$$3$$$ times, A and B draw $$$1$$$.

→ Ответить

The_Dice

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

Oh! stupid me :) Thx for the answer, very understandable

→ Ответить

Francesco4203

6 месяцев назад, # |

+11

Is it just me who solve A with a naive dp? Can't even come up with any solutions now xD

→ Ответить

jjstar_practice

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

same here

→ Ответить

Ryouko_miku

6 месяцев назад, # |

← Rev. 4 →

I don't like to guess T_T

→ Ответить

6 месяцев назад, # |

Sooo fast rating updation!!!

→ Ответить

andre_rei

6 месяцев назад, # |

Hi all!

Can someone help me figure out what happened with my B? I solved it using C++20 in my machine (the tests where matching) then I submitted my code to CF and got WA on test case 1. I looked at the results on the submission and one test was different from what I got locally.

Then I switched to C++17 on codeforces, submitted my code again and got AC.

What might be the problem? What I think is weird is that I was also using c++20 locally and there was no problems.

AC submission (c++17): 261375967 WA submission (c++20): 261374878

→ Ответить

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

Bro, I got TLE on case 1. Although, running well in my pc. Don't know why!!! Finally, I have managed to get accepted.

→ Ответить

cleanser

6 месяцев назад, # |

This C solution seems simpler than the other ones I've seen. Just take some set of nonadjacent (n-2)/2 elements to make as peaks such that none of the taken ones are equal to 1. Then, you can force those positions in the array a to have values >= n + 2, while forcing all other positions to have values <= n + 1, which guarantees that those become peaks.

→ Ответить

magickffmpeg

6 месяцев назад, # |

got skill-issued, and somehow increased rating lol

→ Ответить

BananaBrain

6 месяцев назад, # |

How to solve B?

→ Ответить

Sreedhar3210

6 месяцев назад, # |

A bit tougher than usual Div2, but the problems were amazing.

I felt B > C, especially proving that binary search works in B has taken a lot of time.

→ Ответить

bever209

6 месяцев назад, # |

BUCKETPOTATO ORZ

→ Ответить

ayushanshul07

6 месяцев назад, # |

I solved A in like 1hr and B in next 30 min. B without binary seach.

Why do I suck at A kind of problems.

→ Ответить

Cancelo

6 месяцев назад, # |

That was a hard one, anyway I enjoyed it.

→ Ответить

Eslam_Ahmed

6 месяцев назад, # |

Pretest Exactly Maintest WOW!

→ Ответить

Um_nik

6 месяцев назад, # |

+123

Very nice round!

→ Ответить

ksandr1v

6 месяцев назад, # |

На самом деле ABC — интересные задачи. Но вот ошибка в переводе, которая полностью поменяла смысл задачи А — очень сильно испортила впечатление...

→ Ответить

Omiya_Shinobu

6 месяцев назад, # |

+29

A little difficult, but absolutely a nice contest and high quality problems.

→ Ответить

6 месяцев назад, # |

'B' was quite tough compared to usual div-2.

→ Ответить

SlavicG

6 месяцев назад, # |

+10

Great problems!

→ Ответить

oaguider5

6 месяцев назад, # |

-8

Any approach to solve this problem?I am stuck

You are given a tree of 'N' vertices, rooted at vertex '0'. You assign a random number in the range '[0, M — 1]' to each of the vertices.

Let us define 'heap-like' as the property that: for all vertices 'v' in the subtree of any vertex 'u' of the tree, the random number assigned to vertex 'u' is less than or equal to the random number assigned to vertex 'v'.

Find the probability that the resulting tree is 'heap-like'.

The answer should be found modulo 10^9 + 7. Formally, let M = 10^9 + 7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and q !≡ 0 (mod M). Output the integer equal to p * (q^-1) mod M. In other words, output such an integer x that 0 <= x < M and x * q ≡ p (mod M).

For Example : Let 'N' = 3, edges = [ [ '0, 1' ], [ '0, 2' ] ], 'M' = 3. Random number assignments that result in a 'heap-like' tree are [ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ], [ 0, 1, 1], [ 0, 0, 2 ], [ 0, 2, 0 ], [ 0, 2, 1 ], [ 0, 1, 2 ], [ 0, 2, 2 ], [ 1, 1, 1 ], [ 1, 2, 1 ], [ 1, 1, 2 ], [ 1, 2, 2 ], [ 2, 2, 2 ]. The total number of possible assignments is '27' and the '14' assignments above result in a 'heap-like' tree. Thus, the probability of a heap-like tree is '(14 / 27) % (10^9 + 7) = 185185187'.

→ Ответить

agrim_09

6 месяцев назад, # |

Hello there! I had a funny little solution for B which involving Segment Trees.

My code : 261728503

Solution :

Hope you understand the solution, if you have any queries feel free to ask, and I'll try to help if possible.

→ Ответить

Creeper_l

6 месяцев назад, # |

I think problem D,E are both clever and interesting.

→ Ответить

towrist

6 месяцев назад, # |

really cool round! Problems have quite short and nifty codes and the ideas are really cool. well done on setting D and E (especially D)

→ Ответить