Binary search is for monotonic functions. Ternary search is for unimodal functions. It must be strict unimodal else the search will halt as soon as it finds a plateau (0 slope). Note every strictly monotonic function is a degenerate unimodal function (with no left or right tail) so ternary search will work when binary search does as long as the monotonicity is strict. Here is some code: https://codeforces.me/blog/entry/43440

Notice the logic for determining which side to recurse on is really a difference quotient, a discrete derivative, slope etc.

https://en.wikipedia.org/wiki/Linear_programming

I just used brute force. Try all possible subset of rows using bitmasks. The constraints imply this will fit within time.

Overflow prob in mod. Was getting same bug until I switched to long longs.

Why is the recursive implementation of segtrees more favorable than the non-recursive? There is an article on here Efficient and easy segment trees that describes an elegant non-recursive implementation. Which should I use for my library?

It works now thanks. Damn I was pulling my hair out last 5 minutes trying to debug this thing!

F

I just assumed the function was unimodal and tried ternary search and it almost AC'd. Can you elaborate your solution?

EDIT: unimodal not monotonic

Why is my ternary search failing on one test case for D? :((

https://atcoder.jp/contests/abc165/submissions/12647186

RIP

Ah, the beautiful Central Limit Theorem at work.

If there are at most 50 nodes then the the longest shortest path from vertex 1 (source) to any other vertex can be at most 49. If the weight is at most 50 then the total number of silver coins is 49 * 50 = 2450.

The complexity is given by the running time for Djikstra's using an adj. list representation of a graph. More here: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time

How to solve D-F?

Can you link me your submission?

Naive will fail yes. It's a simple combinatorics/counting question: Instead of asking how many ways there are to find the triplets, ask how many there ways there AREN'T triplets and subtract this number from the total possible set of triplets.

The total set is $$$\binom{n}{3}$$$ ways since we are just choosing 3 indices from a set of n chars. Then subtract from the total all the ways to make 3 in a row reds, green, and blues which is $$$\binom{nR}{3}$$$ + $$$\binom{nG}{3}$$$ + $$$\binom{nB}{3}$$$. Then subtract the ways to make a double which is $$$\binom{nR}{2}(nG + nB)$$$ ie the ways of selecting two of the same color, and multiply it with any other color. DO this for the other two colors. Then finally we can do a simple nested loop in $$$O(n^2)$$$ time to determine which triples have same width, but we have to make sure that none of these triples have the same color because we already subtracted those (principle of inclusion exclusion).

I solved problem D in last 2 minutes. Spent almost 1 hour debugging it and found there was an overflow error in my $$$nC2$$$ and $$$nC3$$$ functions. I got huge rush when I saw AC on it!! Wonderful questions!!

https://atcoder.jp/contests/abc162/submissions/11854513

Really nice man

it better be virus themed questions

oohhh wow

I understand the sum of the first $$$k$$$ odds is $$$k^2$$$ but I've been staring at this equation $$$(k * (k+1) + k * (k-1))/2$$$ on paper for 30 minutes and I don't understand what it means. I'm just curious, can you elaborate (without reducing it using algebra). All I see is the formula for arithmetic sum and $$$\binom n2$$$.

I love this influx of ABCs from AtCoder! Thank you!!

Like this: https://atcoder.jp/contests/abc156/submissions/10289777

related: https://www.geeksforgeeks.org/space-and-time-efficient-binomial-coefficient/

This is a beautiful solution thank you. However, I can't seem to understand why the pos and neg arrays need to be reversed when solving negative case. The way I see it is if you keep neg array non-decreasing and make pos array decreasing, then the product should be non-decreasing as well so it shouldn't affect the total count. So I removed the line where the negative array is reversed and got WA on about 1/3 of the tests.

EDIT: Nvm, I read a bit more about the two-pointers. Reversing the arrays is the correct way to make the two-pointer loop work.

What is the difference between $$$O(1)$$$ and $$$O(30)$$$? How is using bitsets 'true' constant time?

TCO has like at most 8 contestants and the format is very blitzy clocking in at only 85 min. It's much easier to cast this type of event than a 5 hour contest with >100 teams.

How did you get rid of $$$E_n$$$ in the third equation?

Can someone please explain the example a bit clearer? It's quite confusing. I don't understand the second iteration: Then we find $$$2$$$, evaluate {$$$0$$$} here we find it $$$0$$$. From the experience of $$$1$$$, we find $$$a_0 = 1$$$, so $$$\{1\} × 2 = 2$$$ seems good.

From what I understand the discrepancy $$$d$$$ is $$$2$$$ since the connection polynomial is $$$\{0\}$$$ (which means, $$$2 - \{0\}(1) = 2$$$) so the connection polynomial needs to be updated since it is non-zero. Using wikipedia notation:

$$$C(x) := C(x) - d(b)^{-1}B(x)$$$

$$$C(x) := \{0\} - (\frac{2}{1})\{1\} = -2$$$

Where $$$b$$$ and $$$B(x)$$$ are the discrepancy and the connection polynomial from the previous update. So how did he get $$$2$$$ instead of $$$-2$$$ in the example?

도토리 = doh-toh-rlee means acorn in Korean.

Legit thought this was for Yahoo! the American website.

https://www.youtube.com/watch?v=gl1aHhXnN1k

turned out amazin'

thank you, next next

FBI is at my door, what are the next instructions from here?

Related: https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Stars and Bars

A similar question can be rephrased as: How many ways are there to distribute n stars into k bins (possibly empty), where stars are non-distinguishable, but unlike your question, the bins/variables are distinguishable (so order matters!). If n = 4, and you have say k = 4 'bins' to distribute each star, stars and bars will count the number of ways this can be done (the number of unique k-tuples that sum to n). When order does not matter and empty bins are disallowed (eg 1 + 0 + 0 + 3 = 3 + 0 + 0 + 1 = 1 + 0 + 3 + 0 etc are counted as the same, but would all be different in stars in bars), use partitions, provided in the comment above by Gassa.

Note that stars and bars can be extended to work for inequalities: How many ways to write n as a sum that is less than or equal to n using just k = 4 bins? Just add an extra bin (k = 5) where the stars count as 0.

Petr and Onufry write problems for GCJ and Errichto wrote for IOI this year. There is enough overlap with WF probelms.

You know what ICPC 2018 was for MIT this year? Ksun48 + 2. Kevin did all the heavy lifting simply because he is more experienced. He (or they) recalls similar problems they have solved in the past to guide them through the contest. There is hardly ever rigorous proving of an algo during contest. They do indeed follow intuition and experience to solve problems.

Why are you defending Allen and desert97 so much? You don't want 2 lgm's to be on same team? You are friend of theirs? I'm vouching for Matthew because I want MIT to win.

The team should choose whoever make teamwork well and whoever can contribute most to team.

Okay, then pick Matthew.

ksun48 and desert97 made a lazy choice in picking Allen. I know they just want to be on a team with friends, but if they are serious about winning, Matthew is clearly a better choice.

Allen doesn't know about tricky corner cases to problems. He doesn't know enough about algos compared to Matthew. He doesn't have the exposure.

WF problems are written by CP'ers like Errichto, Misof, Petr--not pure mathematicians and their solutions tend to have certain algos in mind (not always ofc). It's not like IMO or Putnam! Totally different!

Having 3 CP'ers is great idea. Have each one of them solve and implement their own subset of problems--share the work. If they get stuck then they present and prove a solution to each other.

As I mentioned before, Matthew performance at IOI is good--silver medal. Are you saying he choked under pressure? Everyone deserves a second chance.

That special case where a team of 2 pure mathematicians won silver at WF pales in comparison to all the teams that have medal'd at a WF with a team full of experienced CP'ers, IOI medalists, etc.

And you say I know nothing about CP, why don't you sign in your main account and show me what experience you have?

Allen simply doesn't have the CP background compared to Matthew. Allen is a competitive mathlete of the highest caliber no doubt, but does he know algos? Does he know DP? Computational geometry? Has he ever competed in SRM's and won? Does he have years of CP experience? Matthew has and does. He is a greater asset to a WF than Allen.

Really? I think a programmer is more useful in contest setting. A mathematician can of course understand a problem and describe a solution at a high level, but that isn't enough in CP. A team is better off with someone who can actually implement algorithms like FFT and Delauney triangulation and not just describe them.

And did you just create a new account to troll me with this comment? Getting silver at IOI is still an extraordinary achievement--Kevin has two.

ksun48 said their team was formed last minute. Kevin is a decorated CP'er and 'mathlete', he plays to win, just like in today's tco final. He should optimize his chances, but it won't happen now that matthew confirmed he isn't on their team. I mean really though, what is the point of two talented CP'ers from the same school going against each other, just put them on the same team! And it's sad for matthew that he won't be able to even attend icpc.

matthew99 could easily replace either of ksun48's 2018 teammates and get substantially better results. I think one of the guys, cliu568, is a pure math guy, but having an actual CP'er is magnitudes more helpful in contest. The other guy, desert97, is actually red, but matthew99 is still better (I'm basing that entirely on their contest history and rank).

That is such a damn shame.

Will you be joining Kevin in MIT's ACM ICPC 2019 team? With you both on same team, MIT has a great shot at medaling gold this year.

My reaction when

ah, thank you

Auto comment: topic has been updated by zxcv890 (previous revision, new revision, compare).

You replace 4's with 2's then where did the extra 1's come from? And what about odd numbers? What is base case?

"Then we can replace all maximum numbers with twos and the rest we split into ones and weight will be the same."

Sorry I'm very new. Can you please explain the solution to Div2 problem A again? I understand every number n > 1 has at least two ways to be partitioned in a strict ordering ([n] and [1,1,1....1]). But what about the numbers in between? Merge a pair of 1's into 2's? Then what do we do about the pairs of 2's? Thank you for your patience.