FairyWinx's blog

By FairyWinx, 4 months ago, translation, In English

Task A. Idea FairyWinx

Hint 1
Hint 2
Solution
Code

Задача B. Idea FairyWinx

Hint 1
Hint 2
Solution
Code

Задача C. Idea FairyWinx

Hint 1
Hint 1
Hint 2
Solution
Code

Задача D. Idea FairyWinx

An important fact
Hint 1.1
Hint 1.2
Hint 1.3
Solution 1
Code
Hint 2.1
Solution 2 (which almost everyone wrote)
Реализация

Задача E. Idea FairyWinx

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Реализация

Задача F. Idea Igorbunov

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Реализация
 
 
 
 
  • Vote: I like it
  • +81
  • Vote: I do not like it

»
4 months ago, # |
Rev. 3   Vote: I like it +68 Vote: I do not like it

Second case in F can be done greedy as well and only slightly less straightforward. We should be looking at two next elements instead of one and if $$$a_{i+1}>a_{i+2}$$$ then we should always add $$$a_{i+1}$$$ to a decreasing subsequence if possible, and vice versa.

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

That was quick! Nice round! Great Problems!

»
4 months ago, # |
  Vote: I like it +40 Vote: I do not like it

Problem C, hint 1:

There is always an answer when the upper right cell is painted white.

I think you meant the upper left cell

»
4 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

I solved D in a pretty clumsy way without managing to come up with any of the nice math. I'm not sure if it's correct. Can somebody try to explain why it works or if it's wrong?

First you factorize x, then remove the non-multiples of d. These are all the good numbers that are candidates for multiplying to x. Let's let N be the length of these remaining good numbers. N ~ O(sqrt(x))

Now, we want to determine which ones of these are beautiful. After running some examples in my head, it seemed like for each good number g, we can just check to see if g/d is also good. If g/d is good, then g is not beautiful. Otherwise, g is beautiful. We can do this in O(N) or O(N log N) with hashing/sorting.

Now we have our remaining beautiful numbers. We just need to find 2 different ways to multiply to x. I tried locally with some huge numbers and the length of the remaining beautiful numbers is very small (around 15-20 for x=1e9). So i just did backtracking dfs over the numbers and divided until i got to 1.

This passed in a pretty reasonable amount of time. Please let me know if it's wrong.

Here is submission: https://codeforces.com/contest/1647/submission/149324001

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

.

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

In problem D, according to definition, if d=2 then 16 can be a beautiful number because 16 is a good number (multiple of 2) and 16 cannot be represented a product of two good numbers but according to tutorial beautiful number is not divisible by d*d. Where I am wrong?

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

Problem D, can someone prove or explain in more details why we can't factor in two ways if d = p^2 and x = p^7?

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

    If we try to represent $$$x$$$ as the product of three numbers, we end up with the set $$$\{p^2,p^2,p^3\}$$$. If we try to move the extra $$$p$$$ factor, the resulting set is the same.

    If we try to represent as $$$x$$$ as the product of two numbers, we end up with the set $$$\{p^3,p^4\}$$$, however $$$p^4 = (p^2)^2$$$, which is not allowed.

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

I like editorials with hints, But WTF dude :| Hint 2.1 of problem D says : Consider the case -_- Ok bro this helped me a lot I solved the whole problem with this hint. Well sometimes it's better to do not put such hints :/

»
4 months ago, # |
Rev. 2   Vote: I like it +49 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

I really enjoyed solving todays problems Thank you codeforces :)

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For problem B we can say that the answer is YES if all components of black squares are rectangles. And then we can solve the problem by the hard way and do dfs.

»
4 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

For people who are getting WA on D, this case might be helpful:

Input

1

19208 14

Expected

YES

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

Can anyone explain me the DP tutorial of question D.

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

Haha. I like the editorial solution of B. I myself spent a lot of time implementing B because I was dumb enough to do the straightforward method of checking if each connected component of 1s formed a rectangle.

Thank you for the quick editorial as well!

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

    I agree, the solution is great, I also did it in BFS, that was a tone of code and so many times of debugging LOL

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

Please fix this

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

Maybe the second part of Problem F is like 1144G - Two Merged Sequences.

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

In $$$D$$$, a simple way to think about the case where $$$d=p^k$$$, $$$x=d^a\cdot b$$$, and $$$b=p^e\cdot f$$$, such that $$$p$$$ is prime, $$$k\geq 1$$$, $$$a\geq2$$$, $$$0\leq e<k$$$, and $$$f$$$ is not a multiple of $$$p$$$:

The maximum-length valid factorization has $$$a$$$ factors, which can be {$$$d$$$, $$$d$$$, ..., $$$d\cdot b$$$}, let's see if we can obtain a different valid factorization as well:

  • If $$$b$$$ is composite ($$$b=x\cdot y$$$, where $$$min(x, y)\geq 2$$$): A different valid factorization with also $$$a$$$ factors is {$$$d$$$, $$$d$$$, ..., $$$d\cdot x$$$, $$$d\cdot y$$$}.
  • Otherwise, since putting $$$b$$$ anywhere within the maximum-length valid factorization will give the same unordered set of factors, a different valid factorization can be obtained only if $$$a\geq 3$$$ and $$$(a-1)\cdot (2k-1)\geq (a\cdot k+e)$$$, which means we can decrease the number of factors from $$$a$$$ to $$$a-1$$$ and obtain a valid factorization.
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can problem F be done if the inter-section of the two subsequence need not be the whole array ?

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

How should one approach problems such as yesterday's D?
A copious amount of casework was required and it is very easy to either overlook or mess up one or more cases.

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

I can not understand Problem D. Madoka and the Best School in Russia.
How is the test case x=128 and d=4 giving the output 'NO'?
If we factorize 128 then some of the valid results are 8*16 and 32*4. Here all of them are good and 8(first case),4(second case) are both beautiful. I know I am missing something but I can not figure it out.

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

    Both numbers need to be beautiful. 16 and 32 are not.

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

      then what about the final test case "1000 10".How can it can output "YES" since all its beatiful factors are [10,20,40,50,250]?--->(it seems like there are only one set to get 1000(20,50))

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

        you can use >=2 beautiful numbers to get x. So [10,10,10] and [20,50] both work.

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

          I get your point.Thanks a lot.

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

      ok. I get it. I was confused about this sample test and the sample test 16384 4. So this can be factorized as 4*4*4*4*4*4*4 and 8*8*4*4*4*4. Yeah I understand now. I was thinking that the factorization will consist only 2 numbers. Thanks

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

Can someone Help me with what is wrong in my solution ?

https://codeforces.com/contest/1647/submission/149384795

I cannot find a case where this will fail. Thanks in advance.

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

Can anyone tell me why I am getting TLE by using unbounded knapsack approach in problem D?

My submission

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

    Got my mistake.

    Anyone looking for dp solution for problem D can check out this — 149391053

    Finding beautiful divisors — Let two good numbers be k1*d,k2*d. A number is beautiful iff it cannot be represented as product of two good numbers. This means that beautiful number != k1*k2*d^2. So, a beautiful number cannot be divisible by d^2. Check all divisors of x, if they satisfy x%d == 0 and x%(d^2) != 0 then divisor is beautiful.

    Let dp[ i ][ j ] represent no of ways to form product j considering first i beautiful divisors. I used top down unbounded knapsack like approach since we can use any amount of good numbers to reach x. (similar to infinite supply of coins)

    dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i-1 ][j / beautiful [ i ] ];

    Using relevant base cases and conditions, required ans = dp[n-1][x]. Since x is uptil 1e9 using conventional 2d array will result in MLE. So I used a map and replaced this memoization condition by map.find({i,j}) != map.end().

    I tried a bottom up approach also but got a TLE and almost MLE — 149387702. If anyone has done bottom up please share submission link.

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

      There is a nice a trick to replace the map $$$dp$$$ with a $$$2d$$$ array.

      We know that the values that can appear in the second dimension are divisors of $$$x$$$. So, we can have an array $$$to\_id$$$ to map each divisor to an $$$ID$$$, obtain that $$$ID$$$ later in $$$O(1)$$$, and use it as an index in the $$$dp$$$ array's second dimension.

      Since for each divisor $$$d$$$ either $$$d\le \sqrt{x}$$$ or $$$\dfrac{x}{d}\le \sqrt{x}$$$, if $$$d\le \sqrt{x}$$$, we can store $$$ID$$$ of $$$d$$$ directly in $$$to\_id[d]$$$, otherwise, we can store the $$$ID$$$ in $$$to\_id[\dfrac{x}{d}+\sqrt{x}]$$$. So, size of $$$to\_id$$$ is at most $$$~2\cdot \sqrt{x}$$$.

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

        Thanks for this trick.Can You please show the implementation of this trick ?

        Since my second state of dp is product / beautiful[ i ], how to use to_id map here ?

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

Am I the only one who struggled even with A.

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

in problem D we have to find a number at worst one beautiful and rest are good, which satisfies the question conditions (in at least two different ways as a product of several (possibly, one) beautiful numbers.), however in the below example 128 4 128 = 4*32 128 = 8 *16, here 4, 8, 32,16 all numbers are good but only 4 and 8 are beautiful numbers because they are not product of two good number i.e 4 = 4*1, or 2*2 (2 and 1 are not good) also 8 = 8*1,4*2,2*2*2(1,2 are not good), and count of pair = 2 , so answer should be YES but given as NO Can anyone tell me what I am missing here?

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

Code. I have given the link to my code, Can someone say why I'm getting TLE. I did the exact same thing what they have given in the tutorial. How much ever i modify i'm always getting TLE until and unless i copy paste the tutorial code. Can someone explain to me why is my code giving TLE??...Also during contest i did some slight modification in my previous code, it got accepted during that time but after system checking it says TLE in 3rd test case.

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

Maybe my English level is low,but what is the meaning of "expand the array" in the editorial of problem F?

In other words,why isn't it called "reverse the array" ?

Sorry to bother you to think about it. :(

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

It seems that first and third case in F can be done without dp. Take the first case as example, we can take out all prefix maximal element, then the dp value is the maximul in the rest. 149532612

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

Why is v <= 700 for the solution by dp in the d problem?

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

I think there is a problem with the language in the explanation of problem D solution 2. In the explanation, checking that "a<=2" happens after we check that "d is composite and not a power of prime" (2nd to last paragraph). However, this means that we do not check whether a<=2 for the case "d is the power of a prime" (last paragraph). This means an implementation following this description fails on x=32 d=2 (outputs "YES" when the answer is "NO").

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

In problem D, why we need dp[{z.first.first / i, i}] = min(dp[{z.first.first / i, i}] + z.second, 2). I tried dp[{z.first.first / i, i}] = dp[{z.first.first / i, i}] is also Accepted.

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

I found the explanation of Solution 1 of Problem D in editorial difficult to read, so I will write down my understanding.

The explanation of $$$dp[n][b]$$$ is as follows.

  • $$$dp[n][b]$$$ is the number of ways to decompose $$$x$$$ into a product of beautiful numbers.
  • $$$n$$$ has not yet been decomposed, and $$$x / n$$$ has already been decomposed.
  • $$$b$$$ is a beautiful number (and divisor of $$$x$$$).
  • $$$b$$$ is used in all products $$$x / n$$$.
  • $$$b$$$ is the largest in all products $$$x / n$$$.

Take the case $$$(x, d) = (36, 2)$$$ for example. Since there are two ways $$$(2 * 18), (6 * 6)$$$, the answer to this case is "YES".

Since we want to represent $$$x = 36$$$ as a product of several beautiful numbers, let's find all beautiful numbers that is divisor of $$$x = 36$$$. In this case $$$(2, 6, 18)$$$.

Initialize with $$$dp[36][1] = 1$$$. In $$$dp[n][b]$$$ we always need to use one of $$$(2, 6, 18)$$$ to decompose $$$n$$$ once.

  • choosing $$$2$$$ we transition to $$$dp[18][2] += dp[36][1]$$$ ($$$36 / 2 = 18$$$).
  • choosing $$$6$$$ we transition to $$$dp[6][6] += dp[36][1]$$$ ($$$36 / 6 = 6$$$).

Note that transitions such as $$$dp[3][2] += dp[6][6]$$$, where the destination $$$b$$$ value is smaller, are prohibited by the definition of $$$dp$$$ (otherwise it would be overcounting).

As a result, we find two states in which $$$x = 36$$$ is completely decomposed: $$$dp[1][18], dp[1][6]$$$. And we see that they correspond to $$$(2 * 18), (6 * 6)$$$ (as mentioned above).

In other words, the state in which $$$x = 36$$$ is completely decomposed is denoted by $$$dp[1][b]$$$, and the sum of $$$dp[1][b]$$$ is the value we want. We can solve this problem by checking if this sum is greater than or equal to $$$2$$$.

Here is my C++ code (modified to make the editorial code more readable).
157492577