Speedforces.

Such a fast editorial! That's great! :)

Second comment:)

Task C have one max test???? My random solution got AC. So weak...

Am I the only one who read

instead of

(Div2D/Div1B)

Interesting as problem 1C is, 1B is really a bad problem. But I do hope the next competition can be better.

losing sleep due to bricking problem a. quite literally

It will be better if the data of div2D/div1B are multi-tests.

I felt sad that I ignored the description "Magically, any two empty cells have no common points (neither edges nor corners)." in div1 C.

I got TLE in C just for taking inputs as double in my code. The same code when I just changed the input type from double to long long it got AC. Help!! Thanks in advance. Links to the TLE and AC code is given below and changes are also specified by comment.

• AC code
• TLE code

With many participants happened this: one of the solutions got TLE, the other one got OK, but they have the same logic (problem Div.2-C).

Why??

can anyone explain to me why the answer in D is only 1 or 0?

I mis read the question 1495B.

Thanks for the contest

In Div_2_C

109615476 : This solution was accepted. 109601607 : This one got me TLE. Can someone please help me understand why did I get tle?

What happened with the solution of 'BFS Trees'?

What is longest monotone segments?

Can Any One Help Mi That Why I Get TLE On Today's Problem C

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ld long double


void solve();

int main()
{
    int tc=1;
    cin >> tc;
    while(tc--)
    {
        solve();
    }
}

void solve()
{
    int n,t1=0,t2=0;
    cin >> n;
    vector<ld> x(n),y(n);
    ld a,b;
    ld sum=0;
    for(int i=0;i<2*n;i++)
    {
        cin >> a >> b;
        if(a==0)
        {
            y[t1++]=abs(b);
        }
        else
        {
            x[t2++]=abs(a);
        }
    }
    // ld sum=0;
    //why tle
    sort(x.begin(),x.end());
    sort(y.begin(), y.end());
    for(int i=0;i<n;i++)
    {
        sum+=sqrtl(x[i]*x[i]+y[i]*y[i]);
    }
    cout << fixed << setprecision(15) << sum << endl;
}

Here Is My Submission.109634972

I cant see solution for div1 a (smg2333) not enough rights

Can anyone explain problem Div 2 D? The editorial is kind of overwhelming for me. Thank You in Advance!

As fast as flash.

It seems that the submission of F is not visible.

Another suggestion: Use name Alice for first player and Bob for second player. This time Quishisomething and Daniel where not so bad, but still I had to read severeal times before being able to memoize who is first, who is second. Later one of the player is referred to as "she"...what might be hard to understand depending on cultural background.

Alice and Bob is simply less confusing.

Then, let's consider the contributions of other vertexes i. In the bfs-trees of both x and y, there must be and only be a edge linking i and j, which j satisfies dist(x,i)=dist(x,j)+1∧dist(y,i)=dist(y,j)+1.

Can someone explain this?

I am still struggling to understand Div2F's statement, can any one please explain what does "Given a graph, we define f(x,y) to be the number of spanning trees of that graph that are BFS trees rooted at vertices x and y at the same time." mean?

PS. got it

For 1495E.

Why this graph has at least 2 simple paths between 2 empty cells.

....X..X..X....
XXXXXXXXXXXXXXX
.X......X......
.X..X.........X
XXXXXXXXXXXXXXX
.X............X
.X.X..X.....X..
XXXXXXXXXXXXXXX
X...X.X........
X.......X...X..
XXXXXXXXXXXXXXX
X.......X......
X............X.
XXXXXXXXXXXXXXX
X.X....X.....X.

What is the difficulty of Div2 C as your opinion?

For Div2 D /Div 1 B Why This Testcase giving ans=0 while ans should be 1

N= 11

5 6 9 8 1 2 3 11 10 7 4

In Div.2C, why can we turn any point (x, y) to (|x|, |y|) without changing the answer?

when i am taking input in long double is giving tle https://codeforces.com/contest/1496/submission/109591967

while long long int gets accepted https://codeforces.com/contest/1496/submission/109594626

is long double making such a huge difference in time? and why it is not getting memory limit exceeded instead of time limit exceeded?

I tried algebra bash for div2 C

I tried implementing DFS for E which failed on some edge cases and now I am wondering, is there actually a solution with DFS?

A problem in Div1A when I use 'printf("%.10Lf", ...)' to print a long double, it seems something wrong with it on the platform, but it does work correctly on my com. So could someone help me on how can I use 'printf' to print a long double ? thx for your help !

For TASK 3 div 2, i wrote a solution with double as my vector type seems and it gives TLE on TC:- 4 but if i change double type to int it passes with time 124ms can anyone one tell me why it is happening

109668126 Code using double

109668230 Code using int

Thank you for turning me green again ;)

The pretest for div2.D is too weak!

Can someone explain the sequence of moves in the following test case for Qingshan to win? Thanks!

5
1 2 5 4 3

Div2 C. Why my submission 109604661 109606220 failed with setprecision(11) and setprecision(16) with double. This infrustrates me to the no end and finally passed with setprecision(15)..

Does anyone have an explanation for this? I thought a setprecision(11) could meet the requirement.

Okay , so here is thing, I misread Problem div2(D)/div1(B) and solved some different problem and later realized that I screwed up the problem statement. I thought that whichever index the player steps on becomes his territory. Meaning, the other player can never approach this index ever. Even though, the original problem is different from the one I assume it was, I consider this alternate problem is also fun to solve.

For div1D, consider f(x, y), what if there are multiple shortest paths between x and y? Tutorial skipped this.

Could someone help me with the problem 1C/2E? I get WA on test 3, but I don't know where goes wrong...Thanks in advance. my code

Someone kindly elaborate Div2F please!

Can someone tell Div1C / Div2E : Will answer always exist regardless whether initial empty cells share a corner or edge or not? I feel this is true, but cannot prove it. And any ideas on how to solve in that case? Using Disjoint Data structure?

Edit: In general I guess there may or may not exist solution but I cant find example, and in general we may have to use backtracking if constraint in question was not given

Can anyone expain, why in Div.2 Problem D,

testcase -->

5

1 2 4 3 5

answer is 0.

How is it obvious that the distance between $$$x$$$ and $$$y$$$ in the tree is $$$dist(x , y)$$$, since $$$dist(x,y)$$$ is number of vertices in the shortest path in the graph(there could be multiple paths)

Can someone tell why this solution 109616067 is exceeding the time limit?

What will be the answer of Div2 D for 1 3 2 input. I think it should be 1.

Just a public personal note that Div1D / Div2F was real "fun" to solve in non-C++, heh.

109775962 is my passing submission. Notes:

• approximately halved runtime by using $$$f(i, j) = f(j, i)$$$ symmetry
• flattened all arrays. This is overall the most productive optimization; it won't pass with regular 2D arrays for D (distance) or ans, or with an array of adjacency lists for the graph. (instead, edges are stored in U and V, sorted by U and using the auxiliary array P to point to the subarrays corresponding to each vertex)
• "back to basics" code style; even the BFS doesn't use a deque, but an array and two pointers, although it can probably still pass with the deque, as the BFS isn't the bottleneck.
• avoided a * b % MOD and uses addition and shifts instead, saves about 150ms over an equivalent solution with multiplication.

I have an even faster submission: 109763945, but it relies on skipping modular multiplication for factors $$$0$$$ and $$$1$$$, and therefore optimizing on this relies on the fact that factors $$$2$$$ and above are limited in number, which is a heuristic that I couldn't prove.

Upd: even faster: 109780486. Modular addition (no multiplication or %). Shortcuts if it finds a $$$0$$$ factor, again, I'm unsure whether there is a way to defeat this optimization and make it run like 109775962.

Neither edges nor corners need a better explanation.

Em...i think the Div1.E's description has a small problem. On the 4th line of INPUT, it says $$$p_{j-1}<p_j(2\leq j \leq n)$$$ but the truth is $$$(2 \leq j \leq m)$$$.

Taking input as a double is slow in c++ (my learning from Div1 A).

deleted