We will hold AtCoder Beginner Contest 233.
- Contest URL: https://atcoder.jp/contests/abc233
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20211225T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: physics0523, sugarrr
- Tester: kyopro_friends, math957963
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
This is the last ABC in this year. As a writer, Merry Christmas!
G
crap I solved this problem a few days ago. Too dumb of me that when I solved the F, I didn't read the G because 20 minutes only was left so I said it is impossible for me to get it.
How to solve C without DFS that is given in the editorial?
https://atcoder.jp/contests/abc233/submissions/28122386
You can use the product function from the python standard library https://docs.python.org/3/library/itertools.html#itertools.product
Starting with a product value of 1, keep a map of the existing products so far. Cross-multiplying each new row of input with the existing products. At the end, if X exists in the map, output its value. Beware of multiplication overflow, which costed me a WA: My submission
Edit: Instead of starting with a product value of 1, start with the first row of input.
Actually you should to initialize dp with dp[X] = 1 and then transfer the dp state by division. Otherwise the number of dp state might be large. My implementation Time complexity is roughly $$$O(\sum{L_i}D)$$$, D is the number divisors of X(D won't be very large;using tree map is fine)
Right, but considering this is question C of AtCoder Beginner Contest, usually this is enough. DP is mostly needed only from question D and onwards.
I had a different solution to E that did involve converting to an integer. It's best explained if the input is a 4-digit number with digits $$$a, b, c, d$$$. We see that $$$a$$$'s contribution to the result is $$$a(1000 + 100 + 10 + 1) = a(10^4 - 1)/9$$$. The total result is $$$\frac{1}{9} [a(10^4 - 1) + b(10^3 - 1) + c(10^2 - 1) + d(10-1)] = \frac{1}{9} (10X - (a + b + c + d))$$$, and in general it is
(10X - (sum of digits of X)) / 9
which can be calculated quickly enough in python.Can G be solved using flows?
Problem G: 1198D - Покраска прямоугольника 1
Why was problem H called Ex?
Maybe the writer thought it's extra……
For problem F, can someone please explain a bit more :
if you repeat “choosing an arbitrary edge that is not a bridge and removing it,” then it ultimately becomes a forest without changing the connectivity. You can place the desired piece to each vertex in order, with leaves processed first.
Given any graph G, if you keep removing non-bridge edges from it, you end up with a spanning forest. Basically in that solution, you can pretend that non-forest edges are not present (i.e. you can find a solution that doesn't use those swap operations)
https://atcoder.jp/contests/abc233/submissions/28135244 I am not able to figure out why my submission timed out for E.
I took input as a string, calculated sum till i th digit and stored it in a array, then i computed the digit (sum%10) and carry (sum/10) in reverse order.
If carry is non zero append it to the final answer. can someone help me debug it
is $$$O(|answer|)$$$, so it's $$$O(n^2)$$$ in total .
Thank you, what would be the right way to do it then?
For example you can add symbols to the end of the string and then reverse it afterwards.
Can someone please give me a testcase where my solution for F is failing. Logic — make components and check if i(in p vector) and i(in c vector) are together or not, if not, then return false, else for each pi in the component, find its position and place it at index pi.
I found a testcase for Task F in which someone might take greater number of operations then allowed ( 5 * 105 ).I tested it here.
Test case seems correct to me, Please verify it. If it is correct consider it adding as test case.
What's wrong with this solution for F:
1) Remove extraneous edges such that we end up with a forest.
2) For arbitrary leaf node in the forest, keep swapping until we get it to be in the right place, at which point we remove the sole edge coming out of it.
Can't seem to find a counterexample.
EDIT: Can someone share test data?