### Imakf's blog

By Imakf, history, 2 months ago,

The jury solutions will be updated later.

The jury solution is updated now.

1496A - Split it!

Idea: waaitg

Solution (Imakf)

1496B - Max and Mex

Idea: waaitg

Solution (waaitg)

1495A - Diamond Miner

Idea: smg23333

Solution (smg23333)

1495B - Let's Go Hiking

Idea: waaitg

Solution (waaitg)

1495C - Garden of the Sun

Idea: Imakf

Solution (Imakf)

1495D - BFS Trees

Idea: waaitg, Daniel_yuan, isaf27

Solution (Daniel_yuan)

1495E - Qingshan and Daniel

Idea: Imakf

Solution (Imakf)

1495F - Squares

Idea: waaitg

Solution (waaitg)

• +160

 » 2 months ago, # |   +82 Speedforces.
•  » » 2 months ago, # ^ |   +56 More number of people would have solved Div2 D/ Div1 B if clear problem statement was made in starting itself .
•  » » » 2 months ago, # ^ |   0 Absolutely.
•  » » » » 2 months ago, # ^ |   +1 for problem 1B if the input is 1 1 10000000 1 shouldn't the answer be 10000001
•  » » 2 months ago, # ^ |   +1 I got WA in div2 C because i was not using set precision. Why is it so? Please explain!!
•  » » » 2 months ago, # ^ |   0 In the output format it is mentioned that answer should be correct upto atleast 9 decimals, so setprecision basically does this : http://www.cplusplus.com/reference/iomanip/setprecision/. Good Q I always used to blindly put fixed<
•  » » 2 months ago, # ^ |   +3 ауызынды жапшы сойлей береди екенсин
 » 2 months ago, # |   -12 Such a fast editorial! That's great! :)
•  » » 2 months ago, # ^ |   0 Sorry for making the second comment meaningless :(
 » 2 months ago, # |   -45 Second comment:)
•  » » 2 months ago, # ^ |   -50 Oh no I'm third :(
•  » » » 2 months ago, # ^ |   +71 Looking at my poor contribution, it's a painful lesson for me :(
•  » » 2 months ago, # ^ | ← Rev. 2 →   +62 Well, your comment isn't as meaningful as your handle.
 » 2 months ago, # |   +37 Task C have one max test???? My random solution got AC. So weak...
•  » » 2 months ago, # ^ |   +56 Hacked. Sorry for weak system test :(
•  » » » 2 months ago, # ^ |   +5 Savage
•  » » » 2 months ago, # ^ |   +30 I believe next time you will make them strong! Wish you luck.
 » 2 months ago, # |   0 why the solutions are not visible.... please look into this.
 » 2 months ago, # | ← Rev. 2 →   -19 Am I the only one who read $p_{x'}p_y$(Div2D/Div1B)
•  » » 2 months ago, # ^ | ← Rev. 2 →   +4 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, # ^ |   0 same with me bro.
•  » » 2 months ago, # ^ |   0 Me too, got 4 times WA for this.
•  » » » 2 months ago, # ^ |   0 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, # ^ |   +8 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, # ^ |   0 Thank you Sir/Ma'am!!!
•  » » 2 months ago, # ^ |   0 But solutions will be exact same except the l%2 condition in the last
•  » » 2 months ago, # ^ |   0 me too bro
•  » » 2 months ago, # ^ |   0 Same :(
•  » » 2 months ago, # ^ |   0 Oh,a sad story.
 » 2 months ago, # |   +14 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 →   0 Loved the contest interesting problems
 » 2 months ago, # |   +3 losing sleep due to bricking problem a. quite literally
 » 2 months ago, # |   +45 It will be better if the data of div2D/div1B are multi-tests.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 Why would it have been better? Is it because that would have allowed to fit more cases in pretests?
•  » » » 2 months ago, # ^ |   +11 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, # |   +26 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, # ^ |   0 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, # |   +4 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, # ^ |   0 Same thing happened to me too. But I couldn't fix it during the contest.
•  » » » 2 months ago, # ^ |   0 Same. I just got 6 TLE with correct algorithm just for that and lost the points for C.
•  » » 2 months ago, # ^ |   0 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, # ^ |   +12 It takes more time to take input as Double in C++ and even it takes more time to sort it.
•  » » 2 months ago, # ^ |   0 Me too,I suggest you use scanf but not use cin
•  » » 2 months ago, # ^ |   0 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 →   +1 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, # |   +1 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, # ^ |   0 i'm think for long double or double sort work very low.
•  » » » 2 months ago, # ^ |   0 I sorted with long long still got tle (took x,y input as double), the problem is with double input.
•  » » 2 months ago, # ^ |   0 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, # |   +3 can anyone explain to me why the answer in D is only 1 or 0?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +3 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 →   +3 Can you elaborate more? Why longest monotone is important here?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +3 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 →   0 I mis read the question 1495B.Thanks for the contest
•  » » 2 months ago, # ^ |   0 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, # ^ |   0 Yes, Thank you for the clarification sir.
 » 2 months ago, # |   -26 badest contest
 » 2 months ago, # |   +4 In Div_2_C109615476 : This solution was accepted. 109601607 : This one got me TLE. Can someone please help me understand why did I get tle?
•  » » 2 months ago, # ^ |   +5 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, # ^ |   +4 Thank You! I'll make a note of it.
 » 2 months ago, # |   0 What happened with the solution of 'BFS Trees'?
 » 2 months ago, # |   0 What is longest monotone segments?
•  » » 2 months ago, # ^ |   0 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, # |   0 Really too fast solution.
 » 2 months ago, # |   -10 Can Any One Help Mi That Why I Get TLE On Today's Problem C #include 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 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
•  » » 2 months ago, # ^ |   +1 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, # ^ |   +1 now it's accepted. thank's a lot i learn new thing and i will never forget it
•  » » » 2 months ago, # ^ |   +1 Could you please tell me that why double is slower than int(as sort).
•  » » » 2 months ago, # ^ |   +1 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, # |   0 I cant see solution for div1 a (smg2333) not enough rights
•  » » 2 months ago, # ^ |   0 Sorry, I'll fix it soon.
 » 2 months ago, # |   +4 Can anyone explain problem Div 2 D? The editorial is kind of overwhelming for me. Thank You in Advance!
•  » » 2 months ago, # ^ | ← Rev. 5 →   +5 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, # |   0 As fast as flash.
 » 2 months ago, # |   +3 It seems that the submission of F is not visible.
•  » » 2 months ago, # ^ |   +11 Sorry. Now it's fixed.
 » 2 months ago, # |   0 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, # ^ |   0 same with me. I think we contest had easy problems
 » 2 months ago, # |   0 many people who solved div2/C must not have thought of the solution in the way given in editorial..
 » 2 months ago, # |   +17 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, # ^ |   0 Absolutely
»
2 months ago, # |
0

# happyCoding

 » 2 months ago, # | ← Rev. 2 →   0 .
 » 2 months ago, # |   0 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, # ^ |   +8 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, # ^ |   0 Thanks
 » 2 months ago, # | ← Rev. 2 →   0 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, # |   0 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, # ^ |   0 Is there anything wrong with the spj?
•  » » » 2 months ago, # ^ |   +5 I guess you might get a single piece of data from multiple sets of data using C++ output, but pay attention to whether or not your code is affected by the fact that multiple sets of data are not cleared, which I do...
•  » » » » 2 months ago, # ^ |   0 Maybe I have the problem. You can see my submission. I can't find anything wrong.https://codeforces.com/contest/1496/submission/109645526
•  » » » » » 2 months ago, # ^ |   +8 Oho, isn't that the same mistake?If you look at the commit record, I just put a clean on your code and it was accepted.This is your code.This is my code. (I put a clean on your code)So it's important to remember to clear out multiple sets of data : )
•  » » » » » » 2 months ago, # ^ |   0 What a pity!/kk
•  » » 2 months ago, # ^ |   0 Sorry, I mean 1496E.
•  » » 2 months ago, # ^ |   0 @Imakf Can you show me the spj for the problem or just tell me why I'm wrong?
•  » » » 2 months ago, # ^ |   0 your graph didnt gurantee any two empty cells have no common points (neither edges nor corners).
•  » » » » 2 months ago, # ^ |   0 This isn't the input case but my answer!
•  » » » » » 2 months ago, # ^ |   +6 What a pity,maybe it's really his problem
•  » » 2 months ago, # ^ |   0 It is clearly a tree. In which submission you hacked the spj?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/contest/1496/submission/109646267I only swapped n and m and I got an accepted.https://codeforces.com/contest/1496/submission/109647174
 » 2 months ago, # |   +1 What is the difficulty of Div2 C as your opinion?
•  » » 2 months ago, # ^ |   +8 1300 As per me
•  » » » 2 months ago, # ^ |   +3 Nice guess
•  » » » » 2 months ago, # ^ |   +3 Thanks Sir!
 » 2 months ago, # | ← Rev. 2 →   0 For Div2 D /Div 1 B Why This Testcase giving ans=0 while ans should be 1N= 11 5 6 9 8 1 2 3 11 10 7 4
•  » » 2 months ago, # ^ |   0 ans=0 is right. why it should be 1 ? explain. there is no index where we can win.
•  » » » 2 months ago, # ^ |   0 For index =7 (0 based ) When value is 11
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +10 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, # ^ |   0 Oh sorry my bad I read condition for y wrong
•  » » » » » » 2 months ago, # ^ |   0 So many were did the same.
 » 2 months ago, # |   0 In Div.2C, why can we turn any point (x, y) to (|x|, |y|) without changing the answer?
•  » » 2 months ago, # ^ |   0 Because distance will still remain same since x^2 = (-x)^2
•  » » » 2 months ago, # ^ |   0 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, # ^ |   0 It is changing x to |x| that keeps the final answer correct.
•  » » » » » 2 months ago, # ^ |   0 Got it. I made a few points on paper and got the intuition for it.
 » 2 months ago, # |   0 when i am taking input in long double is giving tle https://codeforces.com/contest/1496/submission/109591967while long long int gets accepted https://codeforces.com/contest/1496/submission/109594626is 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, # ^ |   0 It takes more time to take input as Double in C++ and even it takes more time to sort it.
•  » » » 2 months ago, # ^ |   0 why is it so?
•  » » » » 2 months ago, # ^ |   0 Sorting a double number requires sort its decimal number which is very big
•  » » » » » 2 months ago, # ^ |   +3 Correct!
 » 2 months ago, # |   +13 I tried algebra bash for div2 C
 » 2 months ago, # |   0 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, # ^ |   0 иа иа иа мыктысын братишка ауызынды жапшы комегин болсын
 » 2 months ago, # |   0 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, # ^ |   +6 transform long double into double to print it
 » 2 months ago, # |   0 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 happening109668126 Code using double109668230 Code using int
•  » » 2 months ago, # ^ |   0 It takes more time to take input as Double in C++ and even it takes more time to sort it.
•  » » 2 months ago, # ^ |   0 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, # |   0 Thank you for turning me green again ;)
 » 2 months ago, # |   +1 The pretest for div2.D is too weak!
•  » » 2 months ago, # ^ |   0 Да ладно енди гана билдин ба
 » 2 months ago, # |   0 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, # ^ |   +13 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, # |   0 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, # ^ |   0 It's because that for the input array you used std::vector instead of std::vector 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 →   0 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, # |   +8 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, # ^ |   0 The same happened with me too.
 » 2 months ago, # |   0 For div1D, consider f(x, y), what if there are multiple shortest paths between x and y? Tutorial skipped this.
•  » » 2 months ago, # ^ |   0 In this case, answer is always 0?
•  » » » 2 months ago, # ^ |   0 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, # |   0 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, # ^ | ← Rev. 2 →   +5 1 4 3 ... ... .X. ... 
•  » » » 2 months ago, # ^ |   0 Oh, thanks!!I'm careless:(
 » 2 months ago, # |   0 Video Editorial For Problem C : https://www.youtube.com/watch?v=U1KOUnJwUAw Problem B : https://www.youtube.com/watch?v=nJk4SpIKWIQproblem A : https://www.youtube.com/watch?v=E4y0ZaF2wQA
 » 2 months ago, # |   +11 Someone kindly elaborate Div2F please!
 » 2 months ago, # | ← Rev. 2 →   +10 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, # ^ |   0 No. Consider a chessboard-like input grid.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 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 →   0 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 →   0 .X. XX. X.X .X. PS. nvm
•  » » » » » » 2 months ago, # ^ |   +21 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, # ^ |   0 This is nice I was also feeling it might fail for smaller chessboard!
 » 2 months ago, # | ← Rev. 3 →   0 Can anyone expain, why in Div.2 Problem D,testcase -->51 2 4 3 5answer is 0.
•  » » 2 months ago, # ^ |   +9 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, # |   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)
•  » » 2 months ago, # ^ |   0 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, # |   0 Can someone tell why this solution 109616067 is exceeding the time limit?
•  » » 2 months ago, # ^ |   +11 use scanf instead of cin and you will get ac 109754059
 » 2 months ago, # |   0 What will be the answer of Div2 D for 1 3 2 input. I think it should be 1.
•  » » 2 months ago, # ^ |   0 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 →   0 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, # |   0 Neither edges nor corners need a better explanation.
 » 2 months ago, # |   0 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, # ^ |   0 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 loses2nd case:Player1 chooses x = 2, Player2 chooses y = 1Player1 moves to x' = 3, Player2 moves to y' = 2Player1 cannot move (p[3] < p[2]) => Player1 losesPlayer1 chooses x = 2, Player2 chooses y = 3Player1 moves to x' = 1, Player2 moves to y' = 2Player1 cannot move (p[1] < p[2]) => Player1 loses3rd case:Player1 chooses x = 3, Player2 chooses y = 2 or y = 3 (it doesn't matter)Player1 cannot move (p[3] < p[2]) => Player1 losesConclusion: Player1 loses in all cases, this is why the answer is 0.
•  » » » 2 months ago, # ^ |   0 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 →   0 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 = 1Step 2: Player1 moves to position 3 => x = 3, Player2 moves to position 2 => y = 2Step 3: Player1 cannot move (p[3] < p[2]) => Player1 loses
•  » » » » » 2 months ago, # ^ |   0 Thank you Tudor67, your explanation was quite helpful.
 » 2 months ago, # |   +16 Em...i think the Div1.E's description has a small problem. On the 4th line of INPUT, it says \$p_{j-1}
•  » » 2 months ago, # ^ |   0 Now it's fixed. Thanks.
»
2 months ago, # |
0

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

# HAPPY CODING

 » 5 weeks ago, # |   0 Taking input as a double is slow in c++ (my learning from Div1 A).