chokudai's blog

AtCoder Beginner Contest 233 Announcement
By chokudai, history, 3 years ago, In English

We will hold AtCoder Beginner Contest 233.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

  • Vote: I like it
  • +78
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

This is the last ABC in this year. As a writer, Merry Christmas!

→ Reply
»
3 years ago, # |
  Vote: I like it +45 Vote: I do not like it

G

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C without DFS that is given in the editorial?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can G be solved using flows?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G: 1198D - Rectangle Painting 1

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Why was problem H called Ex?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Maybe the writer thought it's extra……

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    answer=to_string(sumarr[i-1]%10)+answer;

    is $$$O(|answer|)$$$, so it's $$$O(n^2)$$$ in total .

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

Code
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

I found a testcase for Task F in which someone might take greater number of operations then allowed ( 5 * 105 ).I tested it here.

Testcase Generator

Test case seems correct to me, Please verify it. If it is correct consider it adding as test case.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply