### Morphy's blog

By Morphy, history, 6 years ago,

SnackDown 2018 elimination round starts in ~8 minutes. Top 300 get T-shirts

Let's discuss the problems after the contest!

• +69

| Write comment?
 » 6 years ago, # |   +8 Is it possible to move SRM?
 » 6 years ago, # |   +8 How to solve ADIMAT, XORTABLE and EBAIT?
•  » » 6 years ago, # ^ |   +23
•  » » » 6 years ago, # ^ |   0 And how to use it?
•  » » » » 6 years ago, # ^ |   +13 I think it doesn't help much. Just use "Burnside's lemma" and min(n, m) ≤ 23 to enumerate all cases in one dimension then do DP in other.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +11 for XORTABLE, we find connected components for each vertex and if we know value of this vertex then we can find all value for the component.For each vertex, we can break down segment [L, R] to multiple segments and try endpoints of theses segment to find the one that fit.
•  » » » 6 years ago, # ^ |   0 How are you breaking down the segments exactly?
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 suppose you have L < prefix*** < R you can use segment [prefix000, prefix111] to find union with adj vertexes. Those prefixes can be found by prefix of L or R with at most 1 different bit.
 » 6 years ago, # |   +16 Any ideas what we may have missed in EBAIT? We even wrote stress test...
•  » » 6 years ago, # ^ |   0 If you used the Stern-Brocot Tree, there are cases in which the Tree may be very deep, as well as cases in which it is not optimal to take the LCA in the Stern-Brocot Tree.
•  » » » 6 years ago, # ^ |   +8 I take care of tree being deep. idk about lca, I go down through Farey sequence
 » 6 years ago, # |   -41 How to solve all the questions? Is this what happens when you are out of touch for months or were the contest problems really difficult?
 » 6 years ago, # |   +69 rep(i,0,n) { if (i%2==0) cx+=v[i]; else cy+=v[i]; if (i==n-1) continue; // if (i==n-1) --cy; if (cy*mx>=my*cx) { mx=cx; my=cy; } // if (i==n-1) ++cy; } That's a part of 1st place team's AC submission to problem "Election Bait". As far as I understand, phrase "For each bus except the last bus from the last convoy, after the people from this bus cast their votes, party A must have strictly more votes than party B." means exactly what is written in commented lines. Can someone explain this?
•  » » 6 years ago, # ^ |   +2 Sigh. Rereading my questions about its original statement and the clarifications I received, I noticed that clarification was also unclear and could have been interpreted in either commented or uncommented way. I should have caught that.
•  » » 6 years ago, # ^ |   0 Turns out that description was overly specific, but in the exact wrong way..
•  » » » 6 years ago, # ^ |   +2 Not overly. It needed to be specified. (And in one of many wrong ways.)
 » 6 years ago, # | ← Rev. 2 →   +65 Looks like the data (or statement) for EBAIT is incorrect. In the statement it says for all bus except the last one in last convoy, A has more votes than B; however most solutions understand it as for all buses not in the last convoy, A has more votes than B. We stuck on this problem for more than 3 hrs.
•  » » 6 years ago, # ^ |   +57 Same here, I stuck on this problem for 2 hours...
•  » » 6 years ago, # ^ |   +90 Yes, accepted solutions output 1 1 for the following test case: 1 2 1 1 1 2 Spent two hours due to this as well... luckily it was our only remaining problem during the last hour, but for other teams it might have been crucial.
 » 6 years ago, # |   +59 Also I guess it's Radewoosh's time to joke about "notorious coincidence".
•  » » 6 years ago, # ^ |   +13 XD
 » 6 years ago, # |   +27 SFXPAL may be solved in linear time using . Did anyone use it? Can anyone prove it? :)
•  » » 6 years ago, # ^ |   +5 My team used it.
•  » » 6 years ago, # ^ |   +3 Our solution, also linear: https://www.codechef.com/viewsolution/21809749https://oeis.org/A252700
•  » » 6 years ago, # ^ |   +50 How to solve it in ?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 You can use inclusion-exclusion with dp[i] = ways that last [i, n] is that first suffix is a palindrome
•  » » 6 years ago, # ^ |   0 Does someone have a really rigorous proof of the above statement?
•  » » » 6 years ago, # ^ | ← Rev. 4 →   +8 Call a string bad if it has a palindromic suffix of length  > 1 and call an the number of bad strings of length n. Now we can take a bad string of length n - 1 and put a character in front of it: gives us san - 1 bad strings of length n. We can also make the whole string a palindrome: s⌈ n / 2⌉ strings. However, the bad palindromes that have a smaller palindromic suffix were already counted in 1. So we subtract a⌈ n / 2⌉ such palindromes. So an = san - 1 + s⌈ n / 2⌉ - a⌈ n / 2⌉ (the operation is ceiling if it ain't clear).
•  » » » » 6 years ago, # ^ |   +41 Why is the number of palindromes in 3. a⌈ n  /  2⌉?In 3. we're counting the number of palindromes of length n which have a palindromic suffix of length  ≤ n - 1.a⌈ n  /  2⌉ is the number of palindromes with a palindromic suffix of length  ≤ ⌈ n / 2⌉, so we also need to prove that if a palindrome has a palindromic suffix, then it has a palindromic suffix of length  ≤ ⌈ n / 2⌉ (*).If that's left out as obvious, then we don't need bad strings: Take a good string of length n - 1, put one character in front: Subtract palindromes that are created by taking a good string of length ⌈ n / 2⌉ and turning it into a palindrome of length n: All strings in 2. were counted in 1 because of (*) I think adamant and Vijaykrishna were asking for a proof of (*). It's not hard: if is a palindrome and has a palindromic suffix of length k where k > ⌈ n / 2⌉ then for i ≤ 2k - n and the suffix of length 2k - n is also a palindrome and shorter
•  » » » » » 6 years ago, # ^ |   0 Yes, I figured this proof out later by myself, but thank you anyways for the elaborate explanation.
•  » » 6 years ago, # ^ |   +10 I just made a brute force, searched for the solutions on oeis and found this:http://oeis.org/search?q=Number+of+strings+of+length+n+over+a&sort=&language=english&go=Search
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 The straightforward dp isI guess yours dp can be simply proven using dp above.
 » 6 years ago, # |   +136 This is directed towards Codechef organizers: I am going to explain why team azneyes (with ksun48) and moofest (with me) have basically the same code on ADIMAT.We were both on MIT ACM last year, and did GP of Poland. We both recognized that the problem was the same as there, so we both copy and pasted our AC code from there. That's why the code is the same.
•  » » 6 years ago, # ^ |   0 Can you give link of this GP of Poland's question ?
•  » » » 6 years ago, # ^ |   +15
•  » » » » 6 years ago, # ^ |   +1 Is there any judge where we can submit solutions to the problems of this GP of Poland ?
•  » » » » » 6 years ago, # ^ |   +5 Here is the opencup contest, no idea if the problems are uploaded somewhere else.
 » 6 years ago, # |   +16 Problems from OEIS, from e-maxx, from recent contest — well done Codechef, it was one of the worst contests ever.Is the Codechef coordinator green or cyan?
•  » » 6 years ago, # ^ |   +99 Worst contest ever? I agree that repeated problem from opencup sucks and wrong testdata in Elections sucks even more, but many problems were quite original and interesting. I surely enjoyed this contest (maybe my impression would be different if I would have been solving elections not as my last problem)
•  » » 6 years ago, # ^ |   +9 Opencup isn't really "open" so not many people have access to the contests, how would they know that it is repeated?
•  » » » 6 years ago, # ^ |   +11 I agree, problem from Opencup was a notorious coincidence, but still, there are two OEIS problems and one problem from e-maxx, and T-shirts were decided on them.
•  » » » » 6 years ago, # ^ |   +10 Yeah I agree with others. BTW, which problem is from e-maxx?
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +18 A problem about tree.There is no exact code, but it is explained how this problem is solved. So this problem is just "write standard algorithm, without any changes".
•  » » 6 years ago, # ^ |   +23 Was there an OEIS problem? I solved all, but couldn't find it.
•  » » » 6 years ago, # ^ |   +20 People in Discord say that palindromes and binary matrix can be found on OEIS.
•  » » » » 6 years ago, # ^ |   -39 Tbh, during my competitive career I have found some sequences on OEIS, but never managed to get a solution from there. Usually there are just 30 first elements with no useful info on how to compute it in the fastest way, but a lots of useless info about shitty generating functions or whatever.
 » 6 years ago, # |   +37 So is something going to be done with Election Bait? In a situation when the statement is inconsitent with the test data, accepting all solutions that solve the problem correctly in at least one of the sensible settings seems like a fair thing to do.
•  » » 6 years ago, # ^ | ← Rev. 2 →   -53 Accepting all solutions that solve the problem according to the in-contest version of the problem statement (and changing either the statement or test data, whichever is more practical) seems like the best course of action, yes.UPD: Should I take downvotes to mean nothing should be done? ( ͡° ͜ʖ ͡°)
•  » » » 6 years ago, # ^ |   +24 Sorry, but this looks like wrong understanding. The way proposed by Endagorion was to accept solutions to both versions of the problem, not to pick one of them. So that the accepted solutions stay accepted, but additionally, the currently rejected solutions get rejudged with jury answers being answers to the other version of the problem. It requires some work on the organizers' side.
•  » » » » 6 years ago, # ^ |   -18 The misunderstanding is on your part. I said accepting all solutions that X, not "and rejecting all solutions that not X".There will be a rejudge accepting both versions.
•  » » » » » 6 years ago, # ^ |   0 Sorry again, I just don't see how changing the statement helps rejudging with the other statement.But anyway, looks like there's really no misunderstanding on your part, alright then :) .
•  » » » » » » 6 years ago, # ^ |   -15 Changing the statement is just for the future. Problems are available for practice after all.
•  » » » » » 6 years ago, # ^ |   +13 Thanks! When can we expect the rejudge to be done?
•  » » » 6 years ago, # ^ |   0 It gets even worse because some of the translations may be entirely different kinds of wrong. For instance, the Russian statement misses any kind of formal explanation of the process (it just basically says "the party A should be winning until the very last moment", sic).
•  » » » » 6 years ago, # ^ |   +20 It shows that there should be no translations for important international rounds, unless organizers can really ensure the quality.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -44 Translations are sometimes made using early versions of statements (before I completely rewrite them). Long Challenge started yesterday, so I had 22 problems to work on and only edited EBAIT today. Still, translations are there just for convenience and if someone gets something wrong because of not reading the main problem statement, that's just too bad.
•  » » » » » 6 years ago, # ^ |   +3 In the preelimination contest earlier this year there was a bug in russian statement. The numeration of sides of the triangle is clearly differenthttps://www.codechef.com/SNCKPE19/problems/ANGLEI prefer not to read translated statements since then :)
•  » » » » » 6 years ago, # ^ |   +57 What's the point of making them if you have to read english statement anyway?
•  » » » » » » 6 years ago, # ^ |   +4 Agree. These creepy translations should be deleted. Some things are just too bad to exist.
•  » » » » » » 6 years ago, # ^ |   -47 You have to read the English statement if you want to be 100% sure what's going on. It might be simpler for people to speedread statements in their native languages. But idk, I don't decide that.
•  » » » » » » » 6 years ago, # ^ |   +2 Since you brought up the long contest, in this month's challenge problem, the English statement does not explain how the input is generated but the Russian and Hindi translations do.It seems that to be 100% sure you understand a CodeChef problem, you have to read the English statement and the translations.
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 4 →   -27 The input in the challenge problem is generated in a secret way. Thanks for telling me, it should be removed from the translations — it can lead you to optimising your program's performance on wrong test data without realising it. (Go ahead and give me an implementation of connect().)
•  » » » » » » » » » 6 years ago, # ^ |   +16 That's interesting, I heard the contest admin said the exact opposite: that the pseudocode will be added to the English statement as well, and to look at the translations in the meanwhile.Glad this came up now when there's still plenty of time left in the contest to clarify things.
•  » » » » » » » » » 6 years ago, # ^ |   +8 Of course, when I say something will be done, that's just what I think will/should be done. The translations are updated now.If you think about this generator description, there isn't any area where it clearly tells you something. It doesn't let you reproduce tests with an identical distribution, since connect() is secret. It doesn't exclude any types of tests because the baseline is a random DAG and connect() is secret. OTOH, how tests are formed clearly affects the solution somehow (or it wouldn't be secret), which is something people might miss. It's better to avoid saying something misleading about test data.The main problem with keeping translations accurate, especially when a small correction is made in a statement, is resources: time and people. Think about it, who will check the translations? Are translators supposed to monitor everything and triple-check for differences? I don't know any TL languages except Russian, so that's out. Problemsets are made late since there aren't enough setters, which means testing is often rushed, things change shortly before the contest, and sometimes something gets missed. Translations are the last part of the expected process "initial statement -> changes during testing -> final statement -> translations", and of course, when you parallelise, it's much easier to miss something. Plus consider that people who do everything have their own lives, for example I have a full-time job and usually fix statements in evenings when I have free time. If I'm on a trip somewhere with no net, you might get crap statements; this ties up to the "not enough time" problem.In the end, the situation can't improve unless more good problems are proposed — that would push the whole workflow ahead. There are small improvements like more people checking everything, or not so many shitty non-statements where I have to divine what the setter wanted to write, but they don't affect so much.
•  » » » » » 6 years ago, # ^ |   +127 translations are there just for convenience In most serious competitions I've seen translations are treated as formal documents with equal power as official statements. If that is not the case, there probably should be a notice of that (e.g. "there's no guarantee our translations have anything to do with actual problems, idk lol").
•  » » » » 6 years ago, # ^ |   +56 In Chinese statement for SFXPAL we're told to modulo the answer with 1e9+7 instead of M. Luckily I guess most participants have noticed the extra number M in the input.
 » 6 years ago, # |   +8 Problems were very interesting, enjoyed it quite a bit, even thought they were very difficult for me. If someone could elaborate on Adi and the Matrix it could be nice ^^
•  » » 6 years ago, # ^ | ← Rev. 6 →   +82 You have to use burnside lemma. THe group acting on the set of all binary matrices is (P, Q), where P and Q are permutations of length m and n respectively. Say the cycle lengths in the permutations are (l1, l2, ..., lk) and (L1, L2, ... Lr) respectively.Now we have to find the number of binary matrices unaffected by the pair (P, Q). We will choose some Xa, b and rest will be set through equality conditions. For example, say we choose some index a from a cycle of length li and index b from cycle of length Lj. Then setting Xa, b will set values. So overall, we have to set values to set all values for indices from the cartesian product of two cycles. Hence there are binary matrices fixed by the permutation pair. Now, assume n < m and for each partition of n, do a dp on the other dimension. The overall complexity is O(m2p(n)) or O( where N is the constraint on nm and p(n) is the partition function. Link to solution
 » 6 years ago, # |   +5 How to solve ADITREE ?
•  » » 6 years ago, # ^ |   +18 Choose any root. Observation: We have to take an edge from v to its parent p in our optimal connection iff the number of light-on houses in subtree rooted at v is odd.So you can keep in val[v] parity of light-on houses under v. When you switch light in v you have to do val[w] ^= 1 for each vertex on the path from v to root. The answer to the query is sum of val[v] for all vertices.You can implement those operations efficient using HLD/centroid decomposition.
•  » » » 6 years ago, # ^ |   +10 How to solve it using Centroid Decomposition?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 I figured out that when we switch the values of vertexes a and b, we need to flip the state of every edge on the simple path from a to b either from needing it in our pair connecting to not needing it and vice versa and just count the number of edges we need after every flip. This can be done with heavy light decomposition. Link to my solution:https://www.codechef.com/viewsolution/21809280
 » 6 years ago, # |   +5 OK, so here's my turn to ask something about EBAIT. Not adressing issues connected to this problem, how did you manage to solve it? I see that many teams solved it, however it still seems to me like a really hard problem. I tried to solve it using pretty complicated black box that tells me number of lattice points in first quadrant below line with equation Ax+By=C. This black box is rally tough, but fortunately we had it prewritten, but I still didnt manage to fully solve the problem since I got lost in ocean of formulas. mnbvmar used some algorithm from Wikipedia about continued fractions, but this seems really weird to me and Errichto used some freaky Python function that solved it for him, both of these approaches look nothing at all how I would approach such problem (maybe that's why I didn't solve it?)
•  » » 6 years ago, # ^ |   +10 well, continued fractions seems to be reasonable directions to start from because they give you best approximations of things (with small denominators) and you want to get a good approximation to the start of interval(which is less then end of an interval)
•  » » 6 years ago, # ^ |   +37 A way how I see this problem:You basically have the following inequalities: for some integers for some integers After some hard math I managed to get this: So you need to find between and . I used Stern–Brocot tree to find the closest to the root fraction that lies between L and R. You can also use this.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +3 It's called Stern-Brocot tree. If you google "Stern-Brocot tree site:codeforces.com", you can hopefully find this post where you can simply copypaste.
•  » » 6 years ago, # ^ |   +34 How about this: Try all denominators up to min(C2, 10000), compute the minimum numerator for each. If you didn't find a solution, try 1000 random denominators. If you still didn't find a solution, declare that none exist. AC in 0.05s.
•  » » » 6 years ago, # ^ |   +24
•  » » » 6 years ago, # ^ |   0 So, there's no testcases where there's a single denominator which fits and is quite big (~1e9)? Sounds like bad test suite to me.
•  » » » » 6 years ago, # ^ |   0 Can they be made? How about an extended version with trying numerators up to 10000 too?
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Well, I'm not sure, but something like this should work:Let's get some fraction p/q, approximate it with all the denominators from 1 to c2 from the top and from the bottom. Get closest from both sides and set them as two borders.Of course, you'll also need to construct testcase itself (didn't think whether it's trivial)
•  » » » » » » 6 years ago, # ^ |   0 a b c d should give a range (b / a, (b + d) / (a + c)), so at least any range with max-fraction having the bigger numerator and denominator is doable. When we account for irreducible fractions, that gives even more.When the range of allowed fractions is very tight, I'm thinking of some solution that discards ranges of numerators/denominators that clearly have no solution within the given range...
•  » » » » » » » 6 years ago, # ^ |   0 yep, so if you have p/q and r/s and p,q,r,s <= 5e8, you can always make s > q by multiplying both r and s with some constant. It will mean that r > p automatically.
•  » » » » 6 years ago, # ^ |   +38 Well, test suite was very weak for sure. For example naive solution with Farey sequence worked despite TLing on very small test like 1 2 1 1000000000 999999999 1 
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 There's a way to compute the number of points in integer coordinates inside the triangle (0, 0), (n, 0), (n, (a/b) * n) in O(log(A + B)) with a modified Euclidean algorithm. This is the same as computing the number of points in integer coordinates under the line y * b — x * a <= 0 for 0 <= x <= n. I used this to do binary search to find the first point between the two half-planes.
 » 6 years ago, # |   +59 When will t-shirts be sent?
•  » » 6 years ago, # ^ |   +11 Will t-shirts be sent according to address on codechef profile ... or email queries on the address?