We will hold AtCoder Beginner Contest 152.
- Contest URL: https://atcoder.jp/contests/abc152
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200119T2050&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: latte0119, beet, DEGwer, Drafear, HIR180, kyopro_friends, EnumerativeCombinatorics, yokozuna57
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
Note — Contest starts 10 mins before the usual time.
Hope that there is no question which is available on any other platform. PS:- F of last contest :(
How to do F?
Commentary:
In F why does dp with bitmask fail? For each edge, I had a mask that represented that if, I painted this edge black then which constraints will be satisfied due to it.
Now just a dp(edgeNumber, mask).
Sounds like it would work. Maybe you have some implementation error.
It works,My submission.
For E LCM can be calculated with idea product of two numbers=gcd * lcm. for large number we can take modulus
I don't think it works: $$$gcd(a, b)$$$ is not necessarily congruent modulo $$$M$$$ to $$$gcd(a\bmod{M}, b \bmod{M})$$$.
Can anyone share the implementation of E.I am not able to implement E.
why it is -1^r in problem can you plz clear it saketh
It's a general technique known as Principle of Inclusion-Exclusion: [1] [2].
In F , I have done Meet in the middle and then SOS-DP (https://atcoder.jp/contests/abc152/submissions/13014638)
why am i getting WA in some cases in E? lcm(a1,a2,a3...an)*(1/a1+1/a2+1/a3+....+1/an) was the ans right?
Thats beacuse of overflow while calculating lcm(a1,a2,...,an).
Why does this python code -> Link fails?
How to deal with large numbers in E ?
the idea is to factorize the numbers, you can come up with a formula for finding LCM(a_1, a_2, ..., a_n) from their prime representations.
Python can solve this trivially. Code
Can someone explain why this gets Runtime Error: https://atcoder.jp/contests/abc152/submissions/13704002
Nevermind. I got it. There is no math.gcd in older versions of Python: https://atcoder.jp/contests/abc152/submissions/13704661
Can someone explain why this gets Runtime Error: https://atcoder.jp/contests/abc152/submissions/13704002
Explain D please
Define f(a,b) as number of integers less than or equal to n such that the first digit is a and the last digit is b. Observe that the solution is f(a,b)*f(b,a) over all possibilities. there are 81 possibilities (as leading 0's are not allowed) like so)
English editorial has been uploaded.
why no code in D, E, and F?
Unfortunately usually there are no sample code attached for the latter problems. You can see any submissions here anyway. (You can use filter in order to show only AC codes for a specific problems, and even filter by the programming languages.)
can we see others solution after contest in atcoder?
Yes,After the contest go to Results tab then All Submissions.
I did not get how to solve D, can someone explain?
First, fix an integer $$$A$$$ where $$$1 \leq A \leq N$$$. Assume that the first digit of $$$A$$$ is $$$i$$$ and the last digit is $$$j$$$. How many $$$B$$$s are there that satisfies the given condition? The necessary and sufficient condition is that the first digit of $$$B$$$ is $$$j$$$ and the last digit is $$$i$$$. So, in order to count them, you can iterate the integers from $$$1$$$ to $$$N$$$, and check whether each of them satisfies the conditions written above or not.
Then what to do next? Since $$$N$$$ can be up to $$$2 \times 10^5$$$, the total loops can be up to $$$4 \times 10^10$$$, so it won't finish in time. This means that you are wasting time for something, typically doing the same calculation over and over again. Now focus on this step mentioned above:
Instead of performing the step for every $$$A$$$, you can count "the number of integers such that the first digit is $$$j$$$ and the last digit is $$$i$$$" (Let this number be $$$c_{ji}$$$ by looping through from $$$1$$$ to $$$N$$$ only once. So, you could solve this problem.
For F is O(n*m*2^m) under TL?
https://atcoder.jp/contests/abc152/submissions/9614620
or i am not considering complexity correctly?
m<=min(20,n*(n-1)/2)
so if n==50, m could be as large as 50*(50-1)/2=1225. It's hard to imagine that n*m*2^m could be under TL...
but since you got AC, the m in testcases should be much smaller than the problem stated.
ok, since there are only n-1 edges and constraints combination results in edges combination, the distinct number of results of constraints combinations is bounded to the number of edges combinations, which is 2^(n-1). But 2^(n-1) still looks very large.
ok, got it, m <= min(20,n*(n-1)/2) which means m<=20...
Actually it could be O(n*m+2^m).
First, precompute all edges for each constraint and save as bitmask. (n<=50, so it's doable). This part is O(n*m).
Then enumerate constraint combinations. Through the way just do bitmask or operation. With each combinations mask, __builtin_popcountll(...) could be used to figure out how much 1s in the long long mask, which let me get rid of O(n) loop, and it's said to be O(1). This part is O(2^m) in total.
My submission if you interested
for F did anyone understand the tutorial's solution?
Also if i have a tree with nodes <= 10^5 and some M paths how can i know the total number of edges covered?
O_E what u didn't get in editorial?i don't think it can be solved for large constraints
i didn't understand how it uses LCA and cumulative sums
I'll try my best to explain it.
suppose you want to all edges b/w u-->v
so path will be like u---->lca(u,v)----->v.
in this way determine number of all paths which are white.
You can use LCA since any path from u to v can be decomposed into a path from u to
lca(u,v)
and another path from v tolca(u,v)
which makes our lives easier when we use prefix sums.Using prefix sums is similar to updating a range in array [l,r] when you
arr[l]++ and arr[r+1]--
in this way the prefix sum of every index equals to the number of update ranges that hasstart<= index and end >=index
, similarly when it comes to trees, if you want to say that the path from u to v (where u is an ancestor of v) is used, you can doarr[u]-- , arr[v]++
, and then for each node letarr[node]
= summation of all values of its subtree, if arr[node] is positive, this means the edgeparent[node]
to the node is used because this can happen if there is at least one path that start in one of the subtree's nodes and end in an ancestor of that node.You can check my submission if it's not clear.
It's a nice solution thank you ya zeyad
can someone explain atcoder beginner 152 problem c? https://atcoder.jp/contests/abc152/tasks/abc152_c
because according to question it is given as P[i]<=P[j], but in Sample Input1 it is P[j]>P[i]. Please correct me if I understood the question wrong?
My submission link: https://atcoder.jp/contests/abc152/submissions/12066847
I believe you had misunderstood the condition part, for any integer j(1<=j<=i), Pi<=Pj. Any integer here means that all the integers j in the range[1,i] that satisfy the condition, you should edit code as below, but it actually runs TLE:
You should solve it using min as the editorial shows. Notice that if the all the previous elements Pj>=Pi, Pi is the minimum value for the array from position 1 to position i. We just check how many i s satisfy this condition.
Can someone explain why this gets Compilation error ? Link
it run with my IDE but in atcoder website gets compilation error