### FieryPhoenix's blog

By FieryPhoenix, 10 days ago,

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

Tutorial
Solution

1515G - Phoenix and Odometers

Tutorial
Solution

1515H - Phoenix and Bits

Tutorial
Solution

1515I - Phoenix and Diamonds

Tutorial
Solution

• +368

 » 8 days ago, # | ← Rev. 2 →   +61 Thanks for the nice problems!
•  » » 8 days ago, # ^ |   +2 LUNCHBOX OTZ
•  » » » 8 days ago, # ^ |   -47 Downvoting because he used OTZ instead of orz, which is clearly superior.
•  » » » » 8 days ago, # ^ |   +29 downdooted for needlessly downvoting people
•  » » » » 8 days ago, # ^ |   +35 sto c8kbf orz
•  » » » » 8 days ago, # ^ |   +26 orz does not work as in caps it would be ORZWhen you are typing in all caps, it is better to use OTZ or OFZ
•  » » » » » 6 days ago, # ^ |   +21 How about OГZ
 » 8 days ago, # |   +91 Hmm Tutorials here pretty fast. I guess those edu rounds require some sort of godly Sacrifice before they release solutions.
•  » » 8 days ago, # ^ |   +3 They have a 12 hour open hacking, so cant release solutions. lol
•  » » » 8 days ago, # ^ |   +11 Even after those 12 hours they make us wait. atleast in prev edu round
•  » » » » 8 days ago, # ^ |   +25 Maybe its bcoz edu round setters have to write lot of problems in a month, so they get late in writing editorial.
•  » » » » » 8 days ago, # ^ |   -6 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
•  » » » 8 days ago, # ^ |   +23 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.
 » 8 days ago, # | ← Rev. 4 →   +128 Phoenix and Editorial.
 » 8 days ago, # |   0 Thanks :')
 » 8 days ago, # |   +2 Thanks for the nice problems!
 » 8 days ago, # |   -12 Am I missing something for B? A 3x3 square can be formed with 14 pieces with one 4 piece and five 2 pieces.
•  » » 8 days ago, # ^ | ← Rev. 2 →   +3 nope they cant be. You can't cut or deform isosceles triangles to fit in square
•  » » » 8 days ago, # ^ |   +7 Ah, I subconsciously assumed 2 * short side of triangle = longer side. This is embarrassing...
•  » » 8 days ago, # ^ |   0 Nope you cant form 3x3 with 14 pieces, either form 3x3 with 2pieces which will require 18 pieces(2) or form 3x3 with 4 pieces which will require 36 pieces(4). Refer to first and second test case explanation for better understanding,also check the side lengths of both of the test cases.
 » 8 days ago, # |   0 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?
•  » » 8 days ago, # ^ | ← Rev. 3 →   0 thats exactly what my fix function is doing in the codehttps://codeforces.com/contest/1515/submission/114942890help yourself as i am still salty for not solving problem 5PS: By worst case i assumed max operations which would occur if no pairs with same color occur in your test case for the above variation
 » 8 days ago, # |   +130 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 :PAccepted
•  » » 8 days ago, # ^ |   -79 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
•  » » 8 days ago, # ^ |   +52 takes a few minutes took 37 minutes to me
•  » » 8 days ago, # ^ |   +14 Wow man this is just crazy!!
•  » » 8 days ago, # ^ | ← Rev. 4 →   +11 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.
•  » » » 8 days ago, # ^ |   +115 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 $yx$,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!
•  » » » » 8 days ago, # ^ |   +3 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.
•  » » 8 days ago, # ^ |   +19 woah, never thought of that. Very smart approach :)
•  » » » 8 days ago, # ^ |   +26 No, it's a stupid insecure method instead
•  » » 8 days ago, # ^ |   +3 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
 » 8 days ago, # |   +39 Anybody understand E solution
 » 8 days ago, # |   0 Could someone explain me 3rd in detail ? I would be thankful.
•  » » 8 days ago, # ^ |   0 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 wrongother wise just print which block went in which towercheers
•  » » » 8 days ago, # ^ |   0 Thanks mate :)
•  » » 8 days ago, # ^ |   0 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
•  » » » 8 days ago, # ^ |   0 Yep, thanks I got the problem statement now :)
•  » » 8 days ago, # ^ |   0 see this 114972329
 » 8 days ago, # |   0 any clues what's wrong in C problem ? 114955920
•  » » 8 days ago, # ^ |   0 Maybe this helps Link
 » 8 days ago, # |   0 Problem I was pretty similar to this one: 1439C - Greedy Shopping
 » 8 days ago, # |   +3 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)?
•  » » 8 days ago, # ^ |   0 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.com/blog/entry/90236?#comment-786797
•  » » » 8 days ago, # ^ |   0 They stored the values starting from $100$ which fits in $64$ kb; storing all the values doesn't fit
•  » » » » 8 days ago, # ^ |   0 No, it fits: 114952738Furthermore, I have used only 100 different symbols.
•  » » » » » 8 days ago, # ^ |   0 which $100$ symbols? are the ones below $32$ allowed?
•  » » » » » » 8 days ago, # ^ |   0 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.
 » 8 days ago, # |   +33 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. •  » » 8 days ago, # ^ | -9 Is your formula inclusion, exclusion. Please explain •  » » » 8 days ago, # ^ | 0  » 8 days ago, # | ← Rev. 2 → 0 Can anyone explain Problem B in detail? please!! •  » » 8 days ago, # ^ | +14 Youve to form a square with given pieces if it's possible then print yes otherwise no •  » » 8 days ago, # ^ | 0 •  » » » 8 days ago, # ^ | 0 Thank you :)  » 8 days ago, # | +8 Even after completion of system testing, it is showing pretest passed in B and a negative in standings. What should I do? https://codeforces.com/contest/1515/standings/friends/true  » 8 days ago, # | ← Rev. 8 → +63 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
•  » » 8 days ago, # ^ |   0 Is this a fft solution?
•  » » » 8 days ago, # ^ | ← Rev. 2 →   0 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}}$
•  » » » » 8 days ago, # ^ | ← Rev. 3 →   0 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
•  » » » » » 7 days ago, # ^ |   0 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.
•  » » » » » » 7 days ago, # ^ |   0 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
•  » » » » » » » 6 days ago, # ^ | ← Rev. 3 →   0 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$
 » 8 days ago, # |   0 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 :(
•  » » 8 days ago, # ^ | ← Rev. 2 →   +85 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.
•  » » » 8 days ago, # ^ |   -18 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)$.
•  » » » 8 days ago, # ^ |   0 Actually,look at this:A crazy approach
 » 8 days ago, # |   +6 Can some explain problem E in an easier way ? Editorial is difficut to understand for me.
 » 8 days ago, # |   -17 Can anyone please tell me the test case where my code is failing. https://codeforces.com/contest/1515/submission/114957794
 » 8 days ago, # | ← Rev. 5 →   +3 Why my submission of C got pretest passed but did not enter the system test phase? submission during the contestAfter the system test I submit the same code and get AC.114960806UPD: solved
 » 8 days ago, # |   +6 Anybody please explain E in easier way
 » 8 days ago, # | ← Rev. 2 →   -11 ..
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 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
•  » » 8 days ago, # ^ |   +3 because your input is incorrect. If will give correct input, it will give correct answer))
 » 8 days ago, # |   +39 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.
•  » » 8 days ago, # ^ |   +1 cool,can you explain your idea .I did thought of cc dp during the contest but couldn't quite get it to work
•  » » 3 days ago, # ^ |   +24 Thanks for sharing! I reuploaded your code with English comments (used autotranslator). Posting here so others may find useful:https://codeforces.com/contest/1515/submission/115660316
 » 8 days ago, # |   +17 Thanks for comments in code!
•  » » 8 days ago, # ^ |   0 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.
»
8 days ago, # |
-31

can anyone help me i don't know why it is showing WA in problem A

# include

using namespace std; int main() { int t; cin>>t; while(t--) { int n,x; cin>>n>>x; int arr[n]; for(int i=0;i<n;i++) cin>>arr[i]; int ans[n]; int fw=0; int indexoffw=0; int f=0; int i=0; do{

fw=arr[i];
if(fw>x)
{ f=1;
indexoffw=i;
break;}

i++;
}while(i<n);

if(!f&&(n!=1))
{
cout<<"YES"<<endl;
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
cout<<endl;
break;
}
if(n==1&&arr[0]==x)
{
cout<<"NO"<<endl;
break;
}
if(f){
ans[0]=arr[indexoffw];
int k=1;
for(int i=0;i<n;i++)
{
if(i!=indexoffw)
ans[k++]=arr[i];
}
cout<<"YES"<<endl;
for(int i=0;i<n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
else
cout<<"NO"<<endl;

}

}

 » 8 days ago, # | ← Rev. 2 →   -22 Problem solved
•  » » 8 days ago, # ^ |   +3 Is that an isosceles triangle?
•  » » » 8 days ago, # ^ |   0 no it's not thank you I understood the idea
•  » » 8 days ago, # ^ |   0 Because the triangles are right isosceles triangles.
•  » » 8 days ago, # ^ |   0 The triangles are isosceles triangles
•  » » 8 days ago, # ^ |   0 I made the same mistake, which is assuming that all types of triangles are allowed. Didn't read the statement properly :/
 » 8 days ago, # |   0 Is pair stored in set in sorted form? If yes then sorted by first or second?
•  » » 8 days ago, # ^ |   0 Yes std::set is always sorted. It compares by first, if it is the same, only then it compares by second
 » 8 days ago, # |   +17 You can also solve A by randomly shuffling the array.
 » 8 days ago, # |   +18 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).
•  » » 8 days ago, # ^ |   0 Ah yes, my code: 114960373, feel free to hack
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 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$.
 » 8 days ago, # |   0 Video Editorial for problem C: https://youtu.be/5S6mjYYkdOA
•  » » 6 days ago, # ^ | ← Rev. 2 →   0 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.com/contest/1515/submission/114944125I 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.
 » 8 days ago, # |   0 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> h(n); vector ans(n); for(int i=0;i>h[i].st, h[i].nd=i; sort(all(h)); for(int i=0;i
•  » » 8 days ago, # ^ | ← Rev. 2 →   +1 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]<=h[2]<=...<=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.
•  » » » 8 days ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 8 days ago, # ^ |   0 Yeah! understood your point, thanks a lot! $\ddot\smile$
•  » » 8 days ago, # ^ |   +1 You can prove it, if take subsequences of two different towers and summarize difference of pair corresponding blocks.
 » 8 days ago, # |   0 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)
•  » » 8 days ago, # ^ | ← Rev. 2 →   +3 All weights are distinct. Check here So, you test case is incorrect.
•  » » » 8 days ago, # ^ |   +1 Oh, really, I'm sorry. Thank you
 » 8 days ago, # |   -15 Video Editorial for Problem D: https://youtu.be/e4U4_W9T7Xk
 » 8 days ago, # | ← Rev. 3 →   -21 I confirm mine is the easiest solve for problem D.Feel free to check it out. P.S. 114917152
 » 8 days ago, # |   0 why did this give tle ??i have used sqrt time only to check sqaure? plz tell........
•  » » 8 days ago, # ^ |   0 Your time complexity became: $10^4*sqrt(10^9) \approx 316227766$ So TLE is obvious.
•  » » » 8 days ago, # ^ |   0 But editorial mentions sqrt approach and many people have ac in sqrt approach only..
•  » » » » 8 days ago, # ^ |   +1 They are using inbuilt sqrt function which takes constant time. What they are really doing is finding the sqrt of that number rounded down(let x), if it was a perfect square then x*x must be equal to n.
•  » » 8 days ago, # ^ |   0 Why don't you use inbuilt sqrt function or binary search for square root?
•  » » » 8 days ago, # ^ |   0 People have got ac with same function as I have written..
•  » » » » 8 days ago, # ^ |   0 Can you link a submission which got accepted with this?
•  » » » » » 8 days ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/contest/1515/submission/114909506 You can look at this one..
•  » » » » » » 8 days ago, # ^ |   0 I think you got TLE because of using '%' operation. Simple boolean operations would pass your solution.
•  » » » » » » » 8 days ago, # ^ | ← Rev. 2 →   0 How does this make a diff at all??I should get ac in this one ..is there any wat to get that now?
•  » » » » » » » » 8 days ago, # ^ |   0 '%' operations are a lot slower. I just changed a line and it got ac 115016226
•  » » » » » » » » » 8 days ago, # ^ | ← Rev. 2 →   +1 i should have got ac in this one..that one line took it away..will use set from next time
•  » » » » » » » » » 8 days ago, # ^ |   0 Bro what do you want? Do you want candle march for you so that you can get justice XD
 » 8 days ago, # |   -11 https://codeforces.com/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
•  » » 8 days ago, # ^ | ← Rev. 2 →   +3 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)).
•  » » » 8 days ago, # ^ |   -9 Editorial has mentioned a sqrtn solution also.. Plz see if
•  » » » 8 days ago, # ^ |   0 People have ac with square root solution also
 » 8 days ago, # |   +1 IN C does it make sense to include "NO" in the question or it was just there to create a confusion.
•  » » 8 days ago, # ^ |   0 The answer is always "YES", it's explained in the editorial why that is
•  » » » 8 days ago, # ^ |   0 thankyou!!
 » 8 days ago, # | ← Rev. 2 →   0 someone please explain why i am getting wrong answer in test 3 in D here's my submission https://codeforces.com/contest/1515/submission/114967116
•  » » 8 days ago, # ^ |   +1
 » 8 days ago, # |   0 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.
•  » » 8 days ago, # ^ |   +12 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
•  » » » 8 days ago, # ^ |   0 Can you please explain your approach for the problem E ?
•  » » » » 8 days ago, # ^ |   +12 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.
•  » » » » » 7 days ago, # ^ |   0 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?
•  » » » » » » 7 days ago, # ^ |   +3 Nevermind I'm stupid the statement meant location-wise, not time-wise
•  » » » 8 days ago, # ^ |   +9 Thank you so much!
 » 8 days ago, # |   0 Can anyone try to hack 114954966. I think it should have given TLE.
•  » » 8 days ago, # ^ | ← Rev. 2 →   +5 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.
 » 8 days ago, # |   +8 What a Nice Contest!
•  » » 8 days ago, # ^ |   -8 Phoenix and Positive Rating
•  » » » 8 days ago, # ^ |   +8 Yes,hah
 » 8 days ago, # |   +19 Question on problem H: How do you split/merge tries?
•  » » 5 days ago, # ^ |   +13
 » 8 days ago, # | ← Rev. 2 →   0 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,10but this gives WA, can anyone suggest a counter example
•  » » 8 days ago, # ^ |   +1 x = 1a = [1, 1, 1, 1, 1, 1]after the first four operations, you'll have [2, 4], and the difference is > 1
•  » » » 8 days ago, # ^ |   0 Thanks man
 » 8 days ago, # | ← Rev. 3 →   -13 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.
 » 8 days ago, # |   0 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.114893372This 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.
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 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$.
•  » » » 8 days ago, # ^ |   0 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.
 » 8 days ago, # |   0 I was wondering why rating changes for global rounds are very fast whereas educational rounds and div 3 rounds take a lot of time?
•  » » 8 days ago, # ^ |   0 It is because of the 12 hour open hacking phase after educational and div 3 rounds. The successful hack tests are added to the main system test cases and then all the solutions are re-judged. So it takes 12 hours to completely judge the solutions and update the ranks
 » 8 days ago, # |   +13 Nice Round!
 » 8 days ago, # |   0 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.
 » 8 days ago, # |   0 Very Nice Contest ! Had interesting problems rather than some wierd and boring problems ! Thanks for the round! Hope to see this type of round even more !
 » 8 days ago, # |   0 Thanks for the nice problems
 » 8 days ago, # |   0 Can anyone please help in figuring out what is wrong with this solution for problem c: https://codeforces.com/contest/1515/submission/114996358 I have tried taking the two minimum heights and merge them until the remaining elements are exactly m.
 » 8 days ago, # |   0 can C be done using priority queue?
•  » » 8 days ago, # ^ |   0 Yes, I have done using priority Queue. Link to my Priority Queue based Submission
•  » » » 7 days ago, # ^ |   0 thanks a lot for the approach
 » 8 days ago, # | ← Rev. 4 →   0 Nice Contest
 » 8 days ago, # |   0 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?
 » 8 days ago, # |   +3 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.
•  » » 8 days ago, # ^ |   +12 For the first two conditions, it is C(3, 2), not 2!.
•  » » 8 days ago, # ^ | ← Rev. 2 →   +4 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.
•  » » 8 days ago, # ^ | ← Rev. 3 →   +3 (1 2 4) all combination = 3! = 6 ways(1 3 4) -------------------- = 6 ways(1 2 3 4) = 8 waysTotal : 20 ways
•  » » » 8 days ago, # ^ | ← Rev. 2 →   0 how did you calculate for 1 2 3 4 case ?
•  » » » » 8 days ago, # ^ |   0 You can understand like this.No of ways to turn on all computers(1,2,3,4) areby turning on 1 computer = 0 waysby turning on 2 computer = 0 waysby turning on 3 computer = 12 ways (as explained in the above comment)by turning on 4 computer = 8 waystotal : 20 ways.
•  » » 8 days ago, # ^ | ← Rev. 2 →   +6 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}$.
•  » » » 8 days ago, # ^ |   0 Yes, $X!$ in the numerator, right ?
•  » » » » 8 days ago, # ^ |   +3 yup!
 » 8 days ago, # | ← Rev. 2 →   +57 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
•  » » 8 days ago, # ^ |   +8 Nice!
•  » » 8 days ago, # ^ |   0 Nice solution. Bud i can't understand the transitiondp[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?
•  » » » 8 days ago, # ^ | ← Rev. 2 →   +1 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)
•  » » » » 8 days ago, # ^ | ← Rev. 27 →   0 oh yeah, i understood, thanks
 » 8 days ago, # |   0 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.
•  » » 8 days ago, # ^ |   +1 I think it is NP-Hard.
•  » » » 8 days ago, # ^ |   0 How to formally say it though ? Can you explain ?
•  » » » » 8 days ago, # ^ |   0
•  » » » » » 8 days ago, # ^ |   0 Isn't Bin Packing different from this question ?
•  » » » » » » 8 days ago, # ^ |   0 No. It is exactly what starboy_jb described.
•  » » » » » » » 8 days ago, # ^ | ← Rev. 2 →   -8 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 ?
•  » » » » » » » » 8 days ago, # ^ |   0 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.
•  » » » » » » » » 8 days ago, # ^ |   +8 No, consider $K=2, x=0$.
•  » » » » » » » » » 8 days ago, # ^ |   0 Ahhh yes of course
•  » » » » » » » » » 8 days ago, # ^ |   0 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 ?
•  » » » » » » » » » 8 days ago, # ^ |   +3 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.
•  » » 8 days ago, # ^ |   0 I think for m = 2, this becomes something of the kind of partition problem that we can solve by DP. Not sure how to do for m > 2. Problem Statement : Given N numbers, partition these into 2 sets(S1, S2) such that the difference between S1 and S2 is minimised. If this difference <= x, then it is possible else not possible,
 » 8 days ago, # |   0 https://codeforces.com/contest/1515/submission/114949655 can anyone help me to figure out why is this logic wrong?
 » 8 days ago, # |   +3 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 :(
 » 8 days ago, # |   0 explain C again..its code not able to understand
 » 8 days ago, # | ← Rev. 2 →   -14 Great contest! Missed first 2 ques by some silly mistakes and got demotivated to try more :(
 » 8 days ago, # |   +3 Thanks for the cool problems.
 » 8 days ago, # |   0 PROBLEM A solution goes wrong for 3 6 6 6 6
•  » » 8 days ago, # ^ |   +3 All weights are distinct.
 » 8 days ago, # |   0 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?
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 Consider this case :1 6 2 2 2 2 2 2 2 2
•  » » » 8 days ago, # ^ |   0 Got it. Thanks.
•  » » 8 days ago, # ^ |   0 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.
•  » » » 8 days ago, # ^ |   0 Thanks.
 » 8 days ago, # |   0 Can someone tell the solution to problem E in detail?
•  » » 7 days ago, # ^ | ← Rev. 2 →   +7 I think you want to understand this transitiondp[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)
•  » » » 6 days ago, # ^ |   0 Thanks
 » 8 days ago, # | ← Rev. 2 →   0 IN Q Phoenix and Gold ...if we put test case 1... 8 56.... 34 22 22 34 34 34 34 34 Answer is wrong as it gives ... YES..... 34 22 22 34 34 34 34 34 hece weight will explode.
 » 8 days ago, # |   0 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.
•  » » 8 days ago, # ^ |   0 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.
 » 8 days ago, # |   0 Can anyone briefly explain why there will always a solution exist in Problem C?? Why will we never get a max difference greater than x if we always merge with the smallest height deck?
•  » » 8 days ago, # ^ |   0 "A single block never exceeds the height of x".
•  » » » 8 days ago, # ^ |   0 "A single block never exceeds the height of x". that is true but how does it imply that the max difference between two decks will also not exceed x. Why this soln is not working?? Collect all the N towers in the set, merge the two smallest heights till the size of set is greater than m.
•  » » » » 8 days ago, # ^ |   0 If a single block cannot exceed the height of x, the only way the difference between two blocks can be greater than x is if you add a block to a taller tower. If we always add a block to the shortest tower, the height of that tower increases by only the height of the added block, which is less than x. Sorry I do not understand your approach.
 » 8 days ago, # |   0 How would one approach C if a single block could exceed the height of x? Would the same greedy strategy work? I am having a hard time with the proofs.
•  » » 8 days ago, # ^ |   0 Nope it would not and it's NP Hard. See the above comments from here : https://codeforces.com/blog/entry/90236?#comment-787072
 » 7 days ago, # | ← Rev. 2 →   0 Can anyone please tell me what's wrong in my code for problem D? https://codeforces.com/contest/1515/submission/115072254
•  » » 7 days ago, # ^ |   0 Nevermind, I found the mistake. This is my AC: https://codeforces.com/contest/1515/submission/115072573
 » 7 days ago, # |   0 Can someone please explain D, editorial is too messy and so many variable is used in them.I can't able to figure it out as a whole. Thanks in advance
 » 7 days ago, # |   0 Hi, can anyone please help me in understanding where am I going wrong in my code for problem F. I am getting WA on test 16 saying wrong output format Unexpected end of file — int32 expected.Here is the link to MY CODE
 » 6 days ago, # |   0 I know it may be too late but in 1515C time complexity for each test case can be precise to $O(n \log{m})$. That's because a set or a heap are built from $m$ pairs.
 » 6 days ago, # |   0 I understood the first part of the editorial for problem E but I am not able to understand how the segments are merged using binomial coefficients, can somebody explain it to me.
 » 6 days ago, # |   +13 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}$
•  » » 2 days ago, # ^ |   0 Can you plz elaborate more, I didn't even get what is paragraph.
•  » » » 27 hours ago, # ^ |   0 a series of consecutive opened computers
 » 6 days ago, # |   0 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
•  » » 6 days ago, # ^ |   +5 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.
•  » » » 6 days ago, # ^ |   0 Yea thanks, I just realised this
 » 4 days ago, # | ← Rev. 3 →   0 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.
 » 3 days ago, # |   +16 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 :)