AtCoder Grand Contest 018 will be held on Sunday (time). The writer is maroonrk.

The point values will be 300 — 700 — 800 — 1100 — 1600 — 1700.

Let's discuss problems after the contest.

# | User | Rating |
---|---|---|

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | mnbvmar | 3363 |

4 | Petr | 3330 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3300 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Vn_nV | 3182 |

10 | dotorya | 3156 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 190 |

2 | Errichto | 184 |

3 | rng_58 | 161 |

3 | PikMike | 161 |

5 | Petr | 156 |

6 | Ashishgup | 153 |

6 | Vovuh | 153 |

8 | neal | 151 |

8 | 300iq | 151 |

8 | majk | 151 |

8 | Um_nik | 151 |

AtCoder Grand Contest 018 will be held on Sunday (time). The writer is maroonrk.

The point values will be 300 — 700 — 800 — 1100 — 1600 — 1700.

Let's discuss problems after the contest.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/25/2019 01:23:38 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Will there be a beginner contest as well ?

In AGC's week there's only AGC.

We will hold ABC in the next three weeks.

[reminder] The contest starts in 25 minutes.seriously guys? does this comment deserve so much downvote? I know people are probably annoyed with some other comments, but hating on him is not cool. I feel comments like this helpful as I tend to forget about contest and downvoting it would only make him afraid of commenting. (you don't have to reply to me as you will probably just get downvoted)

is the queue stuck for everyone else as well?

I'm stuck in queue too

Me too. I hope my submission for C will be counted.

PS: It failed T_T

How to solve problem C:Coins?

if there were 2 types instead of 3 , then the solution is just sort according to A[i] — B[i] , take the max X of them as A and the rest Y of them as B

For 3 , sort According to B[i] — C[i] in descending order , now the optimal solution looks like

`BBABAABABABAAB|ACACACACACAACCC`

(a prefix consists of B and A and the suffix C and A) . Among the prefix and suffix , the problem is now for 2 coins .so this can now be done with a segtree.Another solution. Let's choose any distribution. For each two colors, we will put in set most good move from one color to other. While there exists two colors, such that best moves are positive in sum — do this swap. Also, if there is cycle of length 3 of best moves with positive sum — so this cycle. If not — finish, we are best solution.

Correctness can be proven because it is finding MinCostMaxFlow by negative cycles cancellation. But, probably time bound is not obvious. Also, more standard MinCost algorithms can be adopted, to exploit only three colors in similar way.

PS. I think solution described by rajat1603 is much simple.

Can you please elaborate more on its correctness part,I am not able to get that!

Consider the following flow problem.

Each person is a vertex connected by free edge of capacity 1 to source. There are three othere vertex, corresponding to colors, which are connected by free edges to sink, of capacity X,Y,Z corresponding. Also, there is edge of capacity one and cost -A_{i,j} between person and color.

MinCostMaxFlow in this network — is solution to our problem, but it's two slow, so we need to exploit the fact, that there only three colors.

One of the way of solving MinCostMaxFlow is to get any MaxFlow, and then while there is negative cycle — push flow over it. This approach is just finding this cycle fast.

I used a similar solution, but instead of cancelling negative cycles I went for normal MCMF with flow pushing. To decrease the number of cases to consider, I added C[i] to the answer and subtracted C[i] from A[i] and B[i] and ignored the third coin type from now on, so I had only two vertices corresponding to coin types.

I agree the solution by rajat1603 is simpler. On the other hand, it looks like our solution can be adapted and still be fast enough for 4-5 coin types.

First, we think the problem that "there are X+Y+Z pairs(a[i], b[i]), we get X a[i]s and Y b[i]s, maximize sum".

There is upper bound that is "we calc c[i] = max(a[i], b[i]), sort c[i], sum X+Y c[i]s from greater".

We think "we decide offset, calc c[i] = max(a[i], b[i] + offset), sort c[i], sum X+Y c[i]s from greater — offset * (# of use b[i])", it is upper bound of Y = (# of use b[i]).

If offset = -INF, we use X+Y a[i]s. If offset = INF, we use X+Y b[i]s.

So, we can binary search with offset, and check (# of use a[i]) >= X.

Can anyone help me figure out, why this approach is wrong? Code

I sorted elements with

A[i] -B[i], then in the sorted order the firstXelements cannot be part ofAin final solution and also lastYelements cannot be part ofBin final solution.I use similar idea for

A[i] -C[i] andB[i] -C[i]. then I remove all those for whom there is single possibility left. and repeat the entire procedure till I remove all of them.I am not sure about the exact complexity of the program but it seems to be getting finished in time for all cases.

I'm surprised at 400+ AC in problem B. Is it really that easy?

Start with all the events and get the most popular one. Now remove that maximum and repeat until no events are left.

Can you give me an example? I don't really understand what you mean by 'popular'.

I meant the event with the most participants. In sample input 1, 3 people are initially participating in event 2, so we remove that event first.

You can use binary search on answer as well.

It is easy to write check function for it

How to write the check function?

On every step, remove that sports which appears more than

midand ban that sportCODE

Die, ScarletFirebolt.

The trouble happened because of this hacker. We are sorry for inconvenience.

What did he do ?

Submit one-line infinite loop every second. We'll add some submission limit next time...

When will be the queued submissions judged?

After solving A, D, E, F and calculating the score carefully, I submmited.

I felt today's problems are very easy to get wrong for whatever reason.

Jealous xD?

And what is purpose of submitting on last minute? Not participate if you are not good enough today?

Don't you think it's a bit against spirit of competition (totally ok by rules obviously).

tourist style

When tourist does this he is praised by Petr for his creativity, but when Swistakk does this he is accused of being against spirit of competition, I guess that's called "double standards" :D.

On a more serious note, yes, you're right, I agree this is kinda against spirit of competition. However I am not sure whether somebody participates after he clicks "Join AGC XY" or after he makes his first submit and I couldn't find answer in any kind of rules etc, can somebody answer this? In first case, it is completely fine and brings almost no profit, so for the sake of this reply I will assume that second case holds. I think something should be done in system to prevent this kind of thing. Maybe treat user as participant if he opened at least one problem? And moreover, such strategy is connected to some unavoidable risk. If you fail at least two problems you can end up having no time to debug any of them while when following typical strategy you will have more time to debug them and end up having more points. If you fail just last problem and will not be able to debug it in time you will end up with same number of points as when following typical strategy but it will be not big number of points with significantly higher time what will cause a big fall in standings either way. As you can see such strategy is connected to significant risk of failing (look up moejy0viiiiiv's pic and think what would he achieve if he had followed typical strategy), so maybe that's not that bad? My opinion is that it is still kind of cheating but because of what I told significantly less cheaty than it seems :P. And as I told before, something should be done to prevent this. (As a shitty justification for myself, I am currently sick and wanted to compete, but was afraid of getting really poor result)

I'am not Petr so it's probably called "different opinions", not "double standards".

Well, to be honest, I don't really thinks it is something bad. But I always thought, for most people such contest have three main purposes

1) training

2) having fun

3) comparing yourself to other people, you will compete in more official contests, like ICPC.

And i just don't understand what is fun for such strategy, and really thinks that it's making training and comparing worse.

Sirlin explains it best: http://www.sirlin.net/articles/playing-to-win

On the one hand, the strategy is clearly not the way you would want people to compete. On the other hand, the strategy clearly gives the user an advantage. The only reasonable course is to ask AtCoder (and Codeforces, to a lesser extent) to change their contest formats and patch this loophole.

I think having the opportunity to tell someone "haha u jelly bro, this strategy gave me so much win" is totally fun.

http://agc018.contest.atcoder.jp/submissions/1449854

Someone tries to use this code to make judging very slow.

At nearly the end of the contest, I spend 10 minutes to get feedback.

That's too bad.

I solved the 300 after submitting 8 guesses, and I don't know why it worked.

Can someone please explain the solution?

Editorial is available here. (There's always an editorial 1-2 minutes after contest)

Oh, that's nice! Thank you for telling me.

You have very weak test data on A. I've got AC with totally wrong idea... http://agc018.contest.atcoder.jp/submissions/1445462

I really do not understand how this solution is related with the task :D At least that you asked imam[ p[i] — k ] :D

apiad's solution is wrong as well :)

fails on

2 12

6 15

Isn't apiad's username on AtCoder simply apiad xd?

EDIT: I don't get something here xd. AtCoder seems to distinguish user name (mjy something) and user id (apiad). What is the logic behind it? It is confusing.

What the heck? You're checking if k=pi+pj or k=pi and k<=max(pi) o0. Why did you think it is a good idea to submit it if it can't even handle "k=1, p1=2, p2=3" xD? It would be more natural to check if k=pi-pj, I see no logic that can lead one to coming up with such a solution :P. And even more surprisingly, why did it pass xD? It is so incredibly easy to break that with small random cases.

ANIMAL, but trivial mistake your solution could be corrected with bitset Check this for further explanation http://codeforces.com/blog/entry/53168

By the way, problem A uses the same idea as 346A - Alice and Bob.

I was inspired by this problem to set 773F - Test Data Generation for VK Cup 2017 Round 3.

Interesting. Two consecutive AGCs with non-original ideas.

(By saying last round, I'm referring to this task)

[deleted]

[deleted]

[deleted]

Sorry for spamming so many posts. I was not in a good mood recently, and today I was feeling a little bit sick. It was very hot outside and I just got in so I was not feeling pretty comfortable.

Downvoting or Upvoting is up to you. If you don't like my posts or comments, just downvote it. I shouldn't be so emotional. Sorry.

Why do you care about contribution? And how is your "high" rating could be related to that?

Yes,I know that you're much stronger than me (if that makes the sense). But why are you talking about this?

If your posts/comments are getting so many downvotes, it means that community hasn't liked it

You are right. I was pretty irrational just now. Actually I am pretty surprised at what I just said. Sorry.

The idea of problem C is also used in the past more than once. https://www.hackerrank.com/contests/blackrock-codesprint/challenges/audit-sale/problem and http://codeforces.com/contest/730/problem/I (with smaller constraints but some people solved it in a faster way).

Dammit, I could have copied our fast solution from cf problem based on parametric search xD (better known as "trick from aliens") (I didn't solve today's C) (but that wouldn't change my place either way xD)

By the way, speaking about the trick from aliens.

I've tried to apply it yesterday in the TopCoder hard problem. However, I couldn't even make it pass one of the samples. Now it seems to me that it was not applicable at all, because the function "cost if we have K segments" is not a convex function of K. Is that a good criterion for the applicability of the trick? Is there a thread/editorial where I can learn more?

Hah, I and krismaz also independently tried to use this trick yesterday :). And yeah, we didn't give much thought to its correctness, it doesn't work :). Convexity is exactly the condition that is needed. However if convexity is not strict then sometimes additional care needs to be taken if result needs to be restored.

What is "trick from Aliens"?

Some blog which mentions it

Is there a combinatorial interpretation of formulas for problem E?(I mean formulas in the first part of editorial)

Identity we want to prove:

1D version of this identity is well known (as golf club or Christmas stocking identity) and it's combinatorial explanation is that every path going up or right (denoted as U and R) from (0,0) to (a,b) has a unique form (

U+R)^{ * }RU^{ * }(as regular expression). I tried to generalize this idea to 2D and observed that (almost) every such path has unique form (U+R)^{ * }RU^{ + }R^{ * }(and number of such expressions is clearly our LHS). Only path that has no such form isU^{b}R^{a}what stands for this subtracted one.There's an interesting way to interpret the second part of the solution for problem E.

Let's consider Stokes' theorem. It says the integral over a region can be computed as some integral over its boundary.

For problem E, we can think of it as replacing a sum over some grid cells in a region with a sum over its boundary. In fact, this technique seems to work for arbitrary shaped regions, even ones with holes in them.

I'm wondering if there is some way to formalize this connection, or if I'm just imagining things and this is all just a notorious coincidence.

I couldn't get why the author's solution for Problem F (Two trees) meets all the constraints.Could someone explain it to me?Thanks!

Consider an eulerian cycle in the graph described in the editorial.

Each cycle consists of alternating paths in the first tree and second tree with edges joining endpoint of a path of previous tree with startpoint of path of current tree.

Now according to the method described in editorial , for each path , each of the path's nodes subtree sum either increases / decreases by 1 except the LCA of the endpoints.

Now for each node , the only time its subtree sum will change is if a path coming to this continues upward which can happen exactly once(Because each node has exactly one parent edge only)

So this prove that any node which has a path passing from it will have subtree sum as +1 or -1 and since all nodes has a degree of atleast 2 , all nodes will have atleast one path passing from it and hence we are done.