### Acko's blog

By Acko, history, 4 months ago,

Hello, Codeforces!

Hope you're all safe and well.

Microsoft Development Center Serbia is thrilled to announce the finals of the 13th edition of Bubble Cup competition! Bubble Cup is an international, ACM-style team contest aimed at university and high school students.

Contest will take place on Sunday, 4th of October at 11AM CEST, virtually. Live results will be available on the official Bubble Cup website (results will be frozen during the last 45 minutes of the competition). Winners will be announced at the closing ceremony. You can find more info on the BubbleCup website.

Just like the previous editions, this final will be followed by an online mirror competition on Codeforces. Mirror will take place on Monday, 5th of October at 15:05 CEST. Contest will last for 3 hours and ACM ICPC rules will be applied. It will be a competition for teams of 1-3 members. There will be at least eight problems.

Just like last year, the finals are divided in two "divisions", called Premier League and Rising Stars. The two contests will have most of their problems in common, but the Rising Stars competition will feature some easier tasks targeted at high school contestants.

Both of the contests will be mirrored here on Codeforces, with Premier League mapping to the Div1 contest and Rising Stars mapping to the Div2 contest. The mirror will use native Codeforces ACM-ICPC team contest rules.

We kindly ask participants of the virtual finals to hold off discussing problems publicly until the mirror is over.

Contest was mainly prepared by employees of MDCS with help from our alumni member Lazar Milenković (milenkoviclazar). We give our thanks to Nikolay Kalinin (KAN) for the round coordination, Mike Mirzayanov (MikeMirzayanov) and the team behind Codeforces and Polygon platforms. Special thanks goes to Alexandr Lyashko (knightL) for helping out with problem testing.

The contest will be unrated. The reason for this is because rules of this contest are not common for Codeforces.

Editorial will be available in the booklets section on the Bubble Cup website sometime after the online mirror ends.

You can find problems from previous finals on our Codeforces online mirror competitions:

Bubble Cup 8 — Finals [Online Mirror]

Bubble Cup 9 — Finals [Online Mirror]

Bubble Cup X — Finals [Online Mirror]

Bubble Cup 11 — Finals [Online Mirror, Div. 1]

Bubble Cup 11 — Finals [Online Mirror, Div. 2]

Bubble Cup 12 — Finals [Online Mirror, Div. 1]

Bubble Cup 12 — Finals [Online Mirror, Div. 2]

We wish you best of luck in competition!

Update #1: Given the current situation we want everyone to be safe and enjoy the Bubble Cup finals from their home and that's why team members will be allowed to work on different machines.

Update #2: Congratulations to the winners!

Div1:

1. Omatase-Trinity: hos.lyric, maroonrk, yosupo
2. Almost Retired Dandelion: Merkurev, Um_nik
3. times187: Cyanic, ix35, s_r_f
4. tourist
5. Itst两小时阿克离场: newbiegcz, Itst, pupiI

Div2:

1. 2-sad walk: Dart-Xeyter, shart23, sevlll
2. TeamSeven: gabilash1104, sachin208, jnarutoj
3. Fast but not Furious: amirmohammad-nezami, armin.atarod, Parsa84
4. （￣ー￣）: noneTP
5. heh: Eyed, penguinhacker, stEV

Preliminarily version of the editorial can be found here. Full version of the booklet will be published at a later time.

• +222

 » 4 months ago, # |   +2 Auto comment: topic has been updated by Acko (previous revision, new revision, compare).
 » 4 months ago, # |   -13 plz check. the register doesn't work.
•  » » 4 months ago, # ^ |   0 You first need to create a team before registering
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 Personal Deleted. Not Visible.
 » 4 months ago, # | ← Rev. 2 →   -24 Thanks!!
•  » » 4 months ago, # ^ |   0 interested
•  » » 4 months ago, # ^ |   0 how about team up with yourself? ;)
•  » » 4 months ago, # ^ |   0 Yes of course, pm me if you are all in.
 » 4 months ago, # |   -26 why I am able to register in Div1 also ?
 » 4 months ago, # |   -17 is it rated?
•  » » 4 months ago, # ^ |   0 No
 » 4 months ago, # | ← Rev. 3 →   0 ping me if by any chance anybody is interested in teaming up with me UPD: SORRY BUT I've ALREADY TEAMED UP
•  » » 4 months ago, # ^ |   0 I've sent you a message. It'd be a great pleasure to be your teammate.
•  » » 4 months ago, # ^ |   0 i'm interested in teaming up too.
 » 4 months ago, # | ← Rev. 2 →   -17 How many participants allowed in a team?
•  » » 4 months ago, # ^ |   0 "It will be a competition for teams of 1-3 members. There will be at least eight problems." Read the announcement dude
•  » » » 4 months ago, # ^ |   0 Got it.
 » 4 months ago, # |   0 Why you can compete in Bubble Cup #13 just by joining a team?
 » 4 months ago, # |   0 Number of problems is secret?
•  » » 4 months ago, # ^ |   0 There will be at least eight problems. Read the announcement dude
•  » » » 4 months ago, # ^ |   0 Sorry,I read it
 » 4 months ago, # |   0 May I ask whether I can take part in this contest as an individual competitor?
•  » » 4 months ago, # ^ |   0 Yes.
 » 4 months ago, # |   0 if there is any place left in any team , please let me join your team.
•  » » 4 months ago, # ^ |   0 Please pm me, I'm looking for teammates also.
•  » » 4 months ago, # ^ |   0 i'm looking to team up too.
•  » » » 4 months ago, # ^ |   0 Please accept the invitation. Thank you !
 » 4 months ago, # |   +8 Problems are not sorted by difficulty, right?
•  » » 4 months ago, # ^ |   0 It wasn't in the previous BubbleCup rounds, so maybe not.
•  » » » 4 months ago, # ^ |   0 Thanks!
•  » » 4 months ago, # ^ |   0 They are not.
 » 4 months ago, # |   0 Is the order of the questions sorted by difficulty value? (Because this is the icpc rule, I am not sure about this.)
•  » » 4 months ago, # ^ |   +8 Problems are sorted arbitrarily, I don't think that even on ACM ICPC they are sorted (unless something has changed since last time I competed)
 » 4 months ago, # |   +8 I have a couple of questions. What is native Codeforces ACM-ICPC team contest rules? I haven't heard of this rule. I'm particularly concerned about whether it is allowed to copy-paste my library. Team members can work on their own computers. Does this mean we can code simultaneously? Or we still shouldn't use multiple computers at the same time?
•  » » 4 months ago, # ^ |   +8 I am pretty sure it is allowed to code simultaneously, that's why the length of the contest was shortened.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +10 Quoting the rule from the official website:"During the finals, contestants are allowed to use any code previously written by themselves, as well as any source of information on the Internet. You're not allowed to use somebody else's code."So to answer your questions: 1. You can copy/paste your library 2. You can code simultaneously on different computers
 » 4 months ago, # |   0 if my team is successfully registered,can i add participants into my team?@Acko
 » 4 months ago, # |   +140 Get the book "BUGS in Writing: A Guide to Debugging Your Prose", statements are unintuitive (e.g in H) and hard to understand. Also consider adding more formal definition for statements.
•  » » 4 months ago, # ^ |   +5 100% percent agree, we had to practically guess problem H
•  » » 4 months ago, # ^ |   +23 Is this book generally a good read for problem setters or people who write algo articles?
•  » » » 4 months ago, # ^ |   +25 I found the book from the webpage of MIT6.xxx (The human intelligence enterprise), it is a general guide of writing for "computer science people". The book consists many segments, each segment covers one conceptual chunk of information, and each stands alone.I bought a copy months ago and found the book quite fun, and probably helpful for good writing, though I haven't read much of it.I would suggest you to get a scanned version from the web and read the foreword and readme to see if you are interested, since the book is hard to describe in short.
 » 4 months ago, # |   +11 I didn't expect 14 questions.
 » 4 months ago, # |   +8 Why the TL for J is so tight?
•  » » 4 months ago, # ^ |   0 I waste too much time on it ,but get TLE on Test21. :(
•  » » » 4 months ago, # ^ |   0 There is a better solution :)It was intended for dp problems to pass only if they are maximally optimized.The booklet will probably be uploaded tomorrow, and there is a simple derivation that shows that the answer is (m/2 — m/4 + 1)(m/4 + 1) (where / is in integer arithmetic).
•  » » » » 4 months ago, # ^ |   +3 Dp is also a good solution ,why not allow it to pass?
•  » » » » 4 months ago, # ^ |   0
•  » » » » » 4 months ago, # ^ |   0 Thank you . I'm too sleepy now ,I will read it carfully tomorrow.
•  » » » » 3 months ago, # ^ |   0 Still no booklet :p
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 By the way,can O(64*14)pass?
•  » » » » 4 months ago, # ^ |   0 Yes, some solutions can pass.But it hugely depends on constant factor, optimizations, etc.
•  » » 4 months ago, # ^ |   0 I also initially got TLE 21. After constant optimisations I barely got AC in 998ms (94776156). Maybe DP over carries in the sum isn't the intended solution :/
•  » » » 4 months ago, # ^ |   +16 You should use faster IO optimizations(for example getchar or fread)
 » 4 months ago, # | ← Rev. 2 →   +98 These are what we sent and received for problem E during the contest:The input is a floating number while we need to do binary decisions. Are the judge solutions accurate? Yes As nothing is mentioned about the number of digits of the input, we believe there exists a case where the judge solution is incorrect. No comments How many digits after the decimal point can the input values have? 4 decimal places. The planned building area is represented as a rectangle with sides width and height. Is it always located at [0, width] \times [0, height]? Yes What is the constraints of N? If the only constraint is N Q <= 10^6, then there would be 10^6 * 40 points in the input. N <= 150000 What do you think, community? I strongly hope that this kind of problem preparation be gone.
 » 4 months ago, # |   +24 How to solve E: guess the statement.
•  » » 4 months ago, # ^ |   +13 Can you please rephrase it in a better way?
 » 4 months ago, # |   +21 Why does E have such a small amount of constraints? I don't see anything in the statement that guarantees that the input file is smaller than $10^{10^{100}}$ bytes.
 » 4 months ago, # |   0 How to solve div2-M ?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Nevemind didn't see the Div2
•  » » 4 months ago, # ^ |   +5 Topological sorting
 » 4 months ago, # | ← Rev. 2 →   +10 I surely misunderstand E but cannot get what I'm missing.How I understand E: Get the sum of the whole areas of the polygons that intersect with the given circle. But this is too easy, right?I also don't get what that "planned building area rectangle" has to do with the problem.Can someone point out what I'm missing here?
 » 4 months ago, # |   +13 J — amazing time limit :)
•  » » 4 months ago, # ^ | ← Rev. 2 →   +17 Am I the only one to solve it by looking up OEIS ?
•  » » » 4 months ago, # ^ |   0 I wrote a bruteforce till the poly degree 10, then looked at the output)
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 I used the same OEIS sequence.But, When I am precomputing with N=1e6+5 then I am getting AC. But when I am using N=1e7+5 then getting WA also after N=1e7+5 precomputation for all test cases with n>1000 I am receiving actualanswer+1. I don't get why I am getting actual answer+1 for N=1e7+5 precomputation.Can you tell me what's going on?Edit: Talking about Div2 J.
•  » » » » 4 months ago, # ^ |   0 I think what you are talking about is Div2 J. Not Div1. J
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 [never mind]
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 I submitted with long but still got WA. link
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +13 For the sake of a solution which doesn't use OEIS (since our team didn't use OEIS), note that $7 = 2^3 - 1$, so expand the coefficients of the polynomial into their binary representation, and let $a$ be the sum of all powers of $2$ which have the first bit (from the right) set in the coefficient, $b$ be the sum of all powers of $2$ which have the second bit set in the coefficient and $c$ for the third bit.Then you have a bijection between the solutions of $a + 2b + 4c = m$ over non-negative integers $a, b, c$, and the set of all solutions in the problem statement, so we need to just count the number of solutions to the former equation. Now to count them, it suffices to count the number of solutions to $b + 2c \le \lfloor \frac{n}{2} \rfloor$, which turns out to be precisely the expression at OEIS.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +5 am I only one who overkilled this problem with a overcomplicated dp solution 94783445
•  » » » » 4 months ago, # ^ |   0 same here (with hard optimization)
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   +5 Could you explain your solution? I tried submitting a very similar dp solution here as well as during the contest but I can't seem to fit it in TL (I wrote an iterative dp too, but somehow it's slower than the recursive one because it visits all states).
 » 4 months ago, # | ← Rev. 8 →   0 Wasn't J can be solved by this sequence?I got WA on test case 3? Can anyone tell me why my solution is wrong on n=10000?Edit: Got AC when changed precomputation from 1e7 to 1e6.
•  » » 4 months ago, # ^ |   0 yeah..this gave AC
 » 4 months ago, # | ← Rev. 3 →   +17
•  » » 4 months ago, # ^ |   +74 Similar to a solution there, we can write $\begin{eqnarray} m&=&a_0+2a_1+2^2 a_2+2^3 a_3 + 2^4 a_4 + 2^5 a_5 + 2^6 a_6 + \cdots \\ &=&\left(a_0 + 8a_3 + 8^2 a_6+\cdots\right)+2\left(a_1+8a_4+8^2a_7+\cdots\right)+4\left(a_2+8a_5+8^2a_8+\cdots\right) \\ &=&x+2y+4z \end{eqnarray}$where $x,y,z$ can be any non-negative integer (since the coefficients can be between $0$ and $7$, and we've represented the numbers in base $8$). So the answer is the number of non-negative integer solutions to $x+2y+4z=m$.
•  » » » 4 months ago, # ^ |   +10 I really like this solution. Thanks. Much better than my very complicated proof of problem J.
•  » » 3 months ago, # ^ |   0 How do you come up with such an invariant? Is is something that is based only on intuition?
•  » » » 3 months ago, # ^ |   0 Same, no idea how can we can come up with such solution. I can only see people reducing the problem to bitmask dp with O(t*64*8) at best.
 » 4 months ago, # |   0 how to solve G?
 » 4 months ago, # |   +312 Well that was awful. Statements are long and unreadable in places. You don't give accurate limitations. 15 problems for 3 hours with this kind of writing? I believe there are some interesting problems underneath but you buried them under (at least) 8 problems "write obvious solution in 200 lines of code" (That's my own butthurt, but) What's the point of giving 5e5 tests in J? What were you trying to cut out? Will the problem be worse with one test? Reading the input takes at least 0.3 sec with scanf wtf
•  » » 4 months ago, # ^ |   +26 Couldn't have agreed with point 3 more -- as we were doing the non-mirror version of the contest, I think none of the team members did take a look in 7-8 problems at least
•  » » 4 months ago, # ^ |   +29 J is O(1) per query
 » 4 months ago, # | ← Rev. 5 →   +44 I think the test cases for Problem B are weak . My wrong code was accepted it seems. Link to my submission --> https://codeforces.com/contest/1424/submission/94787727 Though it got accepted It fails on this test case which I thought5 91 1 11 2 21 3 31 4 41 5 52 1 63 1 74 1 85 1 9 The answer must be -1 and my code gives the answer as 9 and still got accepted. Please correct me if I am wrong somewhere.
 » 4 months ago, # | ← Rev. 2 →   +74 This should have been a 5 hour contest and not 3 hours.
 » 4 months ago, # |   +3 Can someone explain how to do F?
 » 4 months ago, # |   0 in problem L, tests have T_i == 0...
 » 4 months ago, # |   +38 How did you write validator for problem M ?
 » 4 months ago, # | ← Rev. 2 →   +5 I passed M 10 minutes after the game, (it looks like 20 minutes, that's because the codeforces main station seems to be banned by GFW for 10 minutes and i cannot access during the period), If it is a rated contest, I would regret it for a long time...What a sad story...
 » 4 months ago, # | ← Rev. 2 →   +72 A neat solution to J:Think of the answer to query $n$ as the n-th coefficient in the following polynomial: (where $B$ is some large number, greater than $10^{18}$) \begin{aligned} &\prod_{i=0}^{B} (1+x^{2^i}+x^{2\cdot 2^i}+\cdots+x^{7\cdot 2^i})\\ =&\prod_{i=0}^{B} \frac{1-x^{2^{i+3}}}{1-x^{2^i}} \\ =& \frac{(1-x^{2^{B+3}})(1-x^{2^{B+2}})(1-x^{2^{B+1}})}{(1-x)(1-x^2)(1-x^4)} \end{aligned}After ignoring high order terms, it will be $\frac{1}{(1-x)(1-x^2)(1-x^4)}$. This is equivalent to complete knapsack problem with item weights $1,2,4$. A little bit math shows that the n-th coefficient is just $\sum\limits_{i=0}^{\lfloor \frac n4\rfloor}\sum\limits_{j=0}^{\lfloor\frac{n-4i}{2}\rfloor}1 = (\lfloor \frac n2 \rfloor - \lfloor \frac n4 \rfloor + 1)(\lfloor \frac n4\rfloor + 1)$.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Div2 J : I used OEIS for generating the sequence formula.When I am precomputing with N=1e6+5 then I am getting AC. But when I am using N=1e7+5 then getting WA also after N=1e7+5 precomputation for all test cases with n>1000 I am receiving actualanswer+1. I don't get why I am getting actual answer+1 for N=1e7+5 precomputation.Can you please help me with what's going on?
•  » » 4 months ago, # ^ |   +18 Here's a more combinatorial version of the same solution (which was how I came up with my solution). Note that $7=2^3−1$, so expand the coefficients of the polynomial into their binary representation, and let $a$ be the sum of all powers of 2 which have the first bit (from the right) set in the coefficient, $b$ be the sum of all powers of 2 which have the second bit set in the coefficient and $c$ for the third bit.Then we have a bijection between the solutions of $a+2b+4c=m$ over non-negative integers $a,b,c$, and the set of all solutions in the problem statement, so we need to just count the number of solutions to the former equation. Now to count them, it suffices to count the number of solutions to $b+2c\le\lfloor \frac{n}{2} \rfloor$, which turns out to be precisely the expression claimed above.
 » 4 months ago, # |   +8 I could be wrong, but I think a lot of people had solutions accepted from problem B which should not have been accepted. The test cases were weak and new ones have been retrospectively added which would have resulted in failures.Problem K (div1) / J (div2) was also very poor. The entire performance of the algorithm depended on reading the inputs fast enough. That is weak.
•  » » 4 months ago, # ^ |   0 Can you please explain how to solve Problem K (div1)/J (div2)?
•  » » » 4 months ago, # ^ |   +8 Sure:The first thing is to ensure you have a fastio configuration — otherwise reading / printing 10**6 times will be enough to TLE.After that, the problem is relatively simple. 1 is always lonely. Beyond that, as we extend the sequence 1,2,3,... etc, the newest number lonely iff it is prime. This is because otherwise we can write the number as n = pq, where p is the smallest prime divisor of n. Then q > 1, otherwise n is prime (contradiction). Take m = p(q-1), then we have the triangle p, q, q-1 which satisfies our requirements (since p>1 and p <= q).When does the prime stop being lonely? The prime stops being lonely when its square joins the set, since p*p, p give us the triangle p, p, 1. It is trivial to show that p is lonely before its square joins, since the triangle p, k, 1 is not possible for k < p.So we generate a list of primes < 10**6 (Sieve of Eratosthenes), and then precompute the answers from 1 to 10**6, adding one each time we hit a prime and subtracting one each time we hit the square of a prime.This can all be done is O(10**6) time.To get the required answers, we simply query our precomputed answers.
 » 4 months ago, # |   0 How to solve div2-B(valuable paper)? Thanks in advance:)
•  » » 4 months ago, # ^ |   +4 I did a binary search on the answer, by removing all edges greater than a certain weight and then doing Hopcroft Karp to find a maximum matching, and check whether the matching is a perfect matching.However, there seem to be people who didn't use matching at all, and I'm curious about their solutions too.
•  » » » 4 months ago, # ^ |   0 nor — I think your method is correct. Many people's algorithms were accepted incorrectly, and would now fail the new test case 21.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Why do we need Hopcroft? I don't think it is necessary. I also thought of the maximum matching of the bipartite graph at first, but found it to be redundant. Just mark the two end points of each road and check whether all factories and airports are all marked.upd:Sorry, I thought about it carefully, and the maximum matching of the bipartite graph is indeed needed.
•  » » » » 4 months ago, # ^ |   0 https://codeforces.com/contest/1424/submission/94794499@mejiamejia — your code now fails the new test case 21
•  » » » » » 4 months ago, # ^ |   0 Yes, the maximum matching of the bipartite graph is necessary. My algorithm is easy to have counterexamples, that is, a factory connects all airports, and an airport connects all factories. I thought of the wrong algorithm during the game because I felt it first The data range of is very large, and running the bipartite graph matching will exceed the time limit.
•  » » » » » » 4 months ago, # ^ |   0 I got hacked at my submission 94774721, but my intended solution was based on Hall's theorem.
•  » » » » » » 4 months ago, # ^ |   +3 Yeah — I failed to come up with a bipartite matching that satisfied the time constraints. Tricky problem, made to look easier than it was by the poor test cases.
•  » » » 4 months ago, # ^ |   0 It was simple greedy tbh. Just greedily remove the high weight edges as long as it is possible. The first edge that we cannot remove is our answer.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 What is the condition of not being able to remove the last edge?In my solution, I assert that the condition is that $MaxMatching(resultantGraph) < N$, and if there is a simpler condition that this degenerates to, please let me know the condition and a proof of it.EDIT: https://codeforces.com/contest/1424/submission/94802563 Your solution (AC in the contest) gives WA on test 21 on resubmitting (added after the contest).
•  » » » » » 4 months ago, # ^ |   0 Thanks for the hack :)
 » 4 months ago, # |   +86 What's wrong with this test to M? 3 3 2 3 4 4 1 3 5 4 2 
•  » » 4 months ago, # ^ |   +43 I suspect that the validator is wrong in M... Could somebody elaborate?
•  » » » 4 months ago, # ^ |   -95 Validator checks only if matrix is Monge array, as we used Monge arrays for the test set. The solution doesn't use any properties specific to Monge arrays, and it works for any matrix that satisfy constraints from the problem statement. We'll try to fix the validator.
•  » » » » 4 months ago, # ^ |   +68 Even though a validator and decent tests are way easier to make than the solution to the problem, none of those existed in this problem and only monge arrays were used. I wonder why...
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   +10 I mean, I believe SMAWK works also for the matrices they described in the task statement... Even they described those matrices in the paper (Section II).Does this mean this is a great task? /s
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +10 Since the validator still isn't fixed, hopefully putting a fixed version here will help change that. Correct validator#include "testlib.h" #include using namespace std; int main(int argc, char* argv[]) { registerValidation(argc, argv); int n = inf.readInt(1,1000,"n"); inf.readSpace(); int m = inf.readInt(1,1000,"m"); inf.readEoln(); vector> v(n); for(int i=0;i0) { for (int j=0;jv[i-1][k] && v[i][j]<=v[i][k]) { string s="submatrix ("+to_string(i)+","+to_string(j+1)+"), ("+to_string(i+1)+","+to_string(k+1)+") is incorrect."; ensuref(0,s.c_str()); } } } } inf.readEof(); } It's also possible to make the time complexity of the validator $O(nm$ $log$ $m)$ with divide and conquer but the speed difference isn't that big.
 » 4 months ago, # |   +4 http://codeforces.com/contest/1424/submission/94795249 Could anyone please explain why this is giving TLE??
•  » » 4 months ago, # ^ |   +31 It's too slow.
•  » » » 4 months ago, # ^ |   0 can you explain why??
•  » » » » 4 months ago, # ^ |   -22 It's slower than $O(t \cdot n)$, while $n,t \leq 10^6$, there's no way it'll pass. Read this or smth
•  » » » » » 4 months ago, # ^ |   +7 Ya this could be a reason but when I changed cout to printf it got accepted http://codeforces.com/contest/1424/submission/94796933
•  » » » » » » 4 months ago, # ^ |   0 Oh, sorry, I've misread it... Yeah, printfs are usually faster than couts. That's why people are using these strange lines with "IOSBASE" or smth
•  » » » » » » » 4 months ago, # ^ |   +5 Yeahh thxxx for helpin me out
•  » » » » » » 4 months ago, # ^ |   +6 No, it's $\mathcal O (\max n + t)$, but somehow with a relatively large constant. I'm sorry the previous code didn't pass :(. Maybe learn constant optimization next time.
•  » » » » » » » 4 months ago, # ^ |   +3 Yeahh learned something new today
 » 4 months ago, # |   +44 By when shall we expect the editorials Acko?
 » 4 months ago, # |   +91 Sorry, I'm greedy, uphacks on B, C, M, and N weren't enough for me:
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Yeah, I believed that it is almost impossible to solve (even to read the input for) the case with $n = 10^6$ and $q = 1$. That's why we issued a clar and told that "N <= 150000" and "4 decimal places."Based on your hack, it seems that the validator seems to check $n \le 150000$, I suspect it does not check the number of the digits; chance for yet another unexpected verdict :)Edit: Oh I misread the numbers of your hack. I must admit I assumed that the test data is not too strong during the contest. Kudos for hacks.
•  » » » 3 months ago, # ^ |   0 You don't validate that polygons don't intersect
 » 4 months ago, # |   0 why there is no system testing?? Many group solve the question no B valuable paper using binary search but they actually got wrong ans in test case 21 that i think added after the contest. So if system testing is there then i think they might got why their logic get WA on test case 21. Please pay attention what i have said. Thank you.
•  » » 4 months ago, # ^ |   0 Test case 21 was added in uphacking.
•  » » » 4 months ago, # ^ |   0 okk but why there is not any system testing??
•  » » » » 4 months ago, # ^ |   0 Because all solutions were tested on all test cases during the contest.
•  » » » » » 4 months ago, # ^ |   0 but before system testing i think the uphacking test cases are also added
•  » » » » » » 4 months ago, # ^ |   +5 Uphacking happens after the contest and lasts for 7 days. They aren't just going to rejudge all solutions 7 days after the contest.
•  » » » » » » » 4 months ago, # ^ |   0 thank you i understand
 » 4 months ago, # |   +145 The statement in M says: $1 \leq n, m \leq 10^6$. I looked through the tests and saw that all tests have $1 \leq n, m \leq 10^3$. Moreover I tried uphacking some solution with tests with $n, m = 1001$ (https://codeforces.com/contest/1423/hacks/669698) and it says "FAIL Integer parameter [name=rows] equals to 1001, violates the range [1, 1000]". Why is that?
 » 4 months ago, # | ← Rev. 2 →   +47 I did a weird constant optimization for J.We can write $m_i$ as a binary string with length $L=60$. Let $M=8$ be the size of coefficient set. We can write a DP solution in $O(t \cdot L \cdot M)$. However, this approach TLEs.I decided to divide the string with length $L$ into blocks of size $B$. We can precompute the DP transition matrix for all binary strings from $0$ to $2^B-1$ in $O(B \cdot 2^B \cdot M^3)$. Then, for each $t$ queries we can multiply $\lceil \frac{L}{B} \rceil$ matrices with the base case matrix in $O(\lceil \frac{L}{B} \rceil \cdot M^2)$ to get the answer.Thus the final complexity is $O(B \cdot 2^B \cdot M^3 + t \cdot \lceil \frac{L}{B} \rceil \cdot M^2)$. Picking $B=12$ passes the testcases. Submission.
•  » » 4 months ago, # ^ |   +38 It's not that weird, similar trick is used in some theoretical algorithms like: 1 2 3What is imo a little weird is that this trick indeed improved actual running time enough to get past TL instead of just improving theoretical time complexity.
 » 4 months ago, # |   +8
 » 4 months ago, # |   +19 I wonder what "Unexpected verdict" means?ps: I found it in Hacks.thx
•  » » 4 months ago, # ^ |   +23 Most probably: one of the model solutions failed on the hack. Or maybe the checker failed. There are probably some other possible reasons, too. Either way, it implies that the organizers botched something.
 » 4 months ago, # |   +64 Shall we even expect editorials? Acko
•  » » 3 months ago, # ^ |   0 Acko, please publish editorial
•  » » » 3 months ago, # ^ |   +3 Sorry for the delay — editorial has been published.
 » 4 months ago, # |   +3 How to solve Lonely Numbers — Div1 problem K — Div2 problem J
•  » » 4 months ago, # ^ |   +7 Observations: $1$ is always lonely; primes greater than $\sqrt{n}$ are always lonely ($P$ can never pair with $k\times P$ for \$k
 » 3 months ago, # |   +7 Editorial ??
 » 3 months ago, # |   +44 Problem E has a lot of issues with hacks.It's too easy to generate a hack, just print as many integers as you can. In fact, I hacked all but two solutions like this. Also, input validation is bad, it doesn't check whether polygons intersect. In fact, you can just print the same polygon as many times as you want. It's also kind of impossible to do within reasonable time.My suggestion: remove all hacks, restore testcases to the official ones used for the BC finals, and disable hacks for this problem.
 » 3 months ago, # | ← Rev. 3 →   -6 Can somebody tell me why are these two problems having this high rating difference in spite of them being the same problems : PROBLEM1 -> 2200 rating PROBLEM2 ->1600 rating I literally used almost the same solution for both the problems SOLUTION1#include #define ar array using namespace std; const int mxN =101 ; int n,d[mxN]; vectoradj[mxN] ; signed main() { cin >> n ; vectors(n) ; for(int i=0;i> s[i] ; for(int i=1;i=n2&&i1=n1||i1>=n2) break ; if(s[i-1][i1]==s[i][i1]) continue ; adj[s[i-1][i1]-'a'].push_back(s[i][i1]-'a') ; d[s[i][i1]-'a']++; break; } } queuequ ; string ans ; for(int i=0;i<26;i++) if(!d[i]) qu.push(i); while(qu.size()){ int u = qu.front() ; qu.pop() ; for(int x:adj[u]){ --d[x] ; if(!d[x]) qu.push(x) ; } ans+=(char)(u+'a') ; } cout << (ans.size()==26?ans:"Impossible") ; }  SOLUTION2#include #define ar array using namespace std; const int mxN =1e3+1 ; int n,d[mxN],k; vectoradj[mxN] ; vector a[mxN] ; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >>k; for(int i=0,c;i> c ;string s1; for(int j=0;j> s1;a[c].push_back(s1) ; } } vectors; for(int i=0;iok(26) ; int al=0 ; for(string x:s) for(char c:x){ if(!ok[c-'a']) ++al ,ok[c-'a']=1; } for(int i=1;i=n2&&i1=n1||i1>=n2) break ; if(s[i-1][i1]==s[i][i1]) continue ; adj[s[i-1][i1]-'a'].push_back(s[i][i1]-'a') ; d[s[i][i1]-'a']++; break; } } queuequ ; string ans ; for(int i=0;i<26;i++) if(!d[i] && ok[i]) qu.push(i); while(qu.size()){ int u = qu.front() ; qu.pop() ; for(int x:adj[u]){ --d[x] ; if(!d[x]) qu.push(x) ; } ans+=(u+'a') ; } cout << (ans.size()==al?ans:"IMPOSSIBLE") ; } 
 » 3 months ago, # |   0 Auto comment: topic has been updated by Acko (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 2 →   0 @Acko ： My team's name is "5times187" .
 » 3 months ago, # |   0 Can anyone give me a hint of how to optimize bitmask dp in Div 1 problem J ?
 » 3 months ago, # |   0 I tried the problem 1424G many times but its giving wrong and on 7th test case. Can anyone tell the idea behind the question or provide with a solution
 » 2 months ago, # |   0 Orz Itst pupiI and newbiegcz!
 » 2 months ago, # |   0 Can someone tell me why am I getting a TLE here https://codeforces.com/problemset/submission/1423/99648601
•  » » 2 months ago, # ^ |   +3 Hey i made some changes:-using Fast input outputendl ---to---> "\n"typedef long long ll ---to---> #define ll long long inthttps://codeforces.com/problemset/submission/1423/99659754
•  » » » 2 months ago, # ^ | ← Rev. 4 →   0 I had tried using fast IO earlier also but it still gave TLE. Weird but thanks a lot.PS: Just went through the comments and saw that someone previously had posted a similar issue. Should have read the comments first.