Imakf's blog

Codeforces Round #706 Editorial
By Imakf, history, 4 years ago, In English

The jury solutions will be updated later.

The jury solution is updated now.

1496A - Split it!

Idea: waaitg

Tutorial is loading...
Solution (Imakf)

1496B - Max and Mex

Idea: waaitg

Tutorial is loading...
Solution (waaitg)

1495A - Diamond Miner

Idea: smg23333

Tutorial is loading...
Solution (smg23333)

1495B - Let's Go Hiking

Idea: waaitg

Tutorial is loading...
Solution (waaitg)

1495C - Garden of the Sun

Idea: Imakf

Tutorial is loading...
Solution (Imakf)

1495D - BFS Trees

Idea: waaitg, Daniel_yuan, isaf27

Tutorial is loading...
Solution (Daniel_yuan)

1495E - Qingshan and Daniel

Idea: Imakf

Tutorial is loading...
Solution (Imakf)

1495F - Squares

Idea: waaitg

Tutorial is loading...
Solution (waaitg)
  • Vote: I like it
  • +160
  • Vote: I do not like it

Comments Comments (146)
| Write comment?
»
4 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Speedforces.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    More number of people would have solved Div2 D/ Div1 B if clear problem statement was made in starting itself .

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I got WA in div2 C because i was not using set precision. Why is it so? Please explain!!

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    ауызынды жапшы сойлей береди екенсин

    → Reply
»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it -45 Vote: I do not like it

Second comment:)

→ Reply
»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

Am I the only one who read

$$$p_{x'}<p_x,p_{y'}<p_y$$$

instead of

$$$p_{x'}<p_x, p_{y'}>p_y$$$

(Div2D/Div1B)

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Same here, That means I had read the wrong question and still my code passed the pretests... :) Very weak pretest for div2 D :(

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same with me bro.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too, got 4 times WA for this.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, if you don't mind, can you explain what is meant by longest monotone segment? I can't find the explanation of the term anywhere on google.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Longest monotone segment means the longest segment in which all the elements in the segment are increasing or decreasing. but not both. For example:

        • [3, 5, 6, 10] is a monotone because the elements are increasing.
        • [20, 10, 9, 8, 5] is a monotone because the elements are decreasing.
        • [1, 2, 4, 3, 5] is not monotone because the some element are increasing and some are decreasing.

        So the longest monotone segment is the longest of such segment. I don't know if any neighboring element can be the same, but that doesn't matter for the problem since all the elements are guaranteed to be distinct.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But solutions will be exact same except the l%2 condition in the last

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too bro

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same :(

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh,a sad story.

    → Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

losing sleep due to bricking problem a. quite literally

→ Reply
»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Why would it have been better? Is it because that would have allowed to fit more cases in pretests?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Yes. 11 pretests on a YES/NO problem with a lot of casework is very obviously a bad idea but for some reason the authors didn't use multitest.

      → Reply
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, now I read the editorial and came to know about that. Can it be solved for sharing corner points? Or even for sharing edges? (initially assuming it is not forming a cycle?)

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same thing happened to me too. But I couldn't fix it during the contest.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same. I just got 6 TLE with correct algorithm just for that and lost the points for C.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    It takes more time to take input as Double in C++ and even it takes more time to sort it.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not sure, but afaik, although both "long long" and "double" are 8 bytes, the processes on double are way slower, and the reason is the precision problem. I don't think you got TLE because of input, but because of the operations. You use "double" typed vectors, you add elements to them, then sort, multiply them, take the square root. These operations may have overwhelmed the computer(server).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      I don't know why, but Kotlin doesn't care what to store and what to operate with (Long or Double). That's fun btw, cause c++ working slower with doubles.

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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??

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i'm think for long double or double sort work very low.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    cout.setf(ios::fixed | ios::showpoint);
cout.precision(15);

    just don't rewrite it in every test case and try to use '\n' instead of endl

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    The key is that Qingshan has two ways to win. The first is that Qingshan can't move for the both sides of it are greater.In this way, the length of monotone subsequence is important. The second is that Qingshan meets Daniel.It means that Daniel can block Qingshan's way and meet in the middle of a monotone subsequence. Understand that and you will solve it. :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Can you elaborate more? Why longest monotone is important here?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it

        If there are two longest monotone and they have the same position, the position whose value is greatest in the monotone is available when the length of the longest monotone is odd(Try to imagine when the two meet). Otherwise, Daniel can always choose the position whose value is least in the other longest monotone (If it isn't exist, Daniel will choose the position near by Qingshan chosen to make Qingshan can't move to the longest monotone), and Qingshan will always lose.

        → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I mis read the question 1495B.

Thanks for the contest

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We assume that both player plays optimally it includes well choosing the start, if 4 is the number on which is Q, D goes on 3 and no move is possible for Q.\ if 4 is the index D goes on index 1 and either Q move to 3 D move to 2 and Q is stuck either Q goes on the other side and D can walk 3 moves Q too, and Q is stuck, so Q loose if D choose well where it starts

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    turns out inputting a double is slow as hell in cpp. as the values were integer, you should have input them as integers in a first time.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What happened with the solution of 'BFS Trees'?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is longest monotone segments?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    subarray which is either strictly increasing or strictly decreasing .For example take array 2 4 6 5 3 8 7 4 3 . Here 2 4 6 , 8 7 4 3 are some of the monotone segments . 8 7 4 3 is longest monotone segment.

    → Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    use long long int instead of double for a and b and x and y, double (and long double) are slow to read and to sort

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      now it's accepted. thank's a lot i learn new thing and i will never forget it

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Could you please tell me that why double is slower than int(as sort).

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks a lot,even I got to learn a new thing , this thing costed me 3 submissions during the contest as I wasn't aware of this fact

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it +5 Vote: I do not like it

    Think of the permutation as hills and valleys. Notice that the first player always has to start at the top of a hill, as only top of hills will have both adjacent points smaller than it, otherwise player 2 would pick the smaller adjacent side forcing player 1 to pick larger side, hence losing. Now the first player would want to descend, so he will pick the mountain which has the longest (and equal) descent on both side out of all mountains( if he doesn't, then player 2 can pick a longer ascent, and player 1 will run out of moves before player 2).Also there should only exist one unique mountain with the longest sides, otherwise player 2 can ascend the other mountain and since player 1 plays first, he will be the first one to exhaust all his moves. Both sides should be equal so that player 2 can't intercept us at one side(if only one side is longest, player 2 would be able to choose in way so that player 1 loses). Now the length of this descent should be odd, since whatever side player 2 chooses, we can go in the same direction, and he will be the one running out of moves first. This is the only case player 1 wins Edit: logic was wrong initially

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As fast as flash.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It seems that the submission of F is not visible.

→ Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Author's English skill still has space for improvement.

    j is the parent node of i in the required tree. It must satisfy the condition given because required tree is a BFS tree of both x and y. Such j might not exists for some i.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.
→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the difficulty of Div2 C as your opinion?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ans=0 is right. why it should be 1 ? explain. there is no index where we can win.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For index =7 (0 based ) When value is 11

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        If first player will start at index 7 then second player will start from either index 4 or index 10. then first player can't win. from index 7 if first player choose to go 6 then second player will move 4 to 5.and then first player can't move further.

        or if first player move in the right (first player move, second player move) (7->8,4->5) (8->9,5->6) (9->10,6->7) and now first player can't move. So in both situation player first can't win.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because distance will still remain same since x^2 = (-x)^2

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

while long long int gets accepted https://mirror.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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It takes more time to take input as Double in C++ and even it takes more time to sort it.

    → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I tried algebra bash for div2 C

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 !

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    transform long double into double to print it

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It takes more time to take input as Double in C++ and even it takes more time to sort it.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I suffered from the same issue due to my carelessness. Float operations are (10-20 times) slow than their integer counterparts. For this problem, the hotspot of time usage is clearly the sorting, which invokes the comparision for O(n log n) times.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for turning me green again ;)

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The pretest for div2.D is too weak!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

5
1 2 5 4 3
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    If Player 1 is at index 1 -> Player 2 can be at index 2
    If Player 1 is at index 2 -> Player 2 can be at index 1
    If Player 1 is at index 3 -> Any position of player 2 will be loosing position or him. i.e if
    1) player 2 decides to be at index 4
    player 1 -> index 2
    player 2 -> index 3
    Player 1 -> index 1
    Player 2 cant make move.
    2) Player 2 decides to be at index 5
    player 1 -> index 4
    player 2 cant make move
    3) Same in case of index 1 and 2.
    If Player 1 is at index 4 -> Player 2 can be at index 5
    If Player 1 is at index 5 -> Player 2 can be at index 4

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's because that for the input array you used std::vector<int> instead of std::vector<long long> in the previous submissions, nothing to do with precision. More accurately:

    ll tp=a[i]*a[i]+b[i]*b[i];

    This will cause an integer overflow, and the result might be a negative number, which you soon called sqrt() on. And this will return nan, as shown on the judger.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In this case, answer is always 0?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah,because if there are multiple shortest paths between x and y, there must be an point i,which doesn't satisfy the condition in the tutorial.

      However,you can just consider the situation that an edge in the shortest path is contained in a circle.I think it's better to understand.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Someone kindly elaborate Div2F please!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. Consider a chessboard-like input grid.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think it works for this big chess, does it fail for higher ? Or maybe a different $$$n\times m$$$ grid ?

      Wrong image here, refer followup reply
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The edges between points (1,1),(1,9),(9,9) and (9,1) in your diagram form a loop, so there may be more than one simple path between two points.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          ok if we let (1,1) with the flower, that is not empty the (1,1) cell?

          Like this:

          Image
          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
            .X.
XX.
X.X
.X.

            PS. nvm

            → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +21 Vote: I do not like it

            You can have a look at the following picture, it is unable to find out the legal solution, I proved it by counterevidence, but the process is more complicated, so I will not write it in detail, you can also have a try ~

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              This is nice I was also feeling it might fail for smaller chessboard!

              → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

testcase -->

5

1 2 4 3 5

answer is 0.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    If first chose position x(x\neq 1), then second chose position x-1. If first chose 1, second can chose any.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To make it clear, "the tree" here means "a tree that is both a BFS tree rooted at x and y at the same time". So by definition, the length of the (one and only) path from x to y on that tree must be equal to the length of the shortest path from x to y in the original graph.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's 0 instead. Suppose Qingshan start at x = 2 (He can't start at x = 1 or x = 3 because he wouldn't be able to make the first move)，Then no matter which y Daniel chooses, Qingshan is definetely going to lose.

    → Reply
»
4 years ago, # |
← Rev. 11   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Neither edges nor corners need a better explanation.

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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)$$$.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
18 months ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

deleted

→ Reply