We will hold AtCoder Beginner Contest 338.
- Contest URL: https://atcoder.jp/contests/abc338
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240127T2100&p1=248
- Duration: 100 minutes
- Writer: evima, yuto1115, tatyam, kyopro_friends, m_99, ynymxiaolongbao
- Tester: kyopro_friends, Nyaan
- Rated range: ~ 1999
- The point values: 100-200-300-425-500-500-600
We are looking forward to your participation!
Hope to make ABCDE!
Me too.
ACed ABCF,but No DEG(
ABCE here, no DFG :(
how did you solve F if you couldn't solve E, xD
E is like even easier than D i think
I spent 10-15 mins trying to solve C thinking it was $$$n \leq 10^6$$$
Hello everyone!I the round gone well.I hope that you all will get positive delta from this contest. Can someone explain me what is wrong in my code for E problem?
https://atcoder.jp/contests/abc338/submissions/49737722
I mean, why that code didn't work? Can someone explain?
The condition
(a[i]%2==0 && b[i]%2==0) || (a[i]%2!=0 && b[i]%2!=0)is necessary but not sufficient.This is a counterexample
What is the output of that?
I think it is "No" Am I Right?
I think the answer is Yes
$$$D > > > > > E$$$
Did anyone manage to cheese $$$2^n \cdot n^3$$$ on F? I got to (32xAC,2xTLE) before realizing the $$$2^n \cdot n^2$$$ optimization and getting AC.
Also E has appeared in a previous ABC/ARC. I can't seem to find the link but the problem involved points on the sides of a square (instead of a circle) and drawing arbitrary curved lines between them (instead of chords) but the solution is identical. Granted, its an educational contest, so it probably doesn't matter too much.
well this worked https://atcoder.jp/contests/abc338/submissions/49743046
yes https://atcoder.jp/contests/abc338/submissions/49737056
I ran the dp 10 iterations (like in bellman) and got ac :)))
i did like $$$2^n ⋅ (n+m)$$$ but with 5 additional iterations so the constant is x5, but it still got AC lol, i can't even prove why it's correct
Maybe it's not, i guess the tests just aren't strong enough
What is the difficulity score of Problem D E F based on codeforces rating system？
1400~1600
Implement what's written in the problem statement.
Implement what's written in the problem statement.
Bruteforce the number of dishes of one of the types.
Calculate for each road the sum of the lengths of the paths $$$(X_k, X_{k + 1})$$$ that will pass through the current road (instead of the other arc of the circle), and the same for the ones that won't pass through the current road. This can be done with prefix sums. After that, try all the roads and calculate the length of the tour using the precalculated values.
For each chord $$$i$$$, check if there is another chord $$$j$$$ satisfying $$$A_i < A_j < B_i < B_j$$$ or $$$A_j < A_i < B_j < B_i$$$. This can be done using a data structure that supports range minimum/maximum queries.
If a walk exists, eventually, all the cities must be visited, in some order. Find an optimal order in which the cities will be visited using bitmask dynamic programming.
The answer to the problem is the minimum of the values $$$dp[2^n - 1][i] + dist[i][j]$$$ over all the valid pairs $$$i, j$$$. $$$dist[i][j]$$$ can be calculated for all pairs $$$i, j$$$ using Floyd–Warshall algorithm.
For each $$$i$$$, calculate two values:
$$$dp_+[i]$$$ the sum of the evaluations of the subarrays starting at $$$i$$$.
$$$dp_*[i]$$$ the sum of the evaluations of the subarrays starting at $$$i$$$ but not containing a '+' character.
The above values can be calculated from the right to the left by maintaining the positions of the last '+' and '*' characters and doing some casework.
The answer to the problem is the sum of all the values $$$dp_+[i]$$$.
You don't need an RMQ data structure for E.
I'm assuming $$$A_i \lt B_i$$$ in the following notation for simplicity. You can just swap them if they aren't, it still represents the same chord.
Keep a stack and process the chord endpoints in order from $$$1$$$ to $$$2n$$$. When you reach $$$A_i$$$, push $$$i$$$ onto the stack. Then when you reach $$$B_i$$$, check if $$$i$$$ is on top of the stack.
If some other value (say $$$j$$$) is on top of the stack it represents a pair of chords with $$$A_i \lt A_j \lt B_i \lt B_j$$$, i.e, chords $$$i$$$ and $$$j$$$ intersect, so it isn't possible. Otherwise no chord intersects $$$i$$$, so we just pop it from the stack and continue.
Submission
Binary Search Solution for C
No offense but I would like it if you could help me figure out what's wrong with my code , if I had to look for a solution I would've read the editorial.
I did not reply to you, did I? just shared a reference for anyone searching.
My solution to problem F is a little bit different from the one in the editorial.
I also use dp[st][i] to denote the minimum weight under the condition that we have visited all the nodes in the bitmask of st, and we are now at the i-th node. Then, we use function numof1(st) to denote the number of 1s in st, and my algorithm works as follows.
Initially, we have dp[st][i]=0, where numof1(st)=1.
Then, suppose that we have got all the values of dp[st][i], where numof1(st)=1,2,...,k-1, and we are going to find dp[st][i], where numof1(st)=k, by using dp[st'][j], where numof1(st')=k-1. For dp[st'][j], we can go to any dp[st][i], if and only if, st=st' | (1<<i), and there is an edge from node-j to node-i.
Next, for any dp[st][i], we find all the nodes involved in st, and update dp[st][i] again, by using Dij algorithm.
Finally, the answer is the minimum one of dp[(1<<n)-1][i].
Hi,everybody,I found a problem in E Here is the Sample Input 3 114 514 512 113 115 513
But Atcoder's Output is No and somebody's AC code'output is No But somebody's AC code'output is Yes and I try drawing a picture,I found that there is an intersection between the chords, Can you help me?
$$$1\le u,v\le 2\times n$$$