Блог пользователя ScarletS

Автор ScarletS, история, 3 года назад, По-английски

A — Large Digits

Solution

B — Gentle Pairs

Solution

C — 1-SAT

Solution

D — Choose Me

Solution

E — Through Path

Solution

F — Close Group

Solution
  • Проголосовать: нравится
  • +88
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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]| 
    
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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$$$.

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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. link

However, I would like to understand how the bitmask thing works. What is the idea, why does these loops give the correct answer?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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?

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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.

»
3 года назад, # |
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!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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].

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +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?

»
3 года назад, # |
  Проголосовать: нравится 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