AtCoder Beginner Contest 105 Discussion Page

6 лет назад, # |

← Rev. 3 →

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

No because we use mod operation.

→ Ответить

leloy

6 лет назад, # ^ |

or simply use map

→ Ответить

Oumae_Kumiko

6 лет назад, # ^ |

+16

std::map is a kind of Red-black tree.

→ Ответить

f2lk6wf90d

6 лет назад, # ^ |

We don't need map though, just sorting. We can just sort f and for every group g of consecutive equal elements, add $\text{[math]}$ to the answer.

→ Ответить

6 лет назад, # |

← Rev. 3 →

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 лет назад, # |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

-10

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

→ Ответить

sharmajatin741

6 лет назад, # ^ |

but statement translated by google translate for problem A is incorrect

→ Ответить

xuanquang1999

6 лет назад, # |

← Rev. 2 →

+10

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

→ Ответить

wakax365

6 лет назад, # ^ |

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

→ Ответить

Oumae_Kumiko

6 лет назад, # |

← Rev. 2 →

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(N2^N / 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 лет назад, # ^ |

Also you can with this method

→ Ответить

Oumae_Kumiko

6 лет назад, # ^ |

← Rev. 4 →

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.

→ Ответить

parth_15

6 лет назад, # ^ |

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 лет назад, # |

← Rev. 15 →

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 2^k = 2^k + 1 - 2^k

When k is an odd number, the one bit 2^k in a Base 2 number N corresponds to one bit in Base -2 System - 2^k by adding 2^k + 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 лет назад, # |

← Rev. 19 →

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

Candy Distribution

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

s_r ≠ 0 and s_l = s_r, where l ≠ r; or
s_r = 0 and either l = 1 or s_l = 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 $\text{[math]}$

If s = 0, then $\text{[math]}$

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

→ Ответить

starboy_jb

6 лет назад, # |

is It late in rating update?

→ Ответить

I-Owe-You-So-Much

6 лет назад, # ^ |

it's unrated !!

→ Ответить

starboy_jb

6 лет назад, # ^ |

← Rev. 2 →

ok, thanks.

it could be rated.

→ Ответить

chinese

6 лет назад, # |

-24

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

→ Ответить

Damocles

6 лет назад, # |

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 лет назад, # ^ |

← Rev. 3 →

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.

→ Ответить

Damocles

6 лет назад, # ^ |

Thank you so much. It really works. ;)

→ Ответить