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

Problem Div 1 D strongly resembles a problem from the 2015 Putnam competition, which we can see here:

https://artofproblemsolving.com/community/c7h1171035p5624365

If you used the Stern-Brocot Tree, there are cases in which the Tree may be very deep, as well as cases in which it is not optimal to take the LCA in the Stern-Brocot Tree.

Declaring a round unrated destroys a major external reward for students, and moreover emblazons a scarlet letter on the problemsetter. In cases where it is obvious the round should be unrated, we have no choice but to incur these costs. But when the objections are only minor, there is no reason this should happen.

1. sqrtdecompton

1. waterfall

1. ekzhang

USA Team is being announced right now:

1. Benq

The FFT code here (method DOIT) is amazingly accurate (written by ko_osaga) http://codeforces.com/contest/958/submission/37318120

And the new code gets 9 cases out of 10. Sad life.

At least you weren't 5 seconds away from a correct solution to 2. Had two cases, submitted the correct solution without having a print statement, got WA on sample, added print statement, uploaded, just as time ran out...

I don't think your second warning is necessary -- we are on Codeforces, after all :-)

Harvard Team: 1. waterfalls 2. rafael859 3. nhtrnm

Memoization is clean for Div1 B: http://codeforces.com/contest/917/submission/34673801

Massachusetts Institute of Technology Team: 1. ksun48 2. desert97 3. cliu568

I think on F, that ans[0] = ans[1] = 0..

Thanks for the contest, it was fun!

I couldn't get my code to compile, since apparently __int128's don't exist on CF?

http://codeforces.com/contest/913/submission/34030034

Persistent Segment Trees are unnecessary for div1B, as one can instead use the same trick from 868F, where we have the range "sliding" around. Full disclosure: this trick was obtained from Benq

http://codeforces.com/contest/833/submission/33818859

We can think of it this way -- the problem can also be thought of this way.

Given a graph G = (V, E), what's the fewest number of vertices we can mark such that for every a and b in the graph G, there is a path between a and b such that all vertices on this path (except for possibly a and b) are marked.

This restatement makes it clear that the order of the guests is not important.

Hi, I submitted A (incorrectly) just before the website crashed, and I had to waste about half an hour waiting for it to come back on. As a result, my A was submitted 30 minutes later than it should have been, and my rating will likely fall is a result. Can this contest be unrated for me?

If we define P(x) as in the problem, then the condition in question is equivalent to the nth cyclotomic polynomial P_n(x) dividing P(x). Now, it can be shown that the minimal polynomial of a primitive nth root of unity w is the cyclotomic polynomial. https://en.wikipedia.org/wiki/Cyclotomic_polynomial What this means is that if P(w) = 0 for a polynomial P, then P_n(x) divides P(x). Moreover, this condition is necessary and sufficient. In complex numbers, the center of mass is P(w) over the total number of points. Therefore, the condition "center of mass at zero" is necessary and sufficient.

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

Your intuition is correct: see here

https://pdfs.semanticscholar.org/ffe1/b723a0cd0319e5ad326088163acf1eed3d9c.pdf

The number of permutations which work are equal to

1290482565120000, so you have still not found all the solutions.

The permutations you listed are correct. Could you write a program for a = [1^2, 3^4] b = [1^2, 2^6] a*b = [7^2]?

No, I do not know of a single answer to the problem, and a very distinct possibility was no solutions. Thank you!

EDIT: I have been notified that a solution does, in fact, exist to this problem.

From what I have heard, the problem is a harder version of Problem A in this competition: http://cs.stanford.edu/group/acm/slpclive/problems/problems_2016.pdf

I've also heard that one can use Eppstein's algorithm to solve it.

The code here gets AC on A:

http://ideone.com/Dnz3Nu

Agreed. Div2 1000 was easily googleable, and was from an ASC!

This was a great contest! Although I am somewhat salty that I had a solution for the third problem in div2, here, http://ideone.com/172siu, but could not figure out how to submit it.

Was the open hacking phase started?

I have a different solution to Moving Segments, which I think reflects how weak the time limits are. Instead of doing a sweep line, observe that the answer for a point x and an interval [a, b] is merely just max(0, |x - (a + b) / 2| - |(a - b) / 2|) This function has derivatives  - 1, 0, and 1, so it is effectively unimodal, since we are only trying to solve for the answer. Hence, we may apply a ternary search:

#include <bits/stdc++.h>

using namespace std;
typedef pair<long double, long double> PII;
static vector<PII> pairs(100005); 
int N;
long double f(long double x){
    long double res = 0.0;
    for (int i = 0; i < N; i++){
res += max((long double) 0.0, abs(x - (pairs[i].first + pairs[i].second)/2) - abs((pairs[i].first - pairs[i].second)/2));
    }
    return res; 
}
int main() {
    long double l = -1e9, r = 1e9;
    cin >> N;
    for (int i = 0; i < N; i++){
        long double a, b; cin >> a >> b;
        pairs[i] = make_pair(a, b);
    }
    for(int i=0; i<200; i++) {
        long double l1 = (l*2+r)/3;
        long double l2 = (l+2*r)/3;
        if(f(l1) > f(l2)) l = l1; else r = l2;
    }
    cout << setprecision(0);
    cout << fixed;
    cout << f(l) << endl;
}

This easily runs under the time limit, even without i/o optimization. Was allowing such solutions intended?

Is it possible that out-of-contest submissions can be implemented?

D on div 1 is quite similar to this problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=283

The only difference is that that one is slightly harder: B is not necessarily equal to D

It was during computer science class, so I had a valid reason to be on a computer.

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

A solution to the hard case of D can be found here:

http://www.austms.org.au/Publ/Jamsb/V44P2/pdf/1761.pdf

I'm rather angry at this codeforces round. First, although I got A in 00:00, B took me very long, due to the fact that codeforces repeatedly gave me website exceptions while submitting. Furthermore, I received rather strange verdicts. 15518610 [submission:15519407][submission:15520501][submission:15521050] 15521416

Next, I encountered significant lag on D, and I submitted the same program twice during the round.

Conservation of legendary grandmasters???

Should we discuss the problems here after the contest?

Hope for maths!

+100 for successful hacking attempt of codeforces!

What about biology?

For those interested, here is a much easier version of three states. http://www.usaco.org/index.php?page=viewproblem2&cpid=88

Solving A is really good! This is a great AP CS class! On today's contest, it took me three attempts to solve A. Maybe you can translate them into Java and explain my solution to them?

12746212 （WA pretest 4) (strict equality is needed) 12746358 (WA pretest 5) (you have to take away from the maximum always) submission:12748500 (This is a correct solution, following your explanation)

My C Solution: http://codeforces.com/contest/552/submission/11647965 So basically, if we look at everything mod w, the only weight that matters is one, because everything else is zero. So if there is a way to get this to work, we can change the current weight and divide by w. Recursively, this gives the correct answer.

Surprised at high number of TLE's, I guess..

Hmm.

How hard was problem E?