We will hold Sciseed Programming Contest 2021（AtCoder Beginner Contest 219）.

- Contest URL: https://atcoder.jp/contests/abc219
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210918T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: Kodaman, kyopro_friends, leaf1415, math957963, Nyaan, physics0523
- Rated range: ~ 1999

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

We are looking forward to your participation!

One of the best educational contests. Thanks atcoder!

What a action packed day tommorow :0

ABC -> CF -> kickstart back to back with around 30 min break in between each of them.

Leetcode Biweekly->Am i a joke to u?

Spoilerso the recent AtCoder rounds have two extra problems than the regular ones we used to, these two problems have 500, 600 difficulty, maybe it worth increasing the contest time a little?

Idk why downvotes, so retracting it!

Hope this contest will bring good luck to me in CSP-S 2021 (1st round) tomorrow :)

P.S. If you don't know what CSP is click here

HardCoder

For me C/D was too hard according to previous :(

Ho to solve D ?

felt really good after solving today's C ...actually the given string can be compared with abcde....z and then normal sort function can be used ... got it after 30 minutes ...but felt really good after solving :D

i did the same xD

convert given string to abcdef--- and again convert from abcdef-- to given string :3

D was dp.

$$$dp[i][j][k]=$$$minimum no. of meals we can buy from first $$$i$$$ meals so that we have at least $$$j$$$ items of first type and $$$k$$$ items of second type.

Transitions:

$$$dp[i][j][k]=min(dp[i-1][j][k],1+dp[i-1][j-a_i][k],1+dp[i-1][j][k-b_i],1+dp[i-1][j-a_i][k-b_i])$$$

Codewhat do transitions mean with fixed k and fixed j?(when we take only one part of lunchbox or something)

It means that we take the $$$i-th$$$ box but count only the items of first or second type.

Hey, can you explain why this discrete dp doesn't work? I mean when ith lunchbox is taken then we will only get a[i] and b[i] (which is discrete). I don't understand why we are doing continuous dp, over here. It would a great help. Thnx.

codeThis gives WA on the test cases added after contest.

Hello, thanks for reminding, it was a small mistake in loop, I corrected it now :)

basically knapsack like dp

D can be solved using Dynamic Programming. Approach: Let dp(i, j, k) be the minimum number of boxes to eat from first i boxes in order to get j octopus balls and k fish-shaped cakes. The transitions will be

. Where x and y are X and Y (given as inputs)

SubmissionRecursion + Memoization

Hi, Could you please tell the significance of min(x,j+a[i]) and min(y,k+b[i]) in your code? I wrote just 1+dp(i-1,j+a[i],k+b[i]) and got WA / RE etc. How does it affect the logic?

Hello!

See the constraints given in the problem. It's N <= 300 and Ai, Bi <= 300 which means

`(j + a[i])`

and / or`(k + b[i])`

can go upto 300 * 300 which results in RE(due to out of bounds). But, think what happens when`(j + a[i])`

or`(k + b[i])`

becomes`>= x`

or`y`

? Whenever`(j + a[i])`

becomes`>= x`

, we have achieved the goal of getting`>= x`

octopus balls given in the problem. So, we can consider all values`(j + a[i]) >= x`

as`x`

(this is done to avoid Runtime Errors) since we just need to get any number of balls`>= x`

and so we don't care if we have got`> x`

balls or`= x`

balls. The same applies to`(k + b[i])`

too. Hence, the reason I take`min(x, j + a[i])`

instead of`(j + a[i])`

is to make sure that this parameter never exceeds x.P.S: It took me 5 incorrect submissions to find this!

I see I see I understand it now! Thank you! Whoa 5 attempts, looks like a very important optimization!

I solved Problem D using dp.

The implemention of E and F was so painful (at least for me) !!!!!

How did you solve F? Can you share?

Can someone share a neat implemeantaion of pE?

Sure!

Here is my code for solving problem E.

Feel free to ask if there's any unclear part to my code.

Here is the clean code for E, I have added comments for better understanding Code

For me the gap from D to E was big. Solved A-D in like 30 minutes, than did not found any clear idea for E or F.

How to solve G — Propagation?

Similar to brute force approach. The bottleneck of the brute force approach is when

`x`

has a lot of neighbours, updating all the neightbours will take long. So we need to deal with these type of nodes separately.Call a node

`x`

`big`

if the number of it's neighbours is >=`sqrt(2e5)`

. There are very few nodes of this type. So, the idea is to maintain an array of pairs`last_propagation`

for the`big`

nodes. If`qi`

is the last query when a big node`b`

appeared as a query, then`last_propagation[b]`

will be equal to`(value of node b at that the time of the query, qi)`

.We also always keep the values of these

`big`

nodes updated as we process each of the queries sequentially. But we're fine if the values of the small nodes are not always kept updated, since it won't take long to get their latest value using the`last_propagation`

array.Then, to process the queries, consider two cases:

If

`x`

is`big`

, update it's`last_propagation`

and also update it's`big`

neighbours' values.If

`x`

is`small`

, get it's latest value and then update all it's neighbours the brute force way.Here's my submission using this idea. Let me know if I need to clarify anything above.

DELETED

how tf solve A? I have 1 WA and can't get what's wrong...

Maybe you missed "If, however, his rank was Expert, print "expert", ..."

I did, for one penalty.

Tell me that you are joking.If not share your submission link

You printed "expert" for n = 100

But if n >= 90 then answer is "expert"

try writing expert in lowercase. atcoder is case sensitive

you better write atcoder not atocoder

okey guys, that's really funny, switch on C button is laggy on my keyboard, so I've sent the same wrong code twice))))))))))

Why does this not work for G? (35x AC, 2x WA)

Split nodes into "light" (degree $$$\lt \sqrt{m}$$$) and "heavy" (degree $$$\geq \sqrt{m}$$$).

For each node we additionally keep track of all adjacent heavy nodes.

For light nodes, we directly push the result of a query to all of its neighbors after a query.

Additionally for all nodes (heavy or light), when we have a query, we will check for any newer values from heavy neighbors.

Remember to perform a heavy neighbour pull at the end for all nodes before printing the answer.

This takes a total of $$$O(m + (n + q) \sqrt m)$$$ since there can be at most $$$\sqrt{m}$$$ heavy nodes in the graph by definition.

CodeThat's what I did, and it passed (code).

Oops, must be an implementation mistake somewhere then. Thanks for the info.

I am same to you, my code 35*ac ,2*wa ...

The heavy node value might be overwritten later on, thus you need to store the value, too.

tks, i fixed it,and get ac..

Thank you, how do you know when to do heavy-light splitting? I'm having trouble identifying this type of problem

lol i hate geometry problems

I need to go debug my E. My basic idea was to represent the board as a bitmask try all 2^16 bitmasks and check a) Do i cover the required cells? b) Are the cells i have connected? (used DSU) c) Does my polygon have any holes? (used DSU) d) Do i have any self intersections (i.e. corners where one pair of opposite diagonals are included and the other pair where there are not)? However, even on the sample, I'm coming up short on the count, so I'm overkilling boards somewhere.

You don't have to use DSU for checking holes. You can simply do a bfs starting from an edge square that is empty and check if you can visit all empty squares without leaving any behind

Can you please share your code?

What do you mean by "self intersections", I did the following in my AC code:

A mask is considered good iff:

CodeThanks. I must have a bug in my connected checker, as I agree that the self intersections check SHOULD not be necessary. I agree on the "hole-check" piece with you. I guess I'll go use it to discover my bug elsewhere, as it shouldn't be flagging anything.

Finally found the bug: i<15 vs. i<16 in for loop termination condition. Painful :(.

Attatching GO code here:

CodeGod save me from tasks like this E. Only you and its author know which moat is considered correct.

Kudos to the author of E for giving us such a painful experience of implementation hell ! xD!!

Can someone help me with D) . I used knapsack . why is it wrong ?

My Codevector< vector > dp(n + 1, vector((x + 1)*(y + 1), mod));

The sum of the number of snacks can exceed 300.

i have 300*300 = 90000 states as columns (all possible pairs of (x, y)) that's why i initialised dp as

`dp(n, vector<long long>((x + 1) *(y + 1)))`

So i have covered all states right ?

Nope, check this test case:

2 300 300 250 250 300 100

Here, we would need a state to represent (550, 350), which is not covered in your code.

okay thanks a lot :)

How to solve D, I got the easy $$$O(n^{4})$$$ dp, optimized it like hell for it to pass. What was the $$$O(n^{3})$$$ idea?

Just have a state that represents >300 for each snack instead of trying to use the actual values. So in total there should be $$$O(n^2)$$$ states which should result in $$$O(n^3)$$$ solution

dp[i][j][k] = most taiyaki I can get after taking j of first i boxes and having k takoyaki. i did forward DP, but either need to be careful on order to avoid double counting or push updates to a queue-stack and do them at the end.

yaa this is exactly what I also did, need to be careful with optimization.

What a joke.solve a and b less than 5min. Then just WA-WA-WA-WA

Please someone explain why this comparator doesn't work? for C.

If one of the strings is a prefix of the other one you return false. But that should be true or false, depending on which string is shorter.

Sir,can you give me an example plz?

for input:

My output:

The comparison function needs to return true if the first string is lex smaller than the second. So it returns the wrong value if the first string is a prefix of the second. Because then the first one is lex smaller, but the return value is false. But should be true.

I used this as a comparator in the sort function, preety similar to yours

SolutionThis is my code for problem D, can somebody give me a counter test for this code? I got 40/50 test passed at atcoder.

CodeThis is the first time I didn't solve C. Can someone tell me what is wrong with my implementation? I have written it 12 min after the competition has started and didn't find wrong test till the end of the contest, but I have only 2 AC https://atcoder.jp/contests/abc219/submissions/25932882

Did you find out what's wrong?

I am having similar issue, here's my implementation

problem D — can anyone guide me where my logic getting wrong? top-down implementation

SpoilerHere is my top-down implementation, you can go through it.

I understood top-down but I am curious to know where my logic is getting wrong.

You should memorize x and y also because the same value of n can give different answers due to different values of x and y.Then your answer will be dp[n][x][y].

I immediately related to Xenia and tree the moment I read problem G. Kudos to the authors for a really educative problem.

How to solve Problem G?

I feel like E is a little easier than D, because I think D is related to DP while E is related to brute-force.

After some observations, you can figure out the solution to E, but for a beginner coder like me, I just couldn't figure out a way to solve D.

Even though I didn't solve E in time, I still feel happy that it's at least solved in the end.

Here's my video during the contest.

Pretty boring, expected better from an ABC round :/

Alternate solution to $$$G$$$: We keep a bucket of size $$$\leq \sqrt{M}$$$ that stores {vertex, update_value} pairs that we haven't updated in the graph yet. When the size of this bucket becomes $$$\sqrt{M}$$$, then we iterate through every element in it and update the whole graph correspondingly. When we add a new vertex to the bucket, then search through each element in the bucket and find its updated value based on that. Total time complexity should be $$$O(N + Q\sqrt{M})$$$ or something, but my code is still TLEing on some cases. Is it because of using ordered_set?

Can someone please explain E a bit more, I have watched many sybmissions but not getting it