# A — Large Digits

**Solution**

Calculate the sum of the digits of both integers, and print out the maximum.

Time complexity: $$$O(1)$$$ My solution

# B — Gentle Pairs

**Solution**

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

**Solution**

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

**Solution**

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

**Solution**

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

**Solution**

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

`xor`

value`s^m`

mean?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 + Bi`

works for D, while the`Ai + Bi`

doesn'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

relativechange 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 ofA[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?

I think it might be easier to understand the logic using the following example:

If we sort by

`A + B`

, we'll get:In this situation, in order to win the election, we need to make a speech in the first two towns, which is incorrect.

On the other hand, if we use a relative change, sorting by

`2A + B`

, we'll get:And in this case we'll need to make a speech only in the first town in order to win.

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

literallythe comment above yours, and in the editorial.Thanks for the great explanation.

Yes, I had exactly the same logic and I still don't understand why it doesn't work. The only explanation I have — I am too bad at math ... :(

I couldn't understand F , could anyone explain please.

i mean what is the dp state if it is a dp related problem

I didn't attempt ABC but your graph is inspiring