FieryPhoenix's blog

By FieryPhoenix, 4 years 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
  • +376
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +61 Vote: I do not like it

Thanks for the nice problems!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    LUNCHBOX OTZ

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -47 Vote: I do not like it

      Downvoting because he used OTZ instead of orz, which is clearly superior.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        downdooted for needlessly downvoting people

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        sto c8kbf orz

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        orz does not work as in caps it would be ORZ

        When you are typing in all caps, it is better to use OTZ or OFZ

»
4 years 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.

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

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

    • »
      »
      »
      4 years 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

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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

    • »
      »
      »
      4 years 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.

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

Phoenix and Editorial.

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks for the nice problems!

»
4 years 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.

  • »
    »
    4 years 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

    • »
      »
      »
      4 years 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...

»
4 years 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?

»
4 years 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

  • »
    »
    4 years 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

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

    takes a few minutes

    took 37 minutes to me

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

    Wow man this is just crazy!!

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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!

      • »
        »
        »
        »
        4 years 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.

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

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

  • »
    »
    4 years 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

»
4 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Anybody understand E solution

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years 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

  • »
    »
    4 years 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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks man. I was unable to understand the solution until I read your comment.

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

    see this 114972329

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years 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)?

  • »
    »
    4 years 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.net/blog/entry/90236?#comment-786797

    • »
      »
      »
      4 years 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

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

        No, it fits: 114952738

        Furthermore, I have used only 100 different symbols.

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

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

          • »
            »
            »
            »
            »
            »
            4 years 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.

»
4 years 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.net/contest/1515/submission/114961141

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

Can anyone explain Problem B in detail? please!!

»
4 years 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.net/contest/1515/standings/friends/true

»
4 years 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

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

    Is this a fft solution?

    • »
      »
      »
      4 years 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}}$$$

      • »
        »
        »
        »
        4 years 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

        • »
          »
          »
          »
          »
          4 years 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.

          • »
            »
            »
            »
            »
            »
            4 years 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

            • »
              »
              »
              »
              »
              »
              »
              4 years 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$$$

»
4 years 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 :(

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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)$$$.

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

      Actually,look at this:

      A crazy approach

»
4 years 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.

»
4 years 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.net/contest/1515/submission/114957794

»
4 years 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

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Anybody please explain E in easier way

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

..

  • »
    »
    4 years 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

  • »
    »
    4 years 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))

»
4 years 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.net/contest/1515/submission/114935154

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Thanks for comments in code!

  • »
    »
    4 years 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.

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

Problem solved

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

    Is that an isosceles triangle?

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

    Because the triangles are right isosceles triangles.

»
4 years 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?

  • »
    »
    4 years 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

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

You can also solve A by randomly shuffling the array.

»
4 years 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).

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

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

  • »
    »
    4 years 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$$$.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years 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.net/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.

»
4 years 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

  • »
    »
    4 years ago, # ^ |
    Rev. 3   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]\leq h[2]\leq \dots \leq 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.

    • »
      »
      »
      4 years 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.

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

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

  • »
    »
    4 years 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.

»
4 years 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)

»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

»
4 years 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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

https://codeforces.net/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

  • »
    »
    4 years 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)).

»
4 years 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.

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

    The answer is always "YES", it's explained in the editorial why that is

»
4 years 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.net/contest/1515/submission/114967116

»
4 years 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.

  • »
    »
    4 years 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

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

      Can you please explain your approach for the problem E ?

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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?

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

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

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

      Thank you so much!

»
4 years 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.

  • »
    »
    4 years 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.

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

What a Nice Contest!

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
4 years 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

  • »
    »
    4 years 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

»
4 years 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.

»
4 years 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.

  • »
    »
    4 years 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$$$.

    • »
      »
      »
      4 years 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.

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Nice Round!

»
4 years 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.

»
4 years 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.net/contest/1515/submission/114996358 I have tried taking the two minimum heights and merge them until the remaining elements are exactly m.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can C be done using priority queue?

»
4 years 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?

»
4 years 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.

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

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

  • »
    »
    4 years 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.

  • »
    »
    4 years 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

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

      how did you calculate for 1 2 3 4 case ?

      • »
        »
        »
        »
        4 years 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.

  • »
    »
    4 years 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}$$$.

»
4 years 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

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

    Nice!

  • »
    »
    4 years 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?

    • »
      »
      »
      4 years 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)

»
4 years 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.

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

    I think it is NP-Hard.

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

      How to formally say it though ? Can you explain ?

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

          Isn't Bin Packing different from this question ?

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

            No. It is exactly what starboy_jb described.

            • »
              »
              »
              »
              »
              »
              »
              4 years 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 ?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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.

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

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

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

                  Ahhh yes of course

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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 ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years 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 :(

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

explain C again..its code not able to understand

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the cool problems.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

PROBLEM A solution goes wrong for 3 6 6 6 6

»
4 years 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.net/contest/1515/submission/114950963

  • »
    »
    4 years 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

  • »
    »
    4 years 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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell the solution to problem E in detail?

  • »
    »
    4 years 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)

»
4 years 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.

  • »
    »
    4 years 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.

»
4 years 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}$$$
»
4 years 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

  • »
    »
    4 years 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 years 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.

»
4 years 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 :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How would we have solved 1515C, if the constraint hi <= x was not given... I mean if hi > x was possible.

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

Sorry for commenting on this old blog, but for problem D — Phoenix and Socks, the editorialists solution gives WA for the following test case —

1
4 2 2
5 2 5 4

The actual answer is 1 ( you can change the colour of the second left sock to 4). But the editorial's solution gives 2 as the answer. Am I missing something?

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

    That input is invalid because the colors of the socks may not exceed $$$n=4$$$.

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

      oh ok, I didn't notice that constraint when reading the problem, thanks a lot.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution for F can also be proved in another (slightly retarded) manner. If we just prove that , if at any moment of time, some road is repairable, repairing at that moment of time is never suboptimal, then we arrive to the first solution described in the editorial. (we can prove it by contradiction and some case work on the values of the vertices of considered repairable road)

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone Give a counter test case for this solution of Problem-D

I don't know why is it failing test case 3?