### FairyWinx's blog

By FairyWinx, 11 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
Реализация Tutorial of Codeforces Round #777 (Div. 2) Comments (55)
 » 11 months ago, # | ← Rev. 3 →   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.
 » That was quick! Nice round! Great Problems!
 » 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
 » 11 months ago, # | ← Rev. 2 →   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
 » 11 months ago, # | ← Rev. 2 →   .
•  » » Why all your submission are skipped
•  » » Yeah After cheating. Your all submissions are skipped . And we all know what that means right ??.
 » 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?
•  » » 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
•  » » it can, 16 = 2*8
•  » » » Ah! Got it, Don't know why I was thinking wrong.
 » 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?
•  » » 11 months ago, # ^ | ← Rev. 4 →   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.
 » 11 months ago, # | ← Rev. 2 →   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 :/
 » 11 months ago, # | ← Rev. 2 →   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.
 » I really enjoyed solving todays problems Thank you codeforces :)
 » 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.
•  » » Here is my AC solution using DFS — Submission
 » 11 months ago, # | ← Rev. 2 →   For people who are getting WA on D, this case might be helpful:Input119208 14ExpectedYES
•  » » Thank you!!!
 » Can anyone explain me the DP tutorial of question D.
 » 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!
•  » » 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
 » 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  » can problem F be done if the inter-section of the two subsequence need not be the whole array ?  » 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.  » 11 months ago, # | ← Rev. 3 → 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. •  » » Both numbers need to be beautiful. 16 and 32 are not. •  » » » 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)) •  » » » » you can use >=2 beautiful numbers to get x. So [10,10,10] and [20,50] both work. •  » » » » » I get your point.Thanks a lot. •  » » » 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  » 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. •  » » Failing testcase: Ticket 1931 •  » » » Found my mistake. Was missing one Case. Thanks a lot for the help !!  » Can anyone tell me why I am getting TLE by using unbounded knapsack approach in problem D?My submission •  » » 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. •  » » » 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}$. •  » » » » 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 ? •  » » » » » •  » » » » » » Thanks for this bottom up approach. Without using this to_id trick, I was getting TLE  » Am I the only one who struggled even with A.  » 11 months ago, # | ← Rev. 2 → 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?  » 11 months ago, # | ← Rev. 2 → 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.  » 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. :( •  » » Because someone has no better)))  » 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  » Why is v <= 700 for the solution by dp in the d problem?  » 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").  » 10 months ago, # | ← Rev. 2 → 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.  » 9 months ago, # | ← Rev. 2 → 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 = 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 += dp$($36 / 2 = 18$). choosing$6$we transition to$dp += dp$($36 / 6 = 6$). Note that transitions such as$dp += dp$, 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, dp$. 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[b]$, and the sum of$dp[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