awoo's blog

Educational Codeforces Round 98 Editorial
By awoo, history, 6 months ago, translation, In English

1452A - Robot Program

Idea: BledDest

Tutorial
Solution (BledDest)

1452B - Toy Blocks

Idea: adedalic

Tutorial
Solution (adedalic)

1452C - Two Brackets

Idea: BledDest

Tutorial
Solution (pikmike)

1452D - Radio Towers

Idea: BledDest

Tutorial
Solution (BledDest)

1452E - Two Editorials

Idea: BledDest

Tutorial
Solution (pikmike)

1452F - Divide Powers

Idea: adedalic

Tutorial
Solution (adedalic)

1452G - Game On Tree

Idea: adedalic

Tutorial
Solution 1 (pikmike)
Solution 2 (BledDest)
 
 
 
 
  • Vote: I like it
  • +98
  • Vote: I do not like it

Comments Comments (104)
»
6 months ago, # |
  Vote: I like it +18 Vote: I do not like it

What about rating updates?

→ Reply
»
6 months ago, # |
  Vote: I like it +28 Vote: I do not like it

I think, in tutorial G, Alice and Bob had been swapped. It's Alice who has one starting vertex, and it's Bob who chases her, not vice versa.

→ Reply
  • »
    »
    6 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Oh, indeed. I've been told the problem with them reversed and I haven't read the actual statement haha. Will fix in a sec, thanks.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem A's solution a bit more. I couldn't get it!

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    See let min(x,y)=a

    Then, we can first go to (a,a) in exactly a*2 steps. After that we just have to increment in one direction and the best way to do that is by first waiting then moving because it always takes comparatively less number of steps,i.e, 2.

    Also note we can always reach (a,a) in two possible ways by first moving right or left, so when we take steps from (a,a) we can always increment one step without waiting.

    So, answer is (a*2)+1+max(y-x-1)*2 when (y-x-1)>=0 else answer is simply (a*2) when x==y

    You can look at my submission 98961942. Hope you find it helpful !

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      can we write second condition when x!=y as 2*max(x,y)-1 ?? if not please give some examples sorry i didn't read the editorial before

      → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why i get tle in test case 20 of problem E

my submission : 99017296

logic

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Comparator for sorting should follow strict weak ordering. If $$$a=b$$$ then it should always return false, otherwise it's undefined behavior.

    → Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

If anyone didn't understand B. Here is an easy solution-

For solution to exist let us consider an element any index i. Then, for solution to exist we should be able to increment all values at all indexes to the max value in the array because we can't decrement the max value anyway.

Thus, a[i]>=(a[max]-a1)+(a[max]-a2)......(a[max]-a[max])
or, a[i]>=a[max]*n-1-(S-a[i]) where S is total sum of all elements.
or, S>=a[max]*n-1;

So solution boils down to two cases-

1. When S<a[max]*n-1 then the answer is just the difference of these two.

2. If S>a[max]*n-1 then (S-a[max]*n-1) should be equally divisible by (n-1), so just increment S until divisible by (n-1) and the answer is difference of the two.

You can look at my submission here

→ Reply
»
6 months ago, # |
  Vote: I like it -39 Vote: I do not like it

My code gives me wrong answer in test case 3 any one help Question no B

void solve() { ll n; cin>>n;

ll a[n];
ll mx = 0 ;
for (ll i= 0;i<n;i++)
{
    cin>>a[i] ;
    mx = max(mx, a[i]);
}

if (n==2)
{
    cout<<0<<endl;
    return ;
}

ll sum = accumulate(a , a+n , 0) ;

ll temp = mx*(n-1)*(1ll) ;

if (sum == temp)
cout<<0<<endl;
else if(sum <temp)
cout<<abs(sum-temp)<<endl;
else
{
    for (ll i=1;i<=100000;i++)
    {
        if (((n-1)*i*(1ll)) == sum)
        {
            cout<<0<<endl;
            return ;
        }
        else if (((n-1)*i*(1ll)) > sum)
        {
            cout<<(abs(n-1)*i*(1ll) - sum)<<endl;
            return;
        }
    }
}

}

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Proof by Induction for problem D is great but can someone tell me if there is a mathematical proof for that?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we have a tower with power p, it will cover 2p-1 spots, thus the length of the subsegment covered by a tower is always odd.Now we need to find a way to divide a length of n into a number of odd length subsegments. This can be done via dynammic programming, which reduces to finding the nth Fibonacci number. In the end , just divide this by 2^n.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I'm sorry but I didn't need the proof for the solution to this problem. I was wondering how did that function get reduced to just finding the Fibonacci number for a particular input.(which was proved by Induction by the Editorialist)

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        f(n) = f(n-1) + f(n-3) + f(n-5) + .... f(n-2) = f(n-3) + f(n-5) + .... thus f(n) = f(n-1) + f(n-2) Is this what you were looking for?

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah exactly, thanks for putting it that way. Made it so easy to understand.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i didnt get it, can you explain how that comment helped you? i m still confused

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Just look at what he wrote:

              f(n)= f(n-1) + f(n-3) + f(n-5) + .... The above equation should be sufficient to tell you why is this the answer to the problem. You can occupy 1,3,5 ... positions at a time let us call it k and question is reframed as finding the solution to the remaining f(n-k) values which is what the equation above tells.

              Now, Just replace n by n-2 in the above equation and we get,
              f(n-2) = f(n-3) + f(n-5) + .... This is just the same as f(n) without the f(n-1) part.

              thus f(n) = f(n-1) + f(n-2)

              → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Here's the intuitive proof I came up with while upsolving.

        First let's solve it like a normal dp problem (forgetting about the fibonacci numbers). We sweep from left to right. Let $$$dp[i]$$$ mean the number of ways to cover only the first $$$i$$$ positions.

        How do our transitions work? First, $$$dp[0] = 1$$$ because there is one way to cover the first $$$0$$$ positions (don't have any towers at all). Now loop over all i's (from left to right).

        Consider the current $$$dp[i]$$$. We can cover some range with exactly one tower if and only if the length of the segment is odd (so we can put the tower in the midpoint). So $$$dp[i]$$$ is equal to the sum of all dp values where the index has a different parity than i (so $$$dp[i] = dp[i-1]+dp[i-3]+dp[i-5]...$$$). Though this would work, it runs in $$$O(n^2)$$$, so it needs to be optimized.

        The optimization is pretty simple. Because you don't care about the actual values of all previous dp's but just the parity. So instead of storing the whole dp array, just have it store 2 values, $$$dp[0]$$$ and $$$dp[1]$$$. $$$dp[0]$$$ stores the numbers of ways to cover an even prefix, and $$$dp[1]$$$ stores the number of ways to cover an odd prefix.

        You still loop from 1 to n but the transitions are now $$$dp[i \mod 2] = dp[i \mod 2] + dp[1-(i \mod 2)]$$$. This is exactly the Fibonacci recurrence.

        Hope this was helpful! Thanks!

        → Reply
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          That's a really nice way to think about it. Thanks.

          → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          hey thanks for sharing your idea . I have implemented the same idea with bottom up DP. but i am not able to do the same with top down DP. Can you please help me with that ?

          → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          @PurpleCrayon how did you come up with the idea that dp[i] is equal to the sum of all dp values where the index has a different parity than i ??

          → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Nice explanation!

          → Reply
        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          "We can cover some range with exactly one tower if and only if the length of the segment is odd (so we can put the tower in the midpoint). So dp[i] is equal to the sum of all dp values where the index has a different parity than i." I understood the first statement that we can cover some range with exactly one tower if and only if the length of the segment is odd but i am not able to understand from this how you drew the second statement as conclusion. Can you please explain?

          → Reply
          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
            ← Rev. 7   Vote: I like it 0 Vote: I do not like it

            consider a random state dp[9],now we can put one tower in 9th city and care about dp[8]. ( [1,2...8][9] ).then we can also cover 9th city if we put a tower in 8th city of power 2.then 8th city also covers 7 and 9 city( [1,2...6][7,8,9] )..so now we have to care about number of arrangement for the first 6 city.thus dp[9]=dp[8]+dp[6]+.....and so one..(i am 5months late posting this comment...dont if it does help anyone !)

            → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I had a different approach to this problem which is quite intuitive imo. We are effectively choosing a subset out of $$$n$$$ towers such that the sum of powers of those towers cover the entire range $$$1-n$$$.This is equivalent to number of odd integral solutions of the equation $$$ p_1 + p_2 + ... + p_r = n $$$.This can be found out easily by converting it to the form $$$ (2*x_1 + 1) + (2*x_2 + 1) + .. + (2*x_r + 1) = n $$$ and finding non negative integral solution for $$$x_1 , x_2 ,... x_r$$$. Multiply this with the probability of choosing $$$r$$$ towers = $$$1/{2^{n}}$$$ to get the required answer solution

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much! It's a great solution.

      → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i am sorry, this might sound dumb but in you solution , ncr(d+x-1,x-1) here what are you actually choosing and from what

      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        number of non negative integral solutions of the equation $$$x_1 + x_2 + ... +x_r=d$$$ is $$$d+r-1\choose r-1$$$

        → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Why this Solution do not get TLE in problem G? I solved only with bfs/dfs. There is some property?

→ Reply
  • »
    »
    5 months ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    As in Tutorial, this solution is at most $$$O(nlog^2n)$$$

    → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this idea seems at first to be O(n^2) in the worst case. I don't know exactly why this works. but the best counter example i could thought of was a graph with O(x^2) vertices for which the number of total iterations of the dfs section is O(x^3). it means this algorithm is at least O(n sqrt(n)), which seems to run fine in time even for my counter example. maybe there is a way to prove that this is still the worst case complexity. it would be great, as this is such a simple solution.

    an instance of this type of graph is given next. in general, this graph has 1/2 (5 x — 2) (x + 1) vertices (x = 3 for this instance) and the dfs runs x^3+x^2 steps in total. I implemented a generator to test for biggers instances. if you draw it starting from bob's chips and then the vertices which are further away, you will probably understand the idea.

    input
    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

@BledDest Can you give more explanation how problem D can be solved. I didn't get the point how the probability can be considered as Fibonacci number. Please help me to understand.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem D Editorial

How this statement is true?

Covering all towns can be expressed as splitting n into the sum of several positive odd integers

Anyone, Please Explain.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Each town that has power must power itself, and an equal number of towns either side of it.

    Suppose it powers K towns to its left, then it must also power K towns to its right. So in total it powers 2*K+1 towns.

    All the towers together power N towns, and the set is partitioned such that no town is powered twice. As such,

    N = sum (i = 1 to j) (2*Ki + 1), where there are j towns receiving power directly, and the ith town powers Ki either side of it.

    The numerator of the answer is the number of unique sets of j and K1,...,Kj such that the equality holds.

    → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the logic of taking max of the array in calculation of k for B?

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We need an end state where each of the n-1 boxes has exactly (TOTAL)/(n-1). Suppose we choose one of the non-max boxes to redistribute: then all the boxes must have at least the max starting value, since we cannot take any away. Therefore max*(n-1) is a lower bound for the total number.

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah but why would there be atleast max in each box?

      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because if there is one box with max, we can't take any out of this box (if redistributing from any of the others). So that box must finish with at least max, and we require all the boxes to finish with the same number, so they must also have at least max.

        → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i successfully solved 1st problem by this=> ```

ll t;
cin >> t;
while (t--) {
    ll x, y;
    cin >> x >> y;
    ll z = abs(x - y);
    ll ans = (x + y) + ((z > 0) ? z - 1 : 0);
    print(ans);
}

``` but i am thinking can it be solvable using dp like other grid paths problem? i am new at dp so i am having a hard time to think about it.so can anyone help me with this if it is possible to solve using dp

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have solved using dp. The idea is that the points on the diagonal(assume it is {x,x}) will always take x+x = 2*x. Other points can be reached from diagonal by this sequence. At diagonal -> Move -> Stop -> Move -> Stop

    #include <bits/stdc++.h>
#define ll long long
const unsigned int mod = 1000000007;
using namespace std;

int main() {
    int t; cin>>t;
    // Store the steps taken to reach diagonals
    vector<int> dp(10001,0);
    for(int i=1;i<=10000;i++)
        dp[i] = 2*i;
    while(t--)
    {
        int x,y; cin>>x>>y;
        if(x==y) {
            cout<<x+y<<endl;
        }
        else if(x<y) {
            int ans = dp[x] + (y-x)*2 - 1;
            cout<<ans<<endl;
        }
        else if(x>y) {
            int ans = dp[y] + (x-y)*2 - 1;
            cout<<ans<<endl;
        }
    }
    return 0;
}
    → Reply
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      making array name as dp doesn't mean that you solved a dynamic programming problem

      → Reply
»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

IN PROBLEM B Why (a.sum() + n — 2) / (n — 1) and not (a.sum()) / (n — 1) i didn't get it

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the formula to get ceil of(x/y) is (x+(y-1))/y

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okk. But when I write ceil function, ceil(x/y), it throws an error, but writing (x+y-1)/y goes successful.

      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe you forgot to cast long double/float/double type to this fraction. For example: ceil(5 / 2) = ceil(2) = 2, but ceil(5.0 / 2) = ceil(2.5) = 3.

        → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But actually you should never try to use floating point numbers then use ceil, always opt to integer operations if possible.

        → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

Why does this give same results, in modular exponentiation?

ll powe(ll x, ll y){
x = x%mod, y=y%(mod-1);
ll ans = 1;
while(y>0){
if (y&1){
ans = (1ll * x * ans)%mod;
}
y>>=1;
x = (1ll * x * x)%mod;
}
return ans;
}

than this

ll powe(ll x, ll y){
x = x%mod;
ll ans = 1;
while(y>0){
if (y&1){
ans = (1ll * x * ans)%mod;
}
y>>=1;
x = (1ll * x * x)%mod;
}
return ans;
}

The only difference is we do y=y%(mod-1) in the first function.

Edit: figured it out its fermat's theorem, thanks everyone

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Why don't people use spoiler while commenting there code?

    → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't your question obvious, let say we want to compute 2^123097521478997542 mod m, then what do you think will be faster computing 2^123097521478997542 mod m or first compute y mod m-1 which will be smaller than equal to y, then compute power?

    → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The answer is obvious, but I remember there was a problem in which the input size it self exceeds mod-1 and everyone who did pow=pow%(mod-1) in advance got WA, be careful.

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm sorry community, I framed it wrong, I actually meant why both lead to same answer.

      A friend of mine later told me its Little Fermat's theorem.

      This was my first comment in codeforces, wasn't aware about the comment standards we need to maintain, are there any resources, on how questions be asked and all?

      → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D problem, if there are 5 cities, the number of ways to break it into sum of odd positive integer is (3)1,3,1 which shows that there are 3 ways,Can anyone help me in understanding how is it the nth fibonacci ie (5)?

→ Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why solutions with complexity O(nmk) can get AC for problem E? The example are below: submission 1 and submission 2

→ Reply
»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone explain problem E's solution a bit more.Thanks in advance! xD!!

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in the editorial of problem b the first para [ceil(sum/n-1)] is the condition when the nephew chooses the box containing the maximum block, right?

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes it is the block with max toys after you have added toys.

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E,why the solution is right?I spend a long time understanding the code,but can't prove it's correctness.The tutorial seems to ignore this.

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you may think that algorithm is incorrect because of prefix and suffix and that one of them may contain some element which should have been in the other one but it doesn't matter because answer for cases like this will not be the final answer anyway because we are considering all possibilities and final answer will be the case where the conditions are satisfied.

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh!miaoa~zhenbuchuo!thank you for your reply!

      → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why i get tle for B?

submission : 99050069

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    whatever error you meet,you can see the data,the data you tle has sum=5e9,and n-1=4,and ma=1e9,your ma should add many times before you can break,so you tle

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is another nice approach to Problem D using combinatorics.

→ Reply
»
5 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For the problem D

how can we find the number of ways in which N can represented as sum of odd integers as mentioned in the editorial ??: To be specific using the following method

It can be calculated with dynamic programming with prefix sums.
→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody explain me ...in the problem toy blocks , why are you adding (n-2) to the array sum ? i.e. 4th line in fun main() function

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ceil function, that is to get the smallest greater integer.

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So Can't we use directly ceil() function available in header cmath ?

      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Since these are integers, ceil function wont work here.

        → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

And everyone ignored the pun in editorial of B. Not I but you.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me on the modular division given in solution of the problem d?Specifically why he has used 'mod-2' during the divide process?? Any document is also helpful...

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

cin >> a >> b; cout << a + b + abs(a — b) — (a ^ b ? 1 : 0) << endl;

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please don't add codes like this

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the divide function in problem D is mul(x, binpow(y, MOD — 2)) ? I understand the idea behind mul() and binpow(), but why they can perform the divide operation?

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It uses Fermat's little theorem to calculate Modular multiplicative inverse.

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm a bit confused about problem B's description. For example, the tests case 0,3,0. Why can't the answer be 1? You put one block into bin 1, then the kid puts 1 block from bin 2 into 1 and 2 blocks from bin 2 into bin 3. You're left with an even number of blocks.

Is it because the kid is the one that is choosing a random box and you have to make sure no matter what he chooses, that he is happy?

Thanks :)

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. The kid can choose any box he wants and we have to make sure no matter which box he chooses it is possible to make the rest of the elements equal.

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me what's wrong in my solution for problem C. Submission : 99756850

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider this case: )()( your solution will return 0 although the answer is 1; and cuz find() is O(n), it also will get TLE in huge cases.

    → Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

nothing!

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a $$$O(nm)$$$ solution for problem E. Basically, we do scanline. For each participant, we brute force over the left author, and see when can we have the left author as a winner for that participant, and then we do the same for right author. It's really cool IMO. 100792298

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

About question D, why didn't standard code reduce the fraction, or didn't need it at all.

→ Reply
  • »
    »
    5 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry， I've proved that the same answer will be obtained after reduction.

    → Reply