We will hold UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312).
- Contest URL: https://atcoder.jp/contests/abc312
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230729T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: cn449, kyopro_friends, chokudai, evima, Nyaan
- Tester: MMNMM, leaf1415
- Rated range: ~ 1999
- The point values will be 100-200-300-400-500-500-550-600.
We are looking forward to your participation!
Wish this contest will be great!
Finally AtCoder added a link to the discussion area on the homepage of ABC!
Let's work hard , get a great mark together !
Is atcoder begineer contest c,d is more easier than b? is it right? Most of the time b implementation is heavy for me.
Atcoder abc contest: b,c,d is how much rating simillar than a codeforces problem?
Generally, you don't have to prove anything in B since most of the time you can just brute force it.
B C D were all <= 1400 rated. F was <= 1600. I couldn't solve E and G.
bro did you solved problem D?
Yeah. It was simple DP.
yes,here is the code,
using pretty much the same code but getting TLE , Why?
Just pass the string by reference :)
G was easy to be honest , I forgot to consider the case of all triplets in a subtree of a particular node, but after I implemented time got over :(
The solution is to consider the count of nodes above a node X and the number of nodes in the subtree of each child of X.
We can form a triplet in two ways :
1st way : take all the nodes above node X and you can pair it with any two nodes which can be choosen from the subtree of X's children nodes.
2nd way : take all the triplets among X's children nodes' subtree
Suppose z = count of nodes above X.
z can be calculated as n-sub(X) , sub means subtree size of node X
lets say a1, a2 , a3,...., am are the children of node X. We need to calculate the all pair product sum of the subtree sums of a1, a2 , a3,....,am.
Then ans1 = z*(all pair product sum of (sub(a1),sub(a2),sub(a3),....,sub(am))
ans2 = (all triplet product sum of (sub(a1),sub(a2),sub(a3),....,sub(am))
I forgot ans2 case during contest
Final ans is ans1+ans2 , and we will consider all the nodes of the tree as X , tree rooted at 1.
My implementation : code
Just $$$C(n,3)-(\sum_{i,j}dis_{i,j}-C(n,2))$$$. It's a classic problem.
can you please clarify how you simplified it?
$$$i<j<k$$$ means $$$i,j,k$$$ just need to count once, so it equals to count i in the simple path of j,k. So it can be simplified.
Useful learning stuff.
anyone solved problem D with Dp??
here is the formatted code,
Can someone point out what's wrong in this solution of F.It gives WA on 1 testcase.
In my solution i got WA on 3 testcases can anyone tell my mistake code
I'v passed A, B, C and G.
how to approach G,i did D in place of G.
you can find the number of tuples of integers $$$(i,j,k)$$$ such that $$$i<j<k<n$$$ and the given tree does contain a simple path that contains all of vertices $$$i,j$$$ and $$$k$$$. the answer is $$$\sum_{i=1}^n \sum_{j=i+1}^n (dis(i, j) - 1)$$$. This is a typical problem.
okkk gawt ittt
This would still require knowledge of rerooting dp, it can be done much simpler iterating over all possible $$$j$$$'s.
Submission
but actually you don't need dp. the problem can be changed into 'how many times an edge will be passed.'
submission
really hard problem e
cleaner solution to B: Let us observe the coordinates of
#and.in the grid.We can see, in respect to the upper left corner, the red lines are $$$x=3$$$ and $$$y=3$$$, and the blue lines are $$$x=5$$$ and $$$y=5$$$. Then, the area with
.are $$$\max(x,y)=3$$$ and $$$\min(x,y)=5$$$ respectively. Then, the area with#become $$$\max(x,y)<3$$$ and $$$\min(x,y)>5$$$. You can use these directly to get AC.AC submission
chokudai cn449 problem F, I got it accepted after the context, the statement doesn't mention I can take a regular cans without opening it with a can opener.
If Ti=1, the i-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of Xi.so if I wasn't able to open it I assumed I can't take it, and there's no where in the statement mentioned that I can take it with zero happienes.How to do E ;-;
Can anyone check, whats wrong in this solution for problem F
The key part of Ex is similar to CF1732D1
Could someone tell me why did the total number of tuples in G was n*(n-1)*(n-2)/6 ? Why should the number /6 ?
Nobody? Fine……
$$$n \choose 3$$$. also because of the $$$i < j < k$$$ constraint
Oh,that's right.Thank you very much.
For problem C, after watching the official video editorial, I am surprised to see a solution which doesn't use binary search and doesn't use pairs.: Submission
is D possible to solve without dp?
I used a map to solve D. Submission
Does there exist a faster solution to problem D?