Скоростной разбор задач! Спасибо за разбор)

So fast !

In problem B one could simply code an O(NT²) solution and make a 'break' every time when the current probability is small enough (I used 1e-15 as threshold).

For B, I believe that many contestants coded an O(nT) solution, but still got TLE regardless, including myself. Maybe the time limit of 1s was slightly too short?

Here is my code below: is there anything I could have done to speed it up enough? http://mirror.codeforces.com/contest/498/submission/9255020

for myself: never use standard pow, I failed B, because of that.

Ребята, что за дела. Вступаюсь за сокомандника.

Вот его код в дорешке зашел 9259713.

А на контесте Tl на последнем тесте 9256671.

Возможно ли в таких случаях перетестировка например некоторых решений?

UPD1. el_sanchez сказал, что был другой компилятор. Не во прос и под другим зашло 9260008

И как в B по данной динамике посчитать мат. ожидание?
Просто судя по правильным решениям -- просуммировать все значения dp (кроме dp[0][0]).
Я не могу понять, почему это так.

Спасибо вам, за качественные задачи и за быстрый разбор.

In Div1 B/Div2 D, I'm having trouble to find the mistake in my solution :( I get WA on pretest 6 9257394

I basically do

where t is the time, n is the nth song and curplay is the time the current song has been playing.

Can anybody help ?

Finally became an expert.. yipee :)

in Div 1 C , why does not my strategy work correct . Plz help dans http://mirror.codeforces.com/contest/499/submission/9262810

Merry Christmas to everyone !! Became expert !!

put me minus !!!

why this solution does not work for problem C Div 2

9264650

Обидно, когда корректное и не особо неоптимальное решение на плюсах приходится ещё и упорно оптимизировать, чтобы оно проходило =( На каком-нибудь Python, я так чувствую, вообще без шансов эту задачу сдавать.

why dont you attach the code with every problem??? Its really helpful. Please do it. Looking at the solution is difficult for someone trying to understand the solutions of harder problems. Frustrated. :(

EDIT: I discovered the problem and solved it, but anyway that is O(nT^2) so it gets TLE. The idea is correct but in the code I had a mistake in the first condition and I fixed it.

In problem Name That Tune I can't understand the third paragraph. Can anyone explain it more clearly?

Besides, I want to know why my idea is wrong. According to my idea, DP(i,j) = The expected value of number of recognized songs if I started from song i and j seconds have passed. So DP(i,j) = + pow(1 — pi[idx], ti[idx] — 1) * DP(idx + 1, sec + ti[idx]) . And the answer is DP(0,0)

Hope someone tells me what's wrong with the idea or the code. Here is the code:

double DP(int idx, int sec) {
    if (sec > t)
        return idx - 1;
    if (sec == t or idx == n)
        return idx;
    double &ret = memo[idx][sec], tmp = 1;
    if (ret == ret)
        return ret;
    ret = 0;
    for (int i =1 ; i < ti[idx]; ++i) {
        double &tret = memo[idx + 1][sec + i];
        if (tret != tret)
            tret = DP(idx + 1, sec + i);
        ret += pi[idx] * tmp * tret;
        tmp *= 1 - pi[idx];
    }
    return (ret += tmp * DP(idx + 1, sec + ti[idx]));
}

Влияет ли на решение в задаче "Массив и операции" условие "i+j нечетное"?

What is the exact complexity of Kuhn's Algorithm? Is it O(N*E)? Also, O(n*m*logA^3) = 100*100*30*30*30. Yet it passes the time limit. Probably cause of the heuristics inside the algorithm. How can we know for sure that Kuhn's algorithm with heuristics will be able to pass the time limit?

To find the number of lines (in the input) which passes the line (x1,y1,x2,y2) you could also use this way: Consider the name of the line (x1,y1,x2,y2) d Find the intersection of each line in the input with d. (By solving 2 equations). If the intersection (answer of equation) is between our 2 points, then the line crosses d. So we should +1 our answer. It has a little bug: When the gradient becomes infinity which should be solved with an if.

This is my code: Submission Link

problem D(Div.1) can be solved also by sqrt-decomposition. For each city i and for each time v (modulo 60) you should store the total time which is needed to get from city i to the last city which is in the same bucket.

My submission: 9259900

Please Someone explain Div1 B elaborately. Specially transactions between the states ..

Thanks in advance :)

In problem Div 1 B (Name that tune), I could not understand approach to reduce the complexity from O(N*T^2) to O(N*T). Any detailed explanation is really appreciated.

Thanks

Funny fact: problem A from div1 was already used for a CF round very long time ago, and it was problem D for that contest (well, now we have lines instead of circles...) :)

Why does a greedy algorithm not work in 498C? By greedy I mean take a good pair x, y and divide the two number a[x] and a[y] by as many prime factors as possible. Shouldn't it give the same result?

Could anyone please, explain me the third test of the Name That Tune:

3 3
50 3
50 2
25 2

I am thinking this way: p(0;0)=1 p(1;1)=p(0;0)*0.5=0.5 p(1;2)=p(0;0)*(1-0.5)*0.5=0.25 p(1;3)=p(0;0)*(1-0.5)^2*1=0.25 p(2;2)=p(1;1)*0.5=0.25 p(2;3)=p(1;1)*(1-0.5)*1+p(1;2)*0.5=0.375 p(3;3)=p(2;2)*0.25=0.0625

M=p(1;3)*1+p(2;3)*2+p(3;3)*3=1.1875

Where have I missed 0.5?

Thank you

What is wrong in my code?:

include <bits/stdc++.h>

using namespace std;

long long n, x, l[10010], r[10010], ans, res;

int main(){ cin >> n >> x; for(int i = 1; i <= n; i ++){ cin >> l[i] >> r[i]; } ans ++; int j = 1; while(j <= n){ if(ans + x < l[j]){ ans += x; } else { res += r[j] — ans + 1; j ++; } cout << ans << ' '; } cout << res; return 0; }

For problem C div 1, the test is weak, I just use bipartite graph without factorized those numbers, but it still passed the system test. My submission

Div1A — "It can be easily proved that, if two points from statement are placed on different sides of some line, this line will be crossed anyway. So, all we need to do is to cross all these lines, so the answer is the number of these lines." — that is completely obvious why we need to cross all lines such that home and university are on its opposite side, but what is very important — why it suffices to cross them just one time, why there exists a route such that we do not need crossing it more than one time?

I know answer to that question, but I just wanted to point out that saying "it can be easily proven that something obvious" and not mentioning something significantly harder is pretty funny.

What is the expected complexity to Div1D? I coded and optimized it pretty much everywhere where I could and it passed, but TL was 2s and my time was 1,93s...

By the way TL's were very strict in that contest. Amount of people which got TLE on B and E is too damn high. TL to D was also strict, but maybe maxtest was included in pretests, so it didn't cause that many TLE on systests. I always emphasize that there is no point in setting constraints to be as high as possible. It's always very sad to fail, because of some random TLE on systests and it was very often case in that contest.

I know it's 3rd post in a row, but since they all regard to different issues I think it's better to keep them apart.

I could be mad.... I have got TLE4times.... who can give me some help for div2 D here is my code 10266510

I have been getting time limit exceeded on test 65 for 498B (Name that tune). I would be glad if someone could quickly glance at my code and tell me how I am exceeding a runtime of O(nT). This is the link to my code: http://mirror.codeforces.com/contest/498/submission/12256295

An easier way to solve div1 C / div2 E: Try to maximize the no. of operations for every prime factor that occurs in any of the numbers by constructing a flow network that corresponds to a bipartite graph with even indexed vertices in the first partition and odd indexed vertices in the second partition (assuming 0 based indexing). An edge from the source to a vertex i with weight j for the graph corresponding to a prime no. p means that i lies in the first partition and p occurs as the jth power in the ith number. Similarly if i would have been odd indexed, we would have had an edge from i to the sink of weight j. The remaining edges are the edges between the partitions that correspond to good pairs having infinite (or 100) capacity (Since flows from source to the vertices in the first partition and from vertices in the second partition to the sink already put a restriction that the no. p cannot be taken more times than it occurs in the ith no.) . Here is an implementation by rng_58. I understood the solution to the problem from this submission itself.

{deleted}

For the make the tune question, I've done 13 wrong submissions. I'm still getting tle. My solution is O(n*T) but keeps failing on testcase 65. The setter mustn't have kept the constraits for that problem so tight knowing that people will use long double for storing the elements. I even removed that and made a lot of changes to optimize my code but it's still getting tle. It works fine when I run a random testcase 5000*5000 in my machine.