Imakf's blog

By Imakf, history, 2 months 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

»
2 months ago, # |
  Vote: I like it +82 Vote: I do not like it

Speedforces.

  • »
    »
    2 months 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 .

  • »
    »
    2 months 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!!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry for making the second comment meaningless :(

»
2 months ago, # |
  Vote: I like it -45 Vote: I do not like it

Second comment:)

»
2 months 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...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why the solutions are not visible.... please look into this.

»
2 months 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)

  • »
    »
    2 months 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 :(

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same with me bro.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too, got 4 times WA for this.

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too bro

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same :(

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh,a sad story.

»
2 months 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.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Loved the contest interesting problems

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

losing sleep due to bricking problem a. quite literally

»
2 months 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.

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months 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.

»
2 months 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.

  • »
    »
    2 months 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?)

»
2 months 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.

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same issue. Why does reading as double give TLE? It is frustrating because I would have never guessed to switch double to long long. Reading as double just made more sense.

  • »
    »
    2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too,I suggest you use scanf but not use cin

  • »
    »
    2 months 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).

    • »
      »
      »
      2 months 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.

»
2 months 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??

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I sorted with long long still got tle (took x,y input as double), the problem is with double input.

  • »
    »
    2 months 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

»
2 months 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?

  • »
    »
    2 months 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. :)

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months 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.

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I mis read the question 1495B.

Thanks for the contest

  • »
    »
    2 months 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

»
2 months ago, # |
  Vote: I like it -26 Vote: I do not like it

badest contest

»
2 months 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?

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What happened with the solution of 'BFS Trees'?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is longest monotone segments?

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really too fast solution.

»
2 months 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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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

    • »
      »
      »
      2 months 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).

    • »
      »
      »
      2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months 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!

  • »
    »
    2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As fast as flash.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

It seems that the submission of F is not visible.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

after very long time i able to solve A,B,C during the contest , am i improving or really questions were easy?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same with me. I think we contest had easy problems

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

many people who solved div2/C must not have thought of the solution in the way given in editorial..

»
2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
2 months 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?

  • »
    »
    2 months 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.

»
2 months 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

»
2 months 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.
»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the difficulty of Div2 C as your opinion?

»
2 months 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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh sorry my bad I read condition for y wrong

»
2 months 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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, that is okay. I was thinking that if we change x to |x| then the y with which it will get paired, will also change. So, how can we prove that it won't affect the final answer.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is changing x to |x| that keeps the final answer correct.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Got it. I made a few points on paper and got the intuition for it.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I tried algebra bash for div2 C

»
2 months 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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 months 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 !

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    transform long double into double to print it

»
2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for turning me green again ;)

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The pretest for div2.D is too weak!

»
2 months 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
  • »
    »
    2 months 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

»
2 months 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.

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I see. I should cast a[i],b[i] into long long before computing them or define them as long long at the very beginning.

      This really gives me a lesson. I was aware that I could have some overflow but I thought ll tp = some int calculation will cast the variable to long long first.

»
2 months 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.

»
2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In this case, answer is always 0?

    • »
      »
      »
      2 months 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.

»
2 months 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

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Someone kindly elaborate Div2F please!

»
2 months 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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. Consider a chessboard-like input grid.

    • »
      »
      »
      2 months 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
      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it
            .X.
            XX.
            X.X
            .X.
            

            PS. nvm

          • »
            »
            »
            »
            »
            »
            2 months 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 ~

            • »
              »
              »
              »
              »
              »
              »
              2 months 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!

»
2 months 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.

  • »
    »
    2 months 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.

»
2 months 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)

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months 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.

  • »
    »
    2 months 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.

»
2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Neither edges nor corners need a better explanation.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone clear my doubt in Problem D (Div 2) that why the input

3
1 3 2

has output 0 instead of 1.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    p = [1, 3, 2]

    Player1 = Qingshan (moves from x to x' if p[x] > p[x'] and |x — x'| == 1 and x' != y, decreasing sequence)
    Player2 = Daniel (moves from y to y' if p[y] < p[y'] and |y — y'| == 1 and y' != x, increasing sequence)

    1st case:
    Player1 chooses x = 1, Player2 chooses y = 2 or y = 3 (it doesn't matter)
    Player1 cannot move (p[1] < p[2]) => Player1 loses

    2nd case:
    Player1 chooses x = 2, Player2 chooses y = 1
    Player1 moves to x' = 3, Player2 moves to y' = 2
    Player1 cannot move (p[3] < p[2]) => Player1 loses

    Player1 chooses x = 2, Player2 chooses y = 3
    Player1 moves to x' = 1, Player2 moves to y' = 2
    Player1 cannot move (p[1] < p[2]) => Player1 loses

    3rd case:
    Player1 chooses x = 3, Player2 chooses y = 2 or y = 3 (it doesn't matter)
    Player1 cannot move (p[3] < p[2]) => Player1 loses

    Conclusion: Player1 loses in all cases, this is why the answer is 0.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your explanation, but in the 2nd case y'=2 but it is mentioned that y'!=x. So can you please explain this?

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        We use these notations (x and x', y and y') only to emphasize that players can go to neighboring positions that are empty at the current step and have a smaller (for Player1) / greater value (for Player2).

        Player1 moves to x' is the same as changing x to x' (i.e., x = x').
        Player2 moves to y' is the same as changing y to y' (i.e., y = y').

        x and y change at each step.

        2nd case:
        Step 1: Player1 chooses x = 2, Player2 chooses y = 1
        Step 2: Player1 moves to position 3 => x = 3, Player2 moves to position 2 => y = 2
        Step 3: Player1 cannot move (p[3] < p[2]) => Player1 loses

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you Tudor67, your explanation was quite helpful.

»
2 months 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)$$$.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D in Detail explanation : https://www.youtube.com/watch?v=Kn7GpiS-iQw

HAPPY CODING

»
5 weeks 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).