When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

E869120's blog

By E869120, history, 6 years ago, In English

AtCoder Beginner Contest 105 is ongoing now, from August 11, 2018, 21:00 JST.

The writers are DEGwer, Drafear, square1001 and me.
The point values are: 100 — 200 — 300 — 400.

This contest will be unrated because of problems in English statement. At first, there is no English statement in problem A. 6 minutes after starting the contest, the English statement appeared, but it was too late. Sorry for inconvenience.

After the contest, let's discuss the problem.
Thank you for your participation.

UPDATE

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

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by E869120 (previous revision, new revision, compare).

»
6 years ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

We (E869120 and I) made problem B "Cakes and Donuts". The other problems were made by other writers. We maybe publish the English editorial of B (unofficial one, we can maybe translate the other one) in codeforces comment tomorrow, but it is strongly encouraged to discuss about the problems in the round (even before the unofficial editorial publishing).

UPD: We're sorry that we cannot create English editorial today, and it will be published tomorrow. The main reason was, during the contest, we were on trip to somewhere (which were no Wi-Fi, and we actually used tethering). But since the contest was unrated, we had to do too many actions on the Internet and used more than half of this months' cellular network (?) contract. Now uploaded! (Aug. 13th, 2018)

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

    I hope that Atcoder has its own page for discussion...

»
6 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

Here is my Editorial of D in English. Lets denote f(i) equal to sum of elements aj where j is between 1... i. More formally . As problem says we need to find such l and r that . We can transfer f(l) into right side, then our equation will be . We can easily find it with Red Black Tree. As you see, our time complexity will be O(NlogN).

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

    Can we solve D with two pointers after calculation of f?

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

      No because we use mod operation.

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

    or simply use map

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

    We don't need map though, just sorting. We can just sort f and for every group g of consecutive equal elements, add to the answer.

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

In problem B, you can just simply calculate with 2 loops. Or you can solve it with Bézout's identity. More detailed you can read there.

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

Are statement was in Japan language only ? I used google translate.

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

    English statements added later. That's why contest unrated.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      I think it's not big problem because we have google translate and also many people used it :)

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

        but statement translated by google translate for problem A is incorrect

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

When will the next regular contest be held? It is already one month since the last regular contest on AtCoder.

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

    Considering this comment, ARC/AGC is likely to be held two weeks later, at the earliest.

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

As a Brute-force search for problem C, there is a solution by meet in the middle. For example, we have all the values for whether the even bit (0, 2, ..., 30) is set (in -2 binary) or not, and do the same thing with odd bit (1, 3, ..., 31) , then find a pair that will become n together. With N = 32, the time complexity is O(N2N / 2). Of course, it would be nice if you could implement a smart solution like the assumed solution, but such a steady solution is sometimes useful.

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

    Also you can with this method

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

      I mean, I understand problem C can be solved in O(logN). But we can not always come up with such a solution, and In many cases div2 and ABC are asked about the implementation capability of brute force search.(like yesterday CF div2 B,C) In addition, since the range of solvable problems for you is broadened by using various solutions to one problem, I presented a solution by meet in the middle.

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

    How do you prove that the number will fit in 30 bits? As there is negative base, we can't assume that it will fit in log(n) bits?

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

The following is my C++14 iterative O(logN) solution of problem C.

Base -2 Number System

The solution is based on the simple equation 2k = 2k + 1 - 2k

When k is an odd number, the one bit 2k in a Base 2 number N corresponds to one bit in Base -2 System  - 2k by adding 2k + 1 to N. Using the bitwise shift right operator iteratively after pushing the least significant bit of N to a bit stack, the previous equation corresponds to incrementing N by 1 after shifting it to the right 1 bit when k is an odd number. The loops stops when N = 0, and the requested string is printed to the standard output by popping the bits from the stack.

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

The following is my C++14 map-based solution of problem D.

Candy Distribution

Let si, where 0 ≤ si ≤ M - 1, be the cumulative sum of Ai modulo M. The condition that the summation of Ai in the index interval [l, r], where 1 ≤ l ≤ r ≤ N, should be a multiple of M is equivalent to the condition that either

  1. sr ≠ 0 and sl = sr, where l ≠ r; or
  2. sr = 0 and either l = 1 or sl = 0

Let the number of elements in A for each cumulative sum s be g(s), which can be computed using a count map data structure. The number of intervals [l, r] associated with s whose summation is a multiple of M can be computed as follows.

If s ≠ 0, then

If s = 0, then

Summing count(s) over all existing values of s in the count map produces the required answer.

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

is It late in rating update?

»
6 years ago, # |
  Vote: I like it -24 Vote: I do not like it

The task C is just a copy of the problem F from this contest. D is very similiar to this one

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

Concerning problem "D — Candy Distribution", I used binomial coefficient template accidentally and found it couldn't get through all tests case except "0_min1" case. Forgive me that I was so stupid to calculate C(n, 2) with a template. I really want to know if the method is right to calculate binomial coefficient.

// Returns value of Binomial Coefficient C(n, k)
ll binomialCoeff(int n, int k)
{
	ll res = 1;
 
	// Since C(n, k) = C(n, n-k)
	if ( k > n - k )
		k = n - k;
 
	// Calculate value of [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
	for (int i = 0; i < k; ++i)
	{
		res *= ll(n - i);
		res /= ll(i + 1);
	}
 
	return res;
}

And this is my contest code for problem D: https://pastebin.ubuntu.com/p/F88GgY26Vq/

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

    Yes, it is right except for the case when k > n. Your present implementation returns 1 in this case, but the correct value is 0.

    You should add the following lines at the beginning of the function

    if( k > n )
       return 0;
    

    This should fix the problem.

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

I missed this contest unfortunately. If I had known it was conducted by my favourite problem setting twins E869120 and square1001 I would have tried to participate.

I upsolved it now and found it a bit on the easier side.

I have written an editorial for D here because there was no English editorial available and it might be helpful for some people.

P.S. — I liked the mathematical solution to Problem B a lot. And Problem C was also quite elegant :)

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

Auto comment: topic has been updated by E869120 (previous revision, new revision, compare).

»
6 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

We've finally wrote the English editorial! We (E869120 and I) only wrote the problem B, but we were able to write English editorial for all problems in less than 100 minutes. The editorial can be seen from the link at the blog statement.
We believe that we wrote detailed one, and for problem C and D, the editorial could be detailed than the official Japanese one! Let's enjoy!
Last but not least, the contest was unrated, and as organizers, we felt some duty of compensating the incident. We actually checked whether the English problem statement of B is uploaded, but if we checked that for all problem, we could have avoided the unrated. That's one of the reason we wrote English editorial.
- E869120, square1001

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can any one explain problem c ?