chokudai's blog

By chokudai, history, 7 weeks ago, In English,

We will hold AtCoder Beginner Contest 147.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Can anyone please give a solution to F?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    The problem actually asks how many different sums can be got from all subsets.

    Let $$$Y = X - D$$$. Then $$$A_i=Y+iD$$$. We can divide $$$gcd(Y, D)$$$ from $$$Y$$$ and $$$D$$$, now let's assume $$$gcd(Y,D)=1$$$.

    We can maintain n maps. Enumerate how many elements we choose from the sequence, now assume it's k.

    So the sum of elements we picked from sequence should be $$$kY+bD$$$, you can store all the sums possible if we pick k elements into map $$$(k\mod D)$$$.

    If there are different ways to choose elements with the same sum, then they will be stored into same map.

    Now let's consider $$$k$$$-th maps, it stores sum like $$$(k+tD)Y+bD$$$, if we subtract $$$kY$$$ from them, they will be multiple of $$$D$$$.

    Consider all sums picked $$$k$$$ elements, actually the sum should be

    $$$\{kY+Dv|1+\ldots+k\leq v\leq (n-k+1)+\ldots+n\}$$$

    You can subtract $$$(k\mod D)Y$$$ from them, then divide $$$D$$$, you'll find all sums contribute from picked $$$k$$$ elements will be compressed as a continuous interval $$$[l,r]$$$, you can maintain them with map.

    At last, count the total length of all intervals stored in maps. The total time complexity is $$$O(n\log_2n)$$$.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    F:

    Let $$$AP = A + (A + 1\cdot D) + (A + 2\cdot D) + \dots + (A + (N - 1)\cdot D$$$)
    The problem essentially asks to count unique sums of every subset of $$$AP$$$.

    Let's iterate over $$$l$$$, in which we consider subsets of size $$$l$$$.
    For each $$$l$$$, we can find a range $$$[L, R]$$$, such that each sum of subsets of size $$$l$$$, lies in $$$[L, R]$$$.
    It is easy to see that $$$L = A\cdot l + \sum\limits_{i=0}^{l-1}{i\cdot D}$$$
    Similarly, $$$R = A\cdot l + \sum\limits_{i=n-l}^{n-1}{i\cdot D}$$$
    By taking $$$l$$$ leftmost, and $$$l$$$ righmost numbers respectively.
    It can be proven that for each such range, all sums with intervals of $$$D$$$ are possible to obtain, i.e. $$$\left(L, L + D, \dots, R\right)$$$
    Since, there can overlapping of sums in ranges for those $$$l$$$'s for which $$$L \pmod D$$$ are same, we merge such ranges before adding there contribution.
    Also, handle the case for $$$D = 0$$$ separately.

    Link

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, it was a beautiful problem.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Awesome explanation,can I understand your logic It can be proven that for each such range, all sums with intervals of D are possible to obtain,but unable to think of a proof of it.Kindly explain

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the solution for problem C ?

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    The editorial is out! Link

    You can use Google translate for the pdf file

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually no need of translation.The editorials are first explained in Japanese and then below they were explained in English also.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    C. If you decide whether each person is honest or unkind, you can easily check in O (N2) whether the condition is consistent with the testimony. Since there are only 2N ways to determine whether or not each person is honest, it is sufficient to investigate whether or not there is a contradiction in all these cases, and to answer the largest number of honesty before the contradiction occurs. The above shows that an integer j between 0 and 2N is for an integer k between 1 and N, person k is honest and that the k-1 digit is 1 when j is represented in binary. By defining it as equivalent state, you can easily try all cases, this method is called bit traversal.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For me it was not that easy, in fact I did not solve it in time. The check for contradictions looks kind of fiddly to me.

      Somewhere in my loop over (1<<n) I had a line of code like

      if(a[j][k]!=(i&(1<<k)))
          ok=false;
      

      Which does not work, correct is

      if(a[j][k]!=((i>>k)&1))
          ok=false;
      
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Since N is at most 15, the main idea is to generate all 2^15 = 32768 possible combinations of whether one is honest, and test whether there are any contradictions. I did this using bit operations, but of course there are other ways of doing that.

    My submission: https://atcoder.jp/contests/abc147/submissions/8866706

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

D.
An Efficient Solution can solve this problem in O(n*64) or O(n) time. The assumption here is that integers are represented using 64 bits.
Optimized solution will be to try bit manipulation. To implement the solution, we consider all bits which are 1 and which are 0 and store their count in two different variables. Next multiple those counts along with the power of 2 raised to that bit position. Do this for all the bit positions of the numbers. Their sum would be our answer.

Explanation : arr[] = { 7, 3, 5 }
7 = 1 1 1
3 = 0 1 1
5 = 1 0 1
For bit position 0 :
Bits with zero = 0
Bits with one = 3
Answer = 0 * 3 * 2 ^ 0 = 0
Similarly, for bit position 1 :
Bits with zero = 1
Bits with one = 2
Answer = 1 * 2 * 2 ^ 1 = 4
Similarly, for bit position 2 :
Bits with zero = 1
Bits with one = 2
Answer = 1 * 2 * 2 ^ 2 = 8
Final answer = 0 + 4 + 8 = 12

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Isn't it that we need to divide by 2 somewhere?

    The above calculates sum of all pairs, not only the ones where j>i. Or am I wrong?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When you paste the whole explanation from geeksforgeeks !!! the whole solution was available on gfg They should not add such question the contest when the solution is already available on such educational websites

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    here for D solid explanation link

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

geothermal didn't write editorials this time.!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was also waiting for his editorial. His explanation of the problems are best

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

English editorial please.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have a problem with pD?

My answer to sample 3 is 794304820, but I somehow got an AC.

My code

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same problem! Where I was making a mistake was calculating 2^60, I wasn't taking the modulo 1e9+7 during its computation assuming it to fit in a long long.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I had an idea for F but couldn't implement in time : The question reduces to finding distinct values S can take. So I did some manual work for number of terms used to form S, say i, so for each i consecutive distinct values lie at the difference of D(common difference), now we have different intervals for all i, need to combine them. To combine first I sort intervals, standard sorting and include a value called as base value with each interval (which is the minimum offset from zero we get if we keep reducing the minimum value of interval ) and then I partition intervals on basis of offset value into different categories of intervals. Now the question reduces to merging of intervals for each category and finding total elements present in all resultant intervals at gap of d.

»
6 weeks ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

E was a rather standard knapsack DP.

We can find the optimal path with a boolean matrix of size $$$H\times W \times 6400$$$ that has $$$true$$$ on index $$$(i,j,d)$$$ iff it's possible to reach the square $$$(i,j)$$$ while having total absolute (red — blue) difference $$$d$$$.

I'd say the only insight needed here was to notice that you only need $$$6400$$$ states for each square. This is because each path has length $$$H+W-1 < 160$$$, and the maximum $$$\vert A_{i,j} - B_{i,j}\vert$$$ to be added/subtracted in each step is $$$80$$$, so an optimal path will never reach over $$$6400$$$ or below $$$-6400$$$ at any point.

Code

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How could you be sure that difference will never reach 6400?

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I thought of C in terms of bipartite graph.Can someone share if he had similar approach and having AC? Code

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I got a question, comparing both submissions, which are pretty similar, Code1 WA and Code2 AC I know that the first one has indices out of bounds and it might lead to undefined behavior, but it is ok that the verdict is a WA or what else could it be ? I mean I do not get why the code1 is a WA, the only idea I have is regarding undefined behavior but is there any other possibility regarding the WA?

Thank you

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain how to solve E in O(min{H, W}(H + W)M), M being Let M = max{|A11 − B11|, ..., |AHW − BHW |}? The editorial says it can be achieved by using a good order of calculation.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Need explanation for E.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Please post test cases of this contest in DropBox.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is a problem very similar to Problem C with higher constraints, which can be solved using DP.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

include

using namespace std;

int main() { int n;//number of people int a[n]; int t[n];//testinomy result of ith person

for(int i=0;i<n;i++{
    cin>>a[i];
    while(a[i]--){
        int p=0;
        cin>>p;
        cin>>t[p];
    }
}
return 0;

}

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$ E - Balanced Path $$$

Did someone do a top down dp computing the minimum absolute difference of the sum of red numbers and the sum of blue numbers?

I think it has the same time complexity as the editorial but i'm getting TLE.

Code
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any one please explain me Bitmask brute forcing that is used to solve C in details.