### FairyWinx's blog

By FairyWinx, 4 months ago, translation,

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
Реализация

• +81

 » 4 months ago, # | ← Rev. 3 →   +68 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, # |   +1 That was quick! Nice round! Great Problems!
 » 4 months ago, # |   +40 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 →   +14 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 →   -12 .
•  » » 4 months ago, # ^ |   +2 Why all your submission are skipped
•  » » 4 months ago, # ^ |   +8 Yeah After cheating. Your all submissions are skipped . And we all know what that means right ??.
 » 4 months ago, # |   0 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, # ^ |   0 16=16*1 16=8*2 16=4*4These are the possible cases, none of them has both the numbers good on right hand side
•  » » 4 months ago, # ^ |   +8 it can, 16 = 2*8
•  » » » 4 months ago, # ^ |   0 Ah! Got it, Don't know why I was thinking wrong.
 » 4 months ago, # |   0 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 →   +1 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 →   -29 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 →   +49 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, # |   0 I really enjoyed solving todays problems Thank you codeforces :)
 » 4 months ago, # |   +1 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 →   +1 For people who are getting WA on D, this case might be helpful:Input119208 14ExpectedYES
•  » » 4 months ago, # ^ |   0 Thank you!!!
 » 4 months ago, # |   +4 Can anyone explain me the DP tutorial of question D.
 » 4 months ago, # |   0 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, # ^ |   0 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, # |   0 Please fix this
 » 4 months ago, # |   0 Maybe the second part of Problem F is like 1144G - Two Merged Sequences.
 » 4 months ago, # |   0 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  » 4 months ago, # | 0 can problem F be done if the inter-section of the two subsequence need not be the whole array ?  » 4 months ago, # | +2 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 → 0 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, # ^ | +3 Both numbers need to be beautiful. 16 and 32 are not. •  » » » 4 months ago, # ^ | 0 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, # ^ | +3 you can use >=2 beautiful numbers to get x. So [10,10,10] and [20,50] both work. •  » » » » » 4 months ago, # ^ | 0 I get your point.Thanks a lot. •  » » » 4 months ago, # ^ | 0 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, # | 0 Can someone Help me with what is wrong in my solution ?https://codeforces.com/contest/1647/submission/149384795I cannot find a case where this will fail. Thanks in advance. •  » » 4 months ago, # ^ | +1 Failing testcase: Ticket 1931 •  » » » 4 months ago, # ^ | 0 Found my mistake. Was missing one Case. Thanks a lot for the help !!  » 4 months ago, # | 0 Can anyone tell me why I am getting TLE by using unbounded knapsack approach in problem D?My submission •  » » 4 months ago, # ^ | +2 Got my mistake.Anyone looking for dp solution for problem D can check out this — 149391053Finding 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, # ^ | 0 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, # ^ | 0 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, # ^ | 0 •  » » » » » » 4 months ago, # ^ | 0 Thanks for this bottom up approach. Without using this to_id trick, I was getting TLE  » 4 months ago, # | 0 Am I the only one who struggled even with A.  » 4 months ago, # | ← Rev. 2 → 0 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 → 0 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, # | 0 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, # ^ | 0 Because someone has no better)))  » 4 months ago, # | 0 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, # | 0 Why is v <= 700 for the solution by dp in the d problem?  » 4 months ago, # | 0 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 → 0 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 → 0 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