FieryPhoenix's blog

By FieryPhoenix, 10 days ago, In English

1515A - Phoenix and Gold

Idea: FieryPhoenix

Tutorial
Solution

1515B - Phoenix and Puzzle

Idea: FieryPhoenix

Tutorial
Solution

1515C - Phoenix and Towers

Idea: FieryPhoenix

Tutorial
Solution

1515D - Phoenix and Socks

Idea: FieryPhoenix

Tutorial
Solution

1515E - Phoenix and Computers

Idea: FieryPhoenix

Tutorial
Solution

1515F - Phoenix and Earthquake

Idea: dragonslayerintraining

Tutorial
Solution

1515G - Phoenix and Odometers

Idea: dragonslayerintraining

Tutorial
Solution

1515H - Phoenix and Bits

Idea: dragonslayerintraining

Tutorial
Solution

1515I - Phoenix and Diamonds

Idea: dragonslayerintraining

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +368
  • Vote: I do not like it

»
8 days ago, # |
Rev. 2   Vote: I like it +61 Vote: I do not like it

Thanks for the nice problems!

»
8 days ago, # |
  Vote: I like it +91 Vote: I do not like it

Hmm Tutorials here pretty fast. I guess those edu rounds require some sort of godly Sacrifice before they release solutions.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    They have a 12 hour open hacking, so cant release solutions. lol

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Even after those 12 hours they make us wait. atleast in prev edu round

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        Maybe its bcoz edu round setters have to write lot of problems in a month, so they get late in writing editorial.

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

          ok makes sense. it may be they have solutions but either they got that wrong or someone came up with better solution which may get updated in editorial. Lol from now on i will take a chill pill after a contest

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Actually even though such delay makes sense AFAIR it was mentioned that there is no requirement to delay editorial until the end of the hacking and it is up to the authors.

»
8 days ago, # |
Rev. 4   Vote: I like it +128 Vote: I do not like it

Phoenix and Editorial.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks :')

»
8 days ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks for the nice problems!

»
8 days ago, # |
  Vote: I like it -12 Vote: I do not like it

Am I missing something for B? A 3x3 square can be formed with 14 pieces with one 4 piece and five 2 pieces.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    nope they cant be. You can't cut or deform isosceles triangles to fit in square

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Ah, I subconsciously assumed 2 * short side of triangle = longer side. This is embarrassing...

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope you cant form 3x3 with 14 pieces, either form 3x3 with 2pieces which will require 18 pieces(2) or form 3x3 with 4 pieces which will require 36 pieces(4). Refer to first and second test case explanation for better understanding,also check the side lengths of both of the test cases.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Variation of Problem D: We are only given number of left and right socks and not which color sock is left or right. We would have to answer for worst possible case of assignment of left and right. What would be approach in this question?

»
8 days ago, # |
  Vote: I like it +130 Vote: I do not like it

You can actually AC with a O(n^4) solution on E using a very stupid method: you can precompute all values up to 400 without any mods locally (takes a few minutes), convert them to a larger base using ASCII characters, and store the large values (ones where n^4 is too slow) in a string that is just under 64kb in size :P

Accepted

  • »
    »
    8 days ago, # ^ |
      Vote: I like it -79 Vote: I do not like it

    I doubt so if this was a hacking phase. Someone might be friend you now just for the sake of hacking solutions in later edu rounds. Just Saying

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    takes a few minutes

    took 37 minutes to me

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Wow man this is just crazy!!

  • »
    »
    8 days ago, # ^ |
    Rev. 4   Vote: I like it +11 Vote: I do not like it

    I like the way you think :)

    Also here is a pure O(n^4) solution getting accepted comfortably, with a little bit of pruning and unrolling.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +115 Vote: I do not like it

      I passed with a pure $$$O(n^4)$$$ too 114926425.

      Let $$$f_{i,j}$$$ be the number of ways to cover a segment of length $$$i$$$ using $$$j$$$ steps.

      We can get an $$$O(n^4)$$$ approach by finding the last to take over all.

      At first I used dfs, which took about $$$120s$$$.

      Then I changed it to a dfs-free approach, which took about $$$60s$$$.

      Then we can see that if $$$f_{x,y}$$$ is zero when $$$y<x/2$$$ or $$$y>x$$$,then it took $$$30s$$$.

      When you know the last place to choose, you also have to know how many steps you are going to use in the left part. Just check the places with non-zero values, then it took $$$15s$$$.

      Then I replaced some mod in my code and it took $$$8s$$$.

      If we are calculating $$$f_{n,m}$$$,let $$$x$$$ be the last position to choose, the answer is the same if we choose $$$n-x+1$$$, it took $$$4s$$$.

      Then I used Fast_Mod instead of regular mod,it took $$$3s$$$ on my PC.

      Submitted it and it passed in less than 2 seconds!

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Haha sounds exactly like the way I solved it. Was a bit skeptical whether it could be done in this way but CF is quite fast.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    woah, never thought of that. Very smart approach :)

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I also passed with $$$O(n^4)$$$, with heavy constant optimization and precomputation. It ran locally in ~$$$1.45s$$$ and got accepted in $$$2854ms$$$ (was $$$2932ms$$$ in pretests and I got scared it might FST)

    All I did was precompute all nCr terms and restrict the bounds of looping on the dp array to not compute useless cells.

    Code: 114943295

»
8 days ago, # |
  Vote: I like it +39 Vote: I do not like it

Anybody understand E solution

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain me 3rd in detail ? I would be thankful.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    u need to make m towers with the n blocks of various sizes none of which exceed size x now pick 2 towers abs( height tower 1 — height tower 2) <= x if the above is not correct for your arrangement then your arrangement is wrong

    other wise just print which block went in which tower

    cheers

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In third problem, the idea is to greedily put the next block in the smallest tower so far. Which can be done using a set as a set stores elements in sorted order, so the first element would be the smallest (in this case it would be the smallest tower's height and index), then we can just add the current block to this tower, and update its height (by removing it from the set and inserting the modified one).

    PS: The way this greedy approach works is that, if we don't add the current block to the smallest tower we would be increasing the difference in their heights, which might get bigger than x, so adding to the smallest tower always ensures that, the difference will never exceed x as the heights of all the blocks is not greater than x.

    I hope this helps :D

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    see this 114972329

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

any clues what's wrong in C problem ? 114955920

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem I was pretty similar to this one: 1439C - Greedy Shopping

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Was $$$n$$$ set to $$$400$$$ in E to cut the precalc solutions (the minimal file size to decode all the answers is 66kb while cf accepts only 65kb files)?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This person says they did use pre-calculation and got the file size to 64kb and their solution got accepted. Maybe they found a work-around. https://codeforces.com/blog/entry/90236?#comment-786797

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      They stored the values starting from $$$100$$$ which fits in $$$64$$$ kb; storing all the values doesn't fit

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, it fits: 114952738

        Furthermore, I have used only 100 different symbols.

        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          which $$$100$$$ symbols? are the ones below $$$32$$$ allowed?

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes, surprisingly, you can use them. The only exceptions are '\n', which I've used as a separator and '$' — I had troubles escaping it in kotlin. So, I have used symbols with codes 14..113 plus 127 instead of dollar sign.

»
8 days ago, # |
  Vote: I like it +33 Vote: I do not like it

Problem E has $$$O(n^2)$$$ solution. The formula:

$$$\sum_{l = n/2 + 1, z = n - l}^{n}2^{l - z - 1}(\sum_{i = z + 1}^{1}(-1)^{z + 1 + i}C_{z+1}^{z+1 - i}(i)^l)$$$

$$$l$$$ denotes amount computers turn on manually and $$$z$$$ — turn on automatically.

submission: https://codeforces.com/contest/1515/submission/114961141

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone explain Problem B in detail? please!!

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Even after completion of system testing, it is showing pretest passed in B and a negative in standings. What should I do? https://codeforces.com/contest/1515/standings/friends/true

»
8 days ago, # |
Rev. 8   Vote: I like it +63 Vote: I do not like it

E can also be solved in $$$O(N^2)$$$.

We're solving for $$$ans(N)$$$

Brief: Let $$$f(k)$$$ be the number of ways to solve when the computers can be split into k non empty subarrays. i,e, $$$k-1$$$ computers aren't turned on manually.

The goal is to solve for each $$$k$$$ in $$$O(n)$$$ and add them separately.

Let's call the number of size $$$m$$$ sequences that contribute to the $$$ans(n)$$$ be equal to $$$g(m,n)$$$

$$$g(n,n) = 2^{n-1}$$$ (Observe the reverse direction of turning on computers. We optionally increment the suffix or prefix)

For a given sequence of lengths of subsegments, $$$S_1, S_2, S_3..S_k$$$, we can solve for each subsegment independently (for each subsegment, it would be $$$g(S, S)$$$ and multiply this product by $$$\frac{(\sum{S_i})!}{\Pi(S_i!)}$$$, where $$$S_i>0$$$. And, also, $$$\sum_{0\leq i \leq k}{S_i} = N - k + 1$$$ (k — 1 is the count of automatically turned on computers)

So, $$$f(k) = \sum_{valid \space set \space of\space sequences \space S}(\Pi_{0 \leq i \leq k}{g(S_i, S_i)} \cdot \frac{(\sum S_i)!}{\Pi(S_i!)})$$$,

Given $$$k$$$, $$$\Pi_{0 \leq i \leq k}{g(S_i, S_i)} = 2^{n-2k+1}$$$

$$$h(k) = \sum_{valid \space set \space of\space sequences \space S}\frac{1}{\Pi_{0 \leq i \leq k}(S_i!)}$$$ for $$$S_i > 0$$$

$$$f(k) = 2^{n-2k+1} * (n - k + 1)! * h(k)$$$

$$$h(k)$$$ is the coefficient of $$$x^{n-k+1}$$$ in $$$(\frac{x^1}{1!} + \frac{x^2}{2!} + ...)^k = (e^x — 1)^k$$$.

Using this, $$$h(k)$$$ can be calculated in $$$O(k)$$$ if we expand $$$(e^x - 1)^k$$$ in binomial terms, and similarly $$$f(k)$$$.

$$$ans(n) = \sum f(k)$$$

code

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is this a fft solution?

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Doesn't use fft. Sorry if I wasn't clear with expanding $$$(e^x - 1)^k$$$. It's equal to $$$\sum_{0\leq i \leq k} {\binom{k}{i}e^{ix}(-1)^{k-i}}$$$.

      And, coefficient of $$$x^r$$$ in $$$(e^x - 1)^k$$$ would be $$$\sum_{0\leq i \leq k} {\binom{k}{i}\cdot\frac{i^r}{k!}(-1)^{k-i}}$$$

      • »
        »
        »
        »
        8 days ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        I don't understand the part where you just defined h(k). Is it a known mathematical fact? How did you come up with that, also it doesn't talk about how for a given k you consider all the possible ways of dividing array in k parts, which I think by stars and bars is n-k+1Ck-1

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Not only partitioning but the order in which the operations are performed is important here e.g. you can perform an operation in Si and then in Sj (i != j) but the order of operations within a segment is not important assuming the order is fixed (all the orders are considered in 2^(n-2*k+1) ).

          Hope it clarifies.

          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The part where you talk about Sj(!=j) is why he is multiplying it by the factor \Pi_{0 \leq i \leq k}{g(S_i, S_i)} \cdot \frac{(\sum S_i)!}{\Pi(S_i!)}. According me this incorporates for a particular partition. There can be a lot of partitions which I don't know how he is accounting them

            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              That was my bad, I corrected my comment now.

              It's the sum over all such partitions of size $$$k$$$. Not just for a single arbitrary partition.

              Each valid partition of size $$$k$$$ is being accounted in the coefficient of $$$x^{n-k+1}$$$ in $$$(\frac{x^1}{1!} + \frac{x^2}{2!} + ...)^k$$$. Look at how the coefficient is incremented by $$$\frac{1}{\Pi_{0 \leq i \leq k}(S_i!)}$$$ for each partition.

              $$$\frac{x^{S_1}}{S_1!}$$$ from the first $$$e^x-1$$$, $$$\frac{x^{S_2}}{S_2!}$$$ from the second $$$e^x-1$$$ and so on subject to $$$\sum S_i = n - k + 1$$$

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess the given mod on E is to stop fft solutions, though 114961513 it can be passed easily, sadly i finished some minutes after the end :(

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +85 Vote: I do not like it

    I think the main reason for variable mod was to avoid people from solving it in $$$O(n^4)$$$ offline and storing all 400 answers.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Yeah that's probably the real reason, but it killed my $$$O(n^3 log n)$$$ fft solution, so i had to squeeze it in $$$O(n^3)$$$.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually,look at this:

      A crazy approach

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Can some explain problem E in an easier way ? Editorial is difficut to understand for me.

»
8 days ago, # |
  Vote: I like it -17 Vote: I do not like it

Can anyone please tell me the test case where my code is failing. https://codeforces.com/contest/1515/submission/114957794

»
8 days ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

Why my submission of C got pretest passed but did not enter the system test phase? submission during the contest

After the system test I submit the same code and get AC.114960806

UPD: solved

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Anybody please explain E in easier way

»
8 days ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

..

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    x=1, although there in the array there is 6, which doesn't respect (x>=a[i], for every 1<=i<=n)

    Note, though, that there are very few cases when such grave mistakes are allowed to pass through the coordinator's 'radar' and be part of a contest. And in this case, this problem got solved by thousands. It's very unlikely for all of those to solve the problem without a correct and rational basis. Before posting something like this, try prove their demonstration wrong, check yourself, and repeat

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    because your input is incorrect. If will give correct input, it will give correct answer))

»
8 days ago, # |
  Vote: I like it +39 Vote: I do not like it

E could also be solved easily in O(n^2) using connected components DP (If you don't know what that is refer to this blog.

Code: https://codeforces.com/contest/1515/submission/114935154

»
8 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Thanks for comments in code!

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They're actually in Portuguese so I don't know if they'll be of any help at all. I guess you can always throw them at a translator and see what you get.

»
8 days ago, # |
  Vote: I like it -31 Vote: I do not like it

can anyone help me i don't know why it is showing WA in problem A

include

using namespace std; int main() { int t; cin>>t; while(t--) { int n,x; cin>>n>>x; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; int ans[n]; int fw=0; int indexoffw=0; int f=0; int i=0; do{

fw=arr[i];
            if(fw>x)
            { f=1;
            indexoffw=i;
                break;}

        i++;
    }while(i<n);


    if(!f&&(n!=1))
    {
        cout<<"YES"<<endl;
        for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";
        cout<<endl;
        break;
    }
    if(n==1&&arr[0]==x)
    {
        cout<<"NO"<<endl;
        break;
    }
    if(f){
    ans[0]=arr[indexoffw];
        int k=1;
        for(int i=0;i<n;i++)
    {
        if(i!=indexoffw)
        ans[k++]=arr[i];
    }
        cout<<"YES"<<endl;
    for(int i=0;i<n;i++)
    cout<<ans[i]<<" ";
        cout<<endl;
    }
    else
        cout<<"NO"<<endl;

}

}

»
8 days ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

Problem solved

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Is that an isosceles triangle?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no it's not thank you I understood the idea

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because the triangles are right isosceles triangles.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The triangles are isosceles triangles

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I made the same mistake, which is assuming that all types of triangles are allowed. Didn't read the statement properly :/

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is pair stored in set in sorted form? If yes then sorted by first or second?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes std::set is always sorted. It compares by first, if it is the same, only then it compares by second

»
8 days ago, # |
  Vote: I like it +17 Vote: I do not like it

You can also solve A by randomly shuffling the array.

»
8 days ago, # |
  Vote: I like it +18 Vote: I do not like it

My solution to the problem I is similar with the author's one, but slightly differs, so I describe it here.

First of all, again, we sort all diamonds first by price, then by weight, now the guy will take them from left to right. After this we'll need the data structure which can do this:

Given an array $$$w_i$$$, we consider points $$$(i, w_i)$$$ on the plane and do queries "add $$$x$$$ to a single point $$$(i, w_i)$$$", "calculate the sum on $$$[0, x)\times[0, y)$$$" and "given $$$c$$$ and $$$x$$$, find the greatest $$$y$$$ so that the sum on $$$[0, x)\times[0, y)$$$ does not exceed $$$c$$$". It's already pretty standard.

Queries of type 1 and 2 are straightforward. To handle query 3 c, let's see what happens. We can ignore all diamonds of weight $$$> c$$$, we take zero of them. For each other diamond we either grab the whole pile of it, or we can't do so. Let's find the first pile which we cannot take. It means answering the question "what is the greatest $$$i$$$ so that the sum on $$$[0, i)\times[0, c)$$$ is at most $$$c$$$". When we find this $$$i$$$, we take as much as we can from the $$$i$$$-th pile of diamonds and proceed further: if we are now at position $$$pos$$$ and we have $$$c'$$$ space remaining, we find out "what is the greatest $$$i$$$ so that the sum on $$$[0, i)\times[0, c')$$$ is at most $$$pre + c'$$$", where $$$pre$$$ is the sum on $$$[0, pos)\times[0, c')$$$. After each taking as much as we can, but not the whole pile, our space becomes $$$c\to (c\pmod{w_i})$$$, that is, reduces at least twice.

Now it seems to me that the complexity of this is $$$O(q\log{C}\log^2{n})$$$ without and $$$O(q\log{C}\log{n})$$$ with fractional cascading, but my first attempt without fc (segment tree of fenwick trees) and optimizations in general got ac in 3.5s (unfortunately, I didn't manage to debug it in time).

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ah yes, my code: 114960373, feel free to hack

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Did you rely on the fact that either query segments are small, or number of operations would be small? It looks like this solution has good constant because of the things above. Also I came up with the same solution, however with something like sqrt decomposition by queries. Then you could make a query of $$$w$$$ with persistent segment tree with precalc before each query block, $$$O(q \sqrt q \log q)$$$.

    UPD: I guess I had something different in my mind when I came up with my solution, although it was requiring the same queries as yours. Anyway, your solution runs in $$$O(nq)$$$ on the test with weights equal to $$$1, c, 1, c-1, \ldots$$$, since you would make one query for each $$$1$$$.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Editorial for problem C: https://youtu.be/5S6mjYYkdOA

  • »
    »
    6 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can someone please explain why my solution to C works in the context of the logic given in the editorial? I have implemented a greedy solution using sorting without using heap.

    https://codeforces.com/contest/1515/submission/114944125

    I have sorted the array in the reverse order. Then I have greedily assigned first m blocks to m towers and then the next m blocks to m towers but in reverse ans so on. The assigned towers will be 1...m m....1 1....m and so on. If the blocks were 5 3 3 2 1 and there are 2 towers my answer would be 1 2 2 1 1. Here blocks are not being assigned to towers with the least height.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please prove the logic behind this AC approach to the problem C, which neither uses set nor min heap?
lld : long long int
st : first
nd : second
all(x) : x.begin(),x.end()

	lld n,m,x;
	cin>>n>>m>>x;

	vector<pair<lld,lld>> h(n);
	vector<lld> ans(n);
	for(int i=0;i<n;i++)
		cin>>h[i].st, h[i].nd=i;

	sort(all(h));
	for(int i=0;i<n;i++)
		ans[h[i].nd]=i%m+1;

	cout<<"YES\n";
	for(auto i:ans)
		cout<<i<<" ";
	cout<<endl;

Link to the accepted solution: 114961797

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    I think it's a smart way of putting the "next" block in the smallest tower currently. (just like the editorial says)

    You sort h (so it is now h[1]<=h[2]<=...<=h[n]). If you assign the first m heights to different towers in the end the smallest tower will be the one that got the h[1] height, that is why you give it h[m+1], but now the smallest tower is the one that got h[2] that's why you give it h[m+2] etc.

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      Another way to see it is to observe that when, as described in the editorial, you remove the smallest tower from the bottom of the sorted list and add a block to it, it becomes the highest and goes to the top of the list, so the list of towers is effectively rotating.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah! understood your point, thanks a lot! $$$\ddot\smile$$$

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can prove it, if take subsequences of two different towers and summarize difference of pair corresponding blocks.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Bad tests in problem A. My wrong solution passed all the tests, although it should have failed on test: 5 5 1 2 2 2 2 (My solution outputs NO)

»
8 days ago, # |
  Vote: I like it -15 Vote: I do not like it

Video Editorial for Problem D: https://youtu.be/e4U4_W9T7Xk

»
8 days ago, # |
Rev. 3   Vote: I like it -21 Vote: I do not like it

I confirm mine is the easiest solve for problem D.Feel free to check it out.
P.S. 114917152

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1515/submission/114909875

why did this give tle ??i have used sqrt time only to check sqaure? plz tell........

»
8 days ago, # |
  Vote: I like it -11 Vote: I do not like it

https://codeforces.com/contest/1515/submission/114909875 \ why does this give tle ??on problem b sqrt n is accepted as mentioned in editorial... i tried to again submit after contest with fast /io but again it gave tle...plz tell

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    You're calculating isPerfectSquare() for each n, this gives you a complexity of O(t*sqrt(n)). You can precalculate this squares before all the tests and store them on a set, this gives you a complexity of O(t*log(number of squares)).

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

IN C does it make sense to include "NO" in the question or it was just there to create a confusion.

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

someone please explain why i am getting wrong answer in test 3 in D here's my submission https://codeforces.com/contest/1515/submission/114967116

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please tell me how you can quickly calculate (n + m!) / n! / m! % MOD (This is in problem E). In some solutions I've seen some "ifact" counting besides the usual factorial, but I can't figure out what it is.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Precompute the factorials from 1 to (n+m) in O(N+M) time and store it in an array, which you can do with a for loop. Also calculate the "modular inverse" of each of the factorials. Instead of dividing, multiply by the modular inverse.

    Geeks for geeks for modular inverse: https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

    My code for E where I do exactly this: 114939759

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain your approach for the problem E ?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        It is exactly the same as the editorial.

        Basically, you have "blocks" of computers where you manually turn them all on (none are automatically turned on). For a block of size n, there are 2^(n-1) ways to turn them on so that none of the computers are not turned on automaticallly, as detailed in the editorial.

        You can think of a final answer as a series of blocks where there is exactly 1 computer turned on automatically between each block.

        There are O(N^2) states in the dp and O(N) transitions. dp[n][m] = answer for the first n numbers, where m of those computers were manually turned on. At each point have another for loop to add a block to the end where you left off. I use choose to account for the fact that you don't have to do the blocks in order, or do finish one block before starting another.

        Then you end up with the formula in the editorial.

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you explain how does the "exactly 1 computer turned on automatically between each block" even work? Since 1 5 3 would simultaneously turn on 2 and 4. Am I missing something?

          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Nevermind I'm stupid the statement meant location-wise, not time-wise

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Thank you so much!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone try to hack 114954966. I think it should have given TLE.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I don't see why it should TLE, because it has only one for loop which runs $$$\sqrt{n}$$$ times for each test case. Correct me if I am wrong.

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

What a Nice Contest!

»
8 days ago, # |
  Vote: I like it +19 Vote: I do not like it

Question on problem H: How do you split/merge tries?

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone kindly explain why greedily adding the 2 smallest values in the array not work in c.

like if we have [2,4,7,9,10] and if we want 3 block just add the smallest 2 and replace, by this we get [6,7,9,10] and then again do the same thing, thus getting [13,9,10] the max difference is 4 which is okay, if we were to do any further operation we would have done that to 9,10

but this gives WA, can anyone suggest a counter example

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    x = 1

    a = [1, 1, 1, 1, 1, 1]

    after the first four operations, you'll have [2, 4], and the difference is > 1

»
8 days ago, # |
Rev. 3   Vote: I like it -13 Vote: I do not like it

In the proof of problem $$$B$$$, in general, the triangle shorter side length can be irrational, hence the square area can be irrational as well. We can say that if the shorter side length is $$$x$$$, the square area will be: $$$(a+\sqrt{2}b)^2x^2$$$, if we divided this by the area of one triangle $$$\dfrac{1}{2}x^2$$$ to get the number of triangles constituting the square we will get $$$2(a+\sqrt{2}b)^2$$$, which is irrational if $$$a$$$ and $$$b$$$ are both non-zeros, and triangles count can not be so.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem 1515C: Can you please check out this solution and see if it is the correct one. The logic sort all the heights in decreasing order and then assign the heights to the towers in a spiral manner, i.e. first k blocks are assigned in increasing order of tower numbers and the next k in decreasing order and then the next k in increasing and so on.

I am attaching a link to my solution, if possible can you please see it.

114893372

This solution uses O(NlogN) sorting and then assigning the heights in O(N) rather than the one given in the tutorial, which will be slower than mine.

If the solution is wrong can you please provide a test case that will fail my solution.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, your method is correct.

    We can add imaginary blocks of height 0 at the end of the sequence so that the total number of blocks is a multiple of $$$m$$$, such that in each pass, every tower is assigned a block. After sorting, consider the difference between the maximum and minimum height added in each pass of the towers. The sum of these differences is less than or equal to $$$x$$$.

    Therefore, the maximum difference of heights of the constructed towers is less than or equal to the sum of differences in each pass, which is less than or equal to $$$x$$$.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, actually I did the math roughly during the contest and got a little nervous about it as I wasn't able to hardproof the solution. Thanks for the contribution.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was wondering why rating changes for global rounds are very fast whereas educational rounds and div 3 rounds take a lot of time?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is because of the 12 hour open hacking phase after educational and div 3 rounds. The successful hack tests are added to the main system test cases and then all the solutions are re-judged. So it takes 12 hours to completely judge the solutions and update the ranks

»
8 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Nice Round!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

A proof for the solution of problem $$$D$$$:

Assuming $$$l\geq r$$$, we only need to consider recoloring and moving $$$\dfrac{l-r}{2}$$$ socks from $$$l$$$ to $$$r$$$. Moving any $$$sock_i$$$ from $$$r$$$ to $$$l$$$ should be accompanied with moving $$$sock_j$$$ from $$$l$$$ to $$$r$$$, which is equivalent to recoloring $$$sock_i$$$ to $$$c_j$$$ and $$$sock_j$$$ to $$$c_i$$$, so we do not need to consider this type of operations.

For the step of moving $$$\dfrac{l-r}{2}$$$ socks from $$$l$$$ to $$$r$$$, we need to so in a way that minimizes the recolorings. So, we need to do it in way that maximizes $$$\sum_{i=1}^n min(l_{count_i}, r_{count_i})$$$ for all colors $$$i$$$. Which is equivalent to first matching the pairs that are ready for matching between $$$l$$$ and $$$r$$$, then moving and matching pairs with same colors in $$$l$$$, as mentioned in the editorial.

»
8 days ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

Problem D : My code is giving runtime error on tc 3 . Someone please help — > https://ideone.com/veYC42

Please Help

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Very Nice Contest ! Had interesting problems rather than some wierd and boring problems ! Thanks for the round! Hope to see this type of round even more !

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the nice problems

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help in figuring out what is wrong with this solution for problem c: https://codeforces.com/contest/1515/submission/114996358 I have tried taking the two minimum heights and merge them until the remaining elements are exactly m.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can C be done using priority queue?

»
8 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Nice Contest

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In the first approach for problem F, when two disjoint sets are merged, then the list of edges of the two sets are also merged. It seems that this merging operation is very costly and would lead to TLE, but in practice it didn't. Is there an explanation for why this is the case?

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

For problem E, how is the answer for the case $$$n = 4$$$ given as $$$20$$$. I can come up with only $$$16$$$
1. xx-x ($$$2!\times 2^1 \times 2^0 = 4$$$ ways)
2. x-xx ($$$2! \times 2^0 \times 2^1 = 4$$$ ways)
3. xxxx ($$$2^3 = 8$$$ ways)

Here x denotes the positions turned on manually and - denotes those that appear automatically.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    For the first two conditions, it is C(3, 2), not 2!.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    For the first 2 cases, it should be 6 ways. In the first case: xx-x it is 2^1 for xx 2^0 for x and since we can rearrange the steps of left and right side, i.e. 3C2.

  • »
    »
    8 days ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    (1 2 4) all combination = 3! = 6 ways

    (1 3 4) -------------------- = 6 ways

    (1 2 3 4) = 8 ways

    Total : 20 ways

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      how did you calculate for 1 2 3 4 case ?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can understand like this.

        No of ways to turn on all computers(1,2,3,4) are

        by turning on 1 computer = 0 ways

        by turning on 2 computer = 0 ways

        by turning on 3 computer = 12 ways (as explained in the above comment)

        by turning on 4 computer = 8 ways

        total : 20 ways.

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    So, finally we have the following formula : Let total number of x is $$$X$$$ and length of segments are $$$x_1$$$, $$$x_2$$$ upto $$$x_k$$$, where $$$k$$$ is the number of segments. Then the number of arrangements are $$$\frac{X!}{x_1! x_2!\dots x_k!}2^{x_1-1}2^{x_2-1}\dots2^{x_k-1}$$$.

»
8 days ago, # |
Rev. 2   Vote: I like it +57 Vote: I do not like it

For problem E, I have an O(N^2) solution which is extremely, extremely easy to write. It uses a technique similar to one used in CEOI 2016 Kangaroo.

Denote dp[i][j] as the number of ways you can have i places "filled in", with j separate contiguous segments. These "segments" must have a space of at least two between them (or else the one space in between would be automatically filled in).

Then, you can run an O(N^2) dp with O(1) transition. For example, each time you can merge two segments, add to one segment, or create a new segment. There are just 5 cases to handle.

Code: 115003639

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Nice!

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice solution. Bud i can't understand the transition

    dp[i+2][j] = (dp[i+2][j]+dp[i][j]*(j<<1))%mod;

    We have j separate contiguous segments with i turn on . How we can jump j segments and i+2 turn on and why multiplier j<<1?

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      what this means is, you can increase the length of a segment by two.

      Let's say I have something like

      ....XXXX....
      

      In one move, I can turn it into

      ..XXXXXX....
      

      by filling in the leftmost X.

      This way, there are j*2 ways to do this, by picking either of the j segments to increase in length, and for each segment choosing left or right. (j<<1 just means j*2, sorry this is not very intuitive but it is a habit)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C, mistakenly, I was solving a different problem. How to solve this?

We have to put those n blocks in m tower such that the sum of blocks in any tower does not exceed X.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think it is NP-Hard.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to formally say it though ? Can you explain ?

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          8 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Isn't Bin Packing different from this question ?

          • »
            »
            »
            »
            »
            »
            8 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No. It is exactly what starboy_jb described.

            • »
              »
              »
              »
              »
              »
              »
              8 days ago, # ^ |
              Rev. 2   Vote: I like it -8 Vote: I do not like it

              Ohh my bad, I read it wrong. How about this then :

              Given n items A[n] with no restriction on 1<= A[i] < 1e+9, is there a way to partition these items into K bins, such that the difference between the max and min bin values <= x.

              Is this polynomial-time solvable ?

              • »
                »
                »
                »
                »
                »
                »
                »
                8 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I am unsure. However it feels like as if there is none...

                You'll have to ask someone more skilled than me to prove it is NP-Hard or come up with a polynomial time solution.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 days ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                No, consider $$$K=2, x=0$$$.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Ahhh yes of course

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  What was the revelation ? As far as I know this can be solved with Knapsack Dp. But can we say for every K and x it is possible ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 days ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

                  No, the knapsack dp works in $$$O(n^2*max(a_i))$$$, which clearly doesn't work for $$$a_i \leq 10^9$$$; $$$max(a_i)$$$ isn't polynomial in input size.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think for m = 2, this becomes something of the kind of partition problem that we can solve by DP. Not sure how to do for m > 2.

    Problem Statement : Given N numbers, partition these into 2 sets(S1, S2) such that the difference between S1 and S2 is minimised. If this difference <= x, then it is possible else not possible,

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1515/submission/114949655 can anyone help me to figure out why is this logic wrong?

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Uh,If you have duplicate numbers in problem A,how to solve it?

I have an idea,and this is the link that I accepted.

I don't know if it's correct. If anybody knows,please tell me,thanks a lot.

sorry,my English is poor :(

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

explain C again..its code not able to understand

»
8 days ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

Great contest! Missed first 2 ques by some silly mistakes and got demotivated to try more :(

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the cool problems.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

PROBLEM A solution goes wrong for 3 6 6 6 6

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for C is almost same logic mentioned above. Fist I take all the heights and push them into a priority queue .Then I pop the two shortest height from the queue and push their sum back to the queue until the size of queue is not equal to m. I also maintain the indexes.
But this idea is wrong is some test case. This idea gives the result of two towers that their height's difference is greater than x in some test case. Why it is happening? Can anyone help?

My solution: https://codeforces.com/contest/1515/submission/114950963

  • »
    »
    8 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Consider this case :

    1
    6 2 2
    2 2 2 2 2 2

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider 6 blocks of size x, and number of resulting towers=2.

    So you will make, in that order, towers of size 2x, 2x, 2x, 4x.

    Then diff is 2x, which is bigger than x.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell the solution to problem E in detail?

  • »
    »
    7 days ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    I think you want to understand this transition

    dp[len+k+1][cnt+k] += dp[len][cnt] ⋅ (ncr(cnt+k,k)) ⋅ power(2,k-1)

    dp[len+k+1][cnt+k] = number of ways to on (len+1)th computer automatiacally and from len+2 to len+k+1(total k computers) on manually

    dp[len][cnt] = number of ways from len = 1 to len = len and we manually on cnt computers now we have dp[len][cnt] and we know the number of ways to on all k computers manually (from len+2 to len+k+1) is power(2,k-1) and to select these k computers we multiply it by ncr(cnt+k,k)

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

IN Q Phoenix and Gold ...if we put test case 1... 8 56.... 34 22 22 34 34 34 34 34 Answer is wrong as it gives ... YES..... 34 22 22 34 34 34 34 34 hece weight will explode.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone has a proof for E? Wouldn't the case 1 5 3 (manual turning on) not be part of the count for the solutions? since 1 5 3 would lead to the simultaneous automatic turning on of 2 and 4. While we're building the solution thinking about several manual computers, one automatic computer, several manual computers, and so on.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nevermind I'm starting to think I have some sort of idea why it works even if sometimes it can be 2 at once. Suppose 2 6 4. Then we can take 2 6 4 as activated manually and 5 activated automatically. We then don't really care if 3 is activated automatically or manually. Why? The elements smaller than 3 (1) are allowed to be anywhere after 3 in the next sequence. The elements bigger than 3 will be placed just as in an activated manually sequence. So it doesn't really matter. Why can we get away with the case for 1 2 3 4 5 as similar to other cases such as 2 3 4 5 6 or 1 4 6 7 8? The 1 2 3 4 5 can be considered the order if we were to sort the elements. And the principle remains the same.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone briefly explain why there will always a solution exist in Problem C?? Why will we never get a max difference greater than x if we always merge with the smallest height deck?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "A single block never exceeds the height of x".

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. "A single block never exceeds the height of x". that is true but how does it imply that the max difference between two decks will also not exceed x.

      2. Why this soln is not working?? Collect all the N towers in the set, merge the two smallest heights till the size of set is greater than m.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        1. If a single block cannot exceed the height of x, the only way the difference between two blocks can be greater than x is if you add a block to a taller tower. If we always add a block to the shortest tower, the height of that tower increases by only the height of the added block, which is less than x.

        2. Sorry I do not understand your approach.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How would one approach C if a single block could exceed the height of x? Would the same greedy strategy work? I am having a hard time with the proofs.

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please tell me what's wrong in my code for problem D? https://codeforces.com/contest/1515/submission/115072254

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain D, editorial is too messy and so many variable is used in them.I can't able to figure it out as a whole. Thanks in advance

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can anyone please help me in understanding where am I going wrong in my code for problem F. I am getting WA on test 16 saying wrong output format Unexpected end of file — int32 expected.

Here is the link to MY CODE

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I know it may be too late but in 1515C time complexity for each test case can be precise to $$$O(n \log{m})$$$. That's because a set or a heap are built from $$$m$$$ pairs.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I understood the first part of the editorial for problem E but I am not able to understand how the segments are merged using binomial coefficients, can somebody explain it to me.

»
6 days ago, # |
  Vote: I like it +13 Vote: I do not like it

E can be solved in $$$O(n^2)$$$ time.

Let $$$f_{n,m}$$$ be the ways to complete $$$m$$$ paragraphs, where these paragraphs contain $$$n$$$ computers totally.

The answer is $$$f_{n,1}$$$.

(1) merge two adjacent paragraphs:

$$$f_{i+3,j-1}\leftarrow(j-1)\times f_{i,j}$$$
$$$f_{i+2,j-1}\leftarrow2\times(j-1)\times f_{i,j}$$$

(2) lengthen a paragraph by one or two:

$$$f_{i+1,j}\leftarrow2\times j\times f_{i,j}$$$
$$$f_{i+2,j}\leftarrow2\times j\times f_{i,j}$$$

(3) add a paragraph:

$$$f_{i+1,j+1}\leftarrow(j+1)\times f_{i,j}$$$
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me why this solution for F would TLE? I tjust looks like nlogn with a big constant factor. Shouldn't that still easily pass for n=3e5? Submission

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

    The complexity is $$$O(n^2 log(n))$$$ after selecting each edge it takes $$$O(nlog(n))$$$ time to update the graph, consider a tree where all vertices are connected to the 1st vertex.

»
4 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Thus, one approach is to repeatedly find the city with the most asphalt and merge it with any of its neighbors
What if we pick the city with the current maximum asphalt (and it is $$$< x$$$) but the neighbors don't have enough to make the sum $$$\geq x$$$, i.e. all my neighbors have very little asphalt.

UPD : Misread the editorial. Understood now.

»
3 days ago, # |
  Vote: I like it +16 Vote: I do not like it

I've often requested for more data structure and algorithmic problems, so now that we just had two great problems in I and H, I want to give a big thank you to the organisers of this round :)