A — Large Digits
Calculate the sum of the digits of both integers, and print out the maximum.
Time complexity: $$$O(1)$$$ My solution
B — Gentle Pairs
As the slope $$$m$$$ of a line between two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ can be found by the equation $$$m = \frac{y_2-y_1}{x_2-x_1}$$$, we simply need to compute the value of $$$m$$$ for each pair $$$(i,j)$$$, while adding $$$1$$$ to our count every time $$$-1 \le m \le 1$$$.
Time complexity: $$$O(N^2)$$$ My solution
C — 1-SAT
We observe that a string $$$T$$$ is unsatisfiable if there exists $$$S_i$$$ such that $$$S_i = T$$$ and $$$S_j$$$ such that "!" $$$+ S_j = T$$$. We can maintain a data structure, such as a map or a set, and each time we add a new string to our set, we check if its pair string (with or without a leading "!") has already been added. If it has, we have found our answer, and we can simply print it (removing a leading "!" if necessary), and exit.
If, after processing all the input strings, no unsatisfiable string has been found, we print "satisfiable".
Time complexity: $$$O(|S|log(|S|))$$$ My solution
D — Choose Me
Notice that every time Takahashi makes a speech in some town $$$i$$$, his vote count, relative to Aoki's vote count, increases by $$$2A_i + B_i$$$, as he gains $$$A_i + B_i$$$ voters, while Aoki loses $$$A_i$$$ voters. We can sort the towns in decreasing order of $$$2A_i + B_i$$$, and greedily take the town which adds most relative votes until Takahashi's relative votes are greater than Aoki's.
Time complexity: $$$O(NlogN)$$$ My solution
E — Through Path
As all queries involve certain edges, once we perform a DFS traversal of the tree, rooted at some arbitrary vertex, each query will involve a parent and child vertex in some order. If we are asked to increase by $$$x_i$$$ the vertexes reachable from the child vertex without visiting the parent vertex, we can simply increase the value of all vertexes in the child vertex's subtree by $$$x_i$$$. On the other hand, if we are asked to increase by $$$x_i$$$ all the vertexes reachable from the parent vertex without visiting the child vertex, we need to increase by $$$x_i$$$ all vertexes which are not in the subtree of the child vertex. We can do this by maintaining a variable which is to be added to all vertexes, and increasing it by $$$x_i$$$, and decreasing the value of all the vertexes in the child vertex's subtree by $$$x_i$$$, effectively undoing the global change for those vertexes. We can perform these changes by doing a total of two DFS traversals.
Time complexity: $$$O(N)$$$ My solution
F — Close Group
This is a classical dynamic programming with bitmasks problem. We can calculate the minimum amount of components possible for some mask $$$m$$$, and iterate over its submasks to reduce this number further. More to be added if there are requests for such.
Time complexity: $$$O(3^N)$$$ My solution
I don't like your solution for problem B. You use doubles which is prone to precision errors and its dangerous to compare doubles because of their precision errors. If you simplify that equation you can use ints and avoid using doubles which IMHO is much safer.
Yes, exactly that's an overkill and somewhat prone to error IMO.. we can simply check for all pairs and count those satisfying
I think you can probably prove that doubles will work here, but I agree that it's simpler and less error-prone in-contest to avoid floating-point whenever possible.
I agree, but I only did this solution after noticing that $$$|x_i|,|y_i| \le 10^3$$$. As a rule of thumb, precision values aren't a problem unless the values are $$$\ge 10^5$$$.
Hi can you please provide a proof for your claim? Thanks!
Just from experience
with solving bad problems.Nice post! May I suggest including your runtime at the end of each problem's explanation?
Good idea! I added them now :)
What is your time complexity for problem F? Isn't it $$$3^n$$$?
Yes. I think that intended is $$$3^n$$$.
Yep, it is! You can read more about why this is the case here.
I solved F by constructing all possible cliques combinations and count them. With the given testdata this actually runs much faster than the bitmask solution. link
However, I would like to understand how the bitmask thing works. What is the idea, why does these loops give the correct answer?
I would like someone to explain the same, but here's what i understood.
We choose a mask m such that the ones represent vertices. then with the two inner loops, we check if this subset of vertices forms a clique. If it does, dp[m]=1 else infinity. we similarly compute all masks, and here's the important part, we iterate over all submasks of a mask, what this does is for any submask s of mask m, we can say dp[m]=min(dp[m],dp[s]+dp[s^m]). what this basically means is we're computing the minimum number such that the current configuration m can be obtained using any possible submasks (that form cliques), s and s^m. We can be sure that submasks will be calulated for m before computing dp[m].
Maybe someone else familiar with it can explain it better?
I'm sorry but what does the value of the
xorvalues^mmean?Let s and s' be two masks that together give mask m.
s ^ s' = m
using commutative property of xor,
(a^b)=c, then (a^c)=b,
s' = (m^s)
This is a common property used in bitmasks, I learned that recently from the recent codechef cookoff problem.
so basically both s and (s^m) are submasks of m, we are just calculating m as a combination of its submasks.
May I please ask somebody to explain why does the
2Ai + Biworks for D, while theAi + Bidoesn't? Thanks!As explained in the editorial above, when Takahashi makes a speech in town $$$i$$$, he gains the $$$A_i$$$ previously pro-Aoki votes, and the $$$B_i$$$ previously pro-Takahashi (but not previously voting) votes. On the other hand, Aoki loses the $$$A_i$$$ votes he was previously going to get from pro-Aoki voters. So the total relative change in votes is $$$A_i + B_i - - A_i = 2A_i + B_i$$$. Sorting by $$$A_i+B_i$$$ is not the same thing, and thus it is incorrect.
Is there a classic problem with the same idea? 'Cause I wondered how a lot of people were able to come up too fast with this sorting 2A[i]+B[i] idea instead of A[i]+B[i].
Not that I've seen, but it's quite easy to see if you look at it logically, i.e. think about what is happening when Takahashi makes a speech in a town. How does this affect previously pro-Takahashi voters and pro-Aoki voters?
Can anybody help me with problem D ("Choose Me"). My approach was:- - first, let number of votes of Takahashi be 0 and that of Aoki be the total sum of A[i] i.e all the votes - Now, sort the whole array on the basis of A[i]+B[i] value, so that when Takahashi goes to a town to for speech he could earn as much as votes as he can, now when he chooses a particular town (after sorting) the votes of Takahashi will increase as he will get votes of both voters of ith town and Aoki will lose the amount of A[i] from his vote's count. and Takahashi will keep adding the amount(i.e he will keep giving speeches) until his votes are strictly greater than Aoki's votes.
This is explained in literally the comment above yours, and in the editorial.