Hey I want to know why you got downvoted... You were just wishing everyone good luck. Am I missing something? I feel bad for you :(

Don't worry we will upvote you eventually. Love from Sweden!

ohhh

No worries for the noobs then!

Road to cyan

I wish!

cf predictor is showing something -200 for you lol.

rama798 you did it on purpose didn't you?

yes sir! how many contests you order?

You needn't think about that in this much advance.. Mostly contests will pop up around 3-5 days before they will be held. And that much of advance notice is enough and there are many Coding Contest Tracker Apps to help you with tracking(Coding Schedule for example) if you need one.

.

[Deleted]

It seems like it didn't work out as you expected XD

too bad you had even asked for permission to use this in next round

Why is he downvoted? He raises a fair point I think?

(Edit: his comment was downvoted when I wrote my comment)

+1 from my side.. We already witnessed(Round 682) what happens when something unorganised goes from tester's side. And this one is without them wholly.. Fingers crossed

And now you are GrandMaster. Dreams come true :)

I think CF Round #683 was not horrible, what do you think?

those who upvoted I really wanna thank you. But I think its not going to work. Anyways Good luck for today's contest.

Now that's a nice way to get upvotes.

It's +1 now, Let's make it 0 again...!!!

Thank you guys for upvoting..

please make my contribution from 103 — 1 to 103

Why So downvotes? I think dude has made a cool website, though it loads a bit late. But I think the UI is just awesome.

You happy now?

have fun with -4 XD

u can click star but that will make the user your friend.it will not increase your count of friends.for that somebody needs to click on the star of your profile

Better try solving the problems instead of wasting time here

about -47

D is a stupid problem.

Whats the trick to B? Solved A, C, D still couldnt figure out B.

Maybe C with B should have been swapped, yes. But B with D? Are you serious?

The order was the same for everyone, so you have only yourself to blame for your poor strategy choices.

Exactly! I solved D with no difficulty, but couldn't solve B.

Educational rounds are always pure destruction for me for some reason

We estimate the difficulty of ER C as Div2B, not Div2C. Do you think that this problem is easier than Div2B?

nth fibonacci * inverse(2^n). You can try brute force by recursion on some small numbers and check the pattern. The question is how many ways are there of choosing (only)odd numbers so that there sum is perfectly n.

When n=2
1 1

When n=3
1 1 1
3

When n=5
1 1 1 1 1
1 1 3
3 1 1
1 3 1
5

These are the ways of arranging radio towers on different n.

The main idea is that lets say you want to cover the region of n blocks, then what you can do is take the 1 position and make the tower to have 1 power, take 3 position and put tower in the middle with power 2, take 5 position and and put tower in the middle with power 3, and so on.

So for a state with n position we get a nice recusive relation

f(n) = f(n - 1) + f(n - 3) + f(n - 5) .....

In the end since we are required to print the probability which is equal to f(n) / 2 ^ n where 2 ^ n are all possible configurations and f(n) are valid configurations. Also remember this all happens under mod

While solving, I didn't realize dp[N] = F(N).

I solved it with dynamic-programming.

 const int maxn = 2e5;
 vector<Mint> dp (maxn + 1);
 Mint odd = 0;
 Mint even = 0;
 for (int i = 1; i <= maxn; i++) {
  if (i % 2 == 1) {
   dp[i] = even;
  }
  else {
   dp[i] = odd;
  }
  if (i % 2 == 1) {
   dp[i] += 1;
  }
  if (i % 2 == 0) even += dp[i];
  else odd += dp[i];
 }
 int n;
 cin >> n;
 cout << dp[n] / power ((Mint) 2, n) << '\n';

Nice observation.

Thanks for the explanation.

The way I solved it is noticing the problem comes down to "Find the number of ways that you can express a number $$$n$$$ as a sum of odd numbers". Pretty well known this is found with the Fibonacci Series.

That's nice! I solved it in a more dubious way. My solution is based on the following observation: suppose the first active tower is x, then towers 1 -> x-1 and x+1 -> 2*x-1 are not active. Ok, now say we have N towers and we activate the first tower. Its signal power is obviously 1. This leaves us with the other N-1 towers and the initial problem, but with only N-1 towers. If we say dp[i] = the solution for i towers, then we can now state that dp[i] = 1/2 * dp[i-1] + something (1/2 is because we have to activate the first tower) Now suppose the first tower we activate is the second one. Its signal power is 2 and the first and third towers are not activated. Excluding these towers, we have the initial problem but with N-3 towers. So dp[i] = 1/2 * dp[i-1] + 1/8 * dp[i-3] + ...

Let's take some examples: dp[5] = 1/2 * dp[4] + 1/8 * dp[2] + 1/32 * dp[0] dp[4] = 1/2 * dp[3] + 1/8 * dp[1]

We can keep 2 partial sums, one for odd numbers and one for even numbers. When we calculate dp[5], we add it to the odd partial sum the following way: sum[odd] = sum[odd] * 1/4 + 1/2 * dp[5].

Say the sum is $$$S$$$, since we want them all to have the same number of blocks and the pile he chose ends up with $$$0$$$ they will have exactly $$$\frac{S}{n-1}$$$ blocks. So we always have to make $$$S$$$ divisible by $$$n-1$$$.

The only other condition is that $$$\frac{S}{n-1}$$$ is at least as large as all elements, otherwise since we can't take blocks away that pile would be larger.

Thus, if the maximum element in the sequence is $$$M$$$ the answer is just the largest of $$$M(n-1)-S$$$ and $$$(-S) \pmod{n-1}$$$

The idea is that if we can use the minimum value of the array to make every other value equal to each other ,then we can do the same for every other $$$i$$$. Let $$$mn$$$ be the minimum value in the array and $$$mx$$$ be the maximum. Then we need to calculate the sum of differences between $$$mx$$$ and every other value different from $$$mn$$$, we can call this value $$$s$$$. If $$$s>=mn$$$ then the required number of blocks will be exactly $$$s-mn$$$. Otherwise, we need to verify that $$$mn-s$$$ is divisible by $$$n-1$$$. If $$$(mn-s) mod (n-1) = 0$$$ then the answer is $$$0$$$, otherwise it will be $$$n-1$$$ minus the remainder.

Just make the sure you can satisfy all the conditions if you pick the box with the smallest number of balls. Because that box is the one with the maximum constraints. Then the other boxes will automatically satisfy the conditions because they will have lesser constraints than the smallest box. To satisfy the smallest box, calculate how much extra balls you require to make every box other than the selected box have the same number of balls i.e. the max.no. of balls in a box.

If the req no. of balls is less than the balls you have, just make sure that the extra balls are divisible by (n-1)

#include <bits/stdc++.h>


#define vi vector<int>
#define tests int t; cin>>t; while(t--)
#define ll long long
#define vll vector<long long>
#define srt(v) sort(v.begin(), v.end())
#define srtg(v) sort(v.begin(), v.end(), greater<int> ())
#define FOR(k, n) for(int k=0; k<n; k++)
#define pb push_back
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define printarr(v) for(auto& x : v) cout<<x<<" "; cout<<endl
#define ree cout<<"******************************************"<<endl
#define int long long

using namespace std;


char nums[10] = { '0','1','2','3','4','5','6','7','8','9' };
char alphsl[26] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z' };
const int MOD = 1000000007;
char alphs[26] = { 'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' };



void solve() {
    
   int n;
   cin>>n;
   
   vector<int> v(n);
   for(auto& x : v) cin>>x;
   
   srt(v);
   
   int maxy=v[n-1];
   int req=0;
   for(int i=1; i<n; i++) req+=maxy-v[i];
   
   if(v[0]<=req){
       cout<<req-v[0]<<endl;
   }
   else {
       int temp=v[0]-req;
       temp%=n-1;
       if(temp==0){
           cout<<0<<endl;
       }
       else {
           cout<<n-1-temp<<endl;
       }
   }
   
   
}


signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
   
    
        tests
        solve();


    return 0;
}

how ?

why do you comment about this before finishing open hacking period....

some guys might hack your code ... hope you for surviving..

Actually, instead of ST, you can use scanline. 100792298

We have written some $$$O(n^2 \log n)$$$ solutions for E, and they pass. Unfortunately, several participants even squeezed $$$O(n^3)$$$ with a lot of optimizations, so perhaps we should've left the constraints as $$$n \le 5000$$$. What is your solution?

Just some pragmas nothing else: code

I really hope somebody finds a hack to these solutions cause its really annonying T_T

I don't think hacking in Educational Rounds gives you any extra score.

You don't gain anything for hacking in an educational contest.

what is proof of using fibonacci pattern in problem D