ScarletS's blog

By ScarletS, history, 13 months ago, In English

A — Large Digits

Solution

B — Gentle Pairs

Solution

C — 1-SAT

Solution

D — Choose Me

Solution

E — Through Path

Solution

F — Close Group

Solution
 
 
 
 
  • Vote: I like it
  • +88
  • Vote: I do not like it

»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi can you please provide a proof for your claim? Thanks!

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Just from experience with solving bad problems.

»
13 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Nice post! May I suggest including your runtime at the end of each problem's explanation?

»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

What is your time complexity for problem F? Isn't it $$$3^n$$$?

»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      I'm sorry but what does the value of the xor value s^m mean?

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it -8 Vote: I do not like it

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, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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   Vote: I like it 0 Vote: I do not like it

          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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

I didn't attempt ABC but your graph is inspiring