### ScarletS's blog

By ScarletS, history, 13 months ago,

Solution

Solution

Solution

Solution

Solution

# F — Close Group

Solution

• +88

 » 13 months ago, # |   +3 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.
•  » » 13 months ago, # ^ |   +6 Yes, exactly that's an overkill and somewhat prone to error IMO.. we can simply check for all pairs and count those satisfying |x[i] - x[j]| >= |y[i] - y[j]|
•  » » 13 months ago, # ^ |   +3 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.
•  » » 13 months ago, # ^ |   +10 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$.
•  » » » 13 months ago, # ^ |   0 Hi can you please provide a proof for your claim? Thanks!
•  » » » » 13 months ago, # ^ |   +18 Just from experience with solving bad problems.
 » 13 months ago, # |   +18 Nice post! May I suggest including your runtime at the end of each problem's explanation?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +6 Good idea! I added them now :)
 » 13 months ago, # |   +5 What is your time complexity for problem F? Isn't it $3^n$?
•  » » 13 months ago, # ^ |   +3 Yes. I think that intended is $3^n$.
•  » » 13 months ago, # ^ |   +9
 » 13 months ago, # |   +5 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. linkHowever, I would like to understand how the bitmask thing works. What is the idea, why does these loops give the correct answer?
•  » » 13 months ago, # ^ |   +3 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?
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 I'm sorry but what does the value of the xor value s^m mean?
•  » » » » 13 months ago, # ^ |   0 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.
 » 13 months ago, # | ← Rev. 2 →   -8 May I please ask somebody to explain why does the 2Ai + Bi works for D, while the Ai + Bi doesn't? Thanks!
•  » » 13 months ago, # ^ |   +18 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.
•  » » » 13 months ago, # ^ |   0 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].
•  » » » » 13 months ago, # ^ |   +1 Is there a classic problem with the same idea? 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?
•  » » » » » 13 months ago, # ^ | ← Rev. 3 →   0 I think it might be easier to understand the logic using the following example: A B 2 0 5 5 8 1 If we sort by A + B, we'll get: A B 5 5 8 1 2 0 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: A B 8 1 5 5 2 0 And in this case we'll need to make a speech only in the first town in order to win.
 » 13 months ago, # |   0 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. But only 22/31 test cases are passing, I cannot figure out the mistake in it. It would be helpful if anybody can give his/her views in which my solution is lacking. here is my code link: my solution of D
•  » » 13 months ago, # ^ |   +3 This is explained in literally the comment above yours, and in the editorial.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 Thanks for the great explanation.
•  » » 13 months ago, # ^ |   0 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 ... :(
 » 13 months ago, # |   0 I couldn't understand F , could anyone explain please.i mean what is the dp state if it is a dp related problem
 » 13 months ago, # |   0 I didn't attempt ABC but your graph is inspiring