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:
- Omatase-Trinity: hos.lyric, maroonrk, yosupo
- Almost Retired Dandelion: Merkurev, Um_nik
- times187: Cyanic, ix35, s_r_f
- tourist
- Itst两小时阿克离场: newbiegcz, Itst, pupiI
Div2:
- 2-sad walk: Dart-Xeyter, tem_shett, sevlll777
- TeamSeven: liit_mixer, sachin208, jnarutoj
- Fast but not Furious: amirmohammad-nezami, armin.atarod, ymmparsa
- （￣ー￣）: noneTP
- heh: Eyed, penguinhacker, el_heffeh
Preliminarily version of the editorial can be found here. Full version of the booklet will be published at a later time.
Auto comment: topic has been updated by Acko (previous revision, new revision, compare).
plz check. the register doesn't work.
You first need to create a team before registering
[Deleted]
interested
why I am able to register in Div1 also ?
is it rated?
No
ping me if by any chance anybody is interested in teaming up with me
UPD: SORRY BUT I've ALREADY TEAMED UP
How many participants allowed in a team?
"It will be a competition for teams of 1-3 members. There will be at least eight problems."
Read the announcement dude
Number of problems is secret?
Read the announcement dude
Sorry,I read it
Problems are not sorted by difficulty, right?
It wasn't in the previous BubbleCup rounds, so maybe not.
Thanks!
They are not.
Is the order of the questions sorted by difficulty value? (Because this is the icpc rule, I am not sure about this.)
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)
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?
I am pretty sure it is allowed to code simultaneously, that's why the length of the contest was shortened.
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
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.
100% percent agree, we had to practically guess problem H
Is this book generally a good read for problem setters or people who write algo articles?
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.
I didn't expect 14 questions.
Why the TL for J is so tight?
I waste too much time on it ,but get TLE on Test21. :(
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).
Dp is also a good solution ,why not allow it to pass?
https://ibb.co/562QqSV
Thank you . I'm too sleepy now ,I will read it carfully tomorrow.
Still no booklet :p
By the way,can O(64*14)pass?
Yes, some solutions can pass.
But it hugely depends on constant factor, optimizations, etc.
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 :/
You should use faster IO optimizations(for example getchar or fread)
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?
As nothing is mentioned about the number of digits of the input, we believe there exists a case where the judge solution is incorrect.
How many digits after the decimal point can the input values have?
The planned building area is represented as a rectangle with sides width and height. Is it always located at [0, width] \times [0, height]?
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.
What do you think, community? I strongly hope that this kind of problem preparation be gone.
How to solve E: guess the statement.
Can you please rephrase it in a better way?
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.
How to solve div2-M ?
Nevemind didn't see the Div2
After arranging all the pages in the correct order, compare the first point of difference between string i and i+1. Add a directed edge from the alphabet in string i to the one in i+1, and build your graph like this. Then do toposort on it to get the alphabetical order. For the impossible case, check for cycles and also check that in the given dictionary there aren't cases like "aa" followed by "a".
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?
J — amazing time limit :)
Am I the only one to solve it by looking up OEIS ?
I wrote a bruteforce till the poly degree 10, then looked at the output)
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.
I think what you are talking about is Div2 J. Not Div1. J
[never mind]
I submitted with long but still got WA. link
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.
am I only one who overkilled this problem with a overcomplicated dp solution 94783445
same here (with hard optimization)
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).
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.
yeah..this gave AC
Problem F.
Problem J.
Similar to a solution there, we can write
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$$$.
I really like this solution. Thanks. Much better than my very complicated proof of problem J.
How do you come up with such an invariant? Is is something that is based only on intuition?
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.
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
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
J is O(1) per query
I think the test cases for Problem B are weak . My wrong code was accepted it seems. Link to my submission --> https://mirror.codeforces.com/contest/1424/submission/94787727 Though it got accepted It fails on this test case which I thought
5 9
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
2 1 6
3 1 7
4 1 8
5 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.
This should have been a 5 hour contest and not 3 hours.
Can someone explain how to do F?
in problem L, tests have T_i == 0...
How did you write validator for problem M ?
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...
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}$$$)
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)$$$.
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?
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.
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.
Can you please explain how to solve Problem K (div1)/J (div2)?
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.
How to solve div2-B(valuable paper)? Thanks in advance:)
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.
nor — I think your method is correct. Many people's algorithms were accepted incorrectly, and would now fail the new test case 21.
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.
https://mirror.codeforces.com/contest/1424/submission/94794499
@mejiamejia — your code now fails the new test case 21
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.
I got hacked at my submission 94774721, but my intended solution was based on Hall's theorem.
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.
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.
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) \lt 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://mirror.codeforces.com/contest/1424/submission/94802563 Your solution (AC in the contest) gives WA on test 21 on resubmitting (added after the contest).
Thanks for the hack :)
What's wrong with this test to M?
I suspect that the validator is wrong in M... Could somebody elaborate?
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.
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...
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
Since the validator still isn't fixed, hopefully putting a fixed version here will help change that.
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.
http://mirror.codeforces.com/contest/1424/submission/94795249 Could anyone please explain why this is giving TLE??
It's too slow.
can you explain why??
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
Ya this could be a reason but when I changed cout to printf it got accepted http://mirror.codeforces.com/contest/1424/submission/94796933
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
Yeahh thxxx for helpin me out
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.
Yeahh learned something new today
By when shall we expect the editorials Acko?
Sorry, I'm greedy, uphacks on B, C, M, and N weren't enough for me:
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.
You don't validate that polygons don't intersect
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.
Test case 21 was added in uphacking.
okk but why there is not any system testing??
Because all solutions were tested on all test cases during the contest.
but before system testing i think the uphacking test cases are also added
Uphacking happens after the contest and lasts for 7 days. They aren't just going to rejudge all solutions 7 days after the contest.
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://mirror.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?
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.
It's not that weird, similar trick is used in some theoretical algorithms like: 1 2 3
What 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.
Problem M of Div 2
I wonder what "Unexpected verdict" means?
ps: I found it in Hacks.
thx
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.
Shall we even expect editorials? Acko
Acko, please publish editorial
Sorry for the delay — editorial has been published.
How to solve Lonely Numbers — Div1 problem K — Div2 problem J
Observations:
$$$1$$$ is always lonely;
primes greater than $$$\sqrt{n}$$$ are always lonely ($$$P$$$ can never pair with $$$k\times P$$$ for $$$k \lt P$$$);
primes no greater than $$$\sqrt{n}$$$ can always pair with its square;
composites can always be expressed as $$$x \times y$$$ where $$$x$$$ is its smallest prime factor, thus they can always pair with $$$x \times (y-1)$$$.
Editorial ??
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.
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
Auto comment: topic has been updated by Acko (previous revision, new revision, compare).
@Acko ： My team's name is "5times187" .
Can anyone give me a hint of how to optimize bitmask dp in Div 1 problem J ?
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
Orz Itst pupiI and newbiegcz!
Can someone tell me why am I getting a TLE here https://mirror.codeforces.com/problemset/submission/1423/99648601
Hey i made some changes:-
using Fast input output
endl ---to---> "\n"
typedef long long ll ---to---> #define ll long long int
https://mirror.codeforces.com/problemset/submission/1423/99659754
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.
Request to add T1Hack data, few of them are written seriously.
Beside there are only one page of submission,it's not too hard to test them again.
Solution to Problem L: Light Switches that does not require bitset:
Let's treat the switches as vectors in $$$\mathbb{Z}_2^d$$$, where $$$d$$$ is the number of lightbulbs. Each query asks us to find a minimum size set of switches such that their sum equals the queried vector.
Before answering queries, let's find a minimum independent set (MIS) of switches. This is a classical problem which can be solved in many different ways. Now, let's represent each switch which is not in the MIS as a linear combination of switches in the MIS.
To answer a query, let's try to represent the queried vector as a linear combination of switches from the MIS. If this is impossible, then the answer is $$$-1$$$. Otherwise, now that we have the vector's MIS representation, the answer can be found in the following manner (note that we always work with the MIS representation of vectors from now on):
For each subset of switches not in the MIS, find the sum of all vectors in this subset plus the queried vector. Relax the answer with the size of the subset plus the popcount of the sum.
It's too slow to try every subset of switches not in the MIS because there can be up to $$$30$$$, meaning that one would have to test up to $$$2^{30}$$$ subsets. However, notice that the number of switches not in the MIS plus the number of switches in the MIS is at most $$$30$$$. We will find the answer in two different ways depending on $$$a$$$, the size of the MIS.
If $$$a \geq 15$$$, we can try every subset.
If $$$a \lt 15$$$, then we will do bitmask DP. Let $$$dp_{i, v}$$$ be the minimum size subset of switches not in the MIS (considering only the first $$$i$$$ switches not in the MIS) such that the queried vector plus all the vectors in the subset equals $$$v$$$. The base case is $$$dp_{0, \text{queried vector}} = 0$$$. The transitions are $$$dp_{i, v} \rightarrow dp_{i + 1, v}$$$ and $$$dp_{i, v} + 1 \rightarrow dp_{i + 1, v \oplus vec_i }$$$. The answer is the minimum value of $$$dp_{\text{ number of vectors not in the MIS}, v} + \text{popcount}(v)$$$.
The time complexity is $$$O((30 - a) * 2^a)$$$ in the first case and $$$O(2^{30 - a})$$$ in the second.
Submission