FairyWinx's blog

By FairyWinx, 3 years 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

| Write comment?
»
3 years 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.

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

That was quick! Nice round! Great Problems!

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

»
3 years 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.me/contest/1647/submission/149324001

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

.

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

    Why all your submission are skipped

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

    Yeah After cheating. Your all submissions are skipped . And we all know what that means right ??.

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

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

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

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

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

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

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

Can anyone explain me the DP tutorial of question D.

»
3 years 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!

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

Please fix this

»
3 years 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.
»
3 years 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 ?

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

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

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

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

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

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

»
3 years 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.me/contest/1647/submission/149384795

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

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

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

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

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

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

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

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

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

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

For problem D , I have a different approach of order(T*root(n)) (T is number of testcases.).I took 4 cases.When n=d^1,ans is NO. When n is of form=k*d^2,if divisors of k are greater than 1 then answer is yes else no.When n is of form k*d^m where m>3,Ans is yes if either divisors of k or divisors of d are greater then 2. Last case is n is of form k*d^m.If divisors of k>1,answer is YES.Else if k is prime no.,iterate through divisors of d and check if there exists a divisor such that k*divisor is not equal to d.If it exists then answer is YES else NO. The number of test cases may seem to be many but the coding implementation is simple. Here is a link to my solution : https://codeforces.me/contest/1647/submission/173842574