### kjain1810's blog

By kjain1810, history, 2 years ago,

This blog is to discuss the problems of ICPC India Online round 2019 held today.

I think the online round this year was substantially better than previous years (except for the weak test data of Beautiful OR problem)

• +113

 » 2 years ago, # |   +15 Does there exist a "correct" solution for the SUMOR question, or is the question approximate?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +31 It seems like an approximate question to me again. Wasted 3 hours for the same shit. Again this year. This case will fail almost every solution submitted for that question: 1320 12 19Admins are also not responding. Don't know. -_-
•  » » » 2 years ago, # ^ |   +19 Maybe they are trying to find a correct solution!
•  » » » 16 months ago, # ^ |   0 Is the answer to this test case:811 2 3Just curious...
•  » » 2 years ago, # ^ |   +5 I think either this is an approximate problem or the tester solution is wrong.
 » 2 years ago, # |   +3 What idea did the top teams use to solve SumOr problem? My team got TLE(probably due to use of set and Unordered set). Time complexity was nlogn.
•  » » 2 years ago, # ^ |   0 We didn't solve the SumOr problem but a team from my institute ranked 17 solved that problem by reversing it i.e they reconstructed the solution from the end in last you will try to have the largest number and then continue adding elements until the total OR reaches that of the whole array. Elements will be added in such a way so that the value gained by order is maximum. After we reach a point where the number we have, total OR equal to that of the array we can add rest of the number in any order. Reverse the process and print it you will get the answer. We tried doing same for bits got WA didn't get much time for correction.
•  » » » 2 years ago, # ^ |   +2 This doesn't work for 12,19,20 as pointed out above
•  » » » » 2 years ago, # ^ |   +1 Well I just shared the method which worked for them and for this test case their solution works fine I guess, 19,12 and then remove 20.
 » 2 years ago, # |   0 Can somebody share their approach for the Beautiful Partition Problem?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 Prefix sum and then Longest Increasing Subsequence
•  » » » 2 years ago, # ^ |   0 Does it involve use of AVL trees?
•  » » » » 2 years ago, # ^ |   0 No
•  » » » » 2 years ago, # ^ |   0 Instead use segment tree.
•  » » » 2 years ago, # ^ |   0 Isn't longest increasing subsequence n^2
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 You can find it in O(nlogn) using Segment Tree or Fenwick Treen or Binary Search.
•  » » » » » 2 years ago, # ^ |   0 How does longest increasing subsequence for prefix sum give the answer.Can u explain please?
 » 2 years ago, # |   +4 How to solve Pen pineapple problem. Please share approach if someone has solved it. Thanks.
 » 2 years ago, # |   0 Where can I know the solutions of ICPC 2019 Online Round. I wasted my 2 hours on the moving segment question. Now I want the explaination and solution of moving segment as I want to know where I messed up in my approach. Can someone help me out with his solution.....
•  » » 2 years ago, # ^ |   0 Suppose the segments have different speed, then after t = 10^10000, whatever direction we give them, they will never overlap. The problem can only arise when segments have the same speed. Now suppose two segments are not overlapping, then they will never overlap at t as they will move parallelly or oppositely. Suppose two segments are overlapping with each other, then we can manage to send them in opposite directions such that they don't overlap. The only case where the problem will arise is when 3 or more segments overlap with the same speed. Note that 3 segments overlapping means that all should overlap with each other pairwise. In that case, the answer will be "no", otherwise it's "yes".
•  » » » 2 years ago, # ^ |   0 I find the exact same logic to find the solution of this problem by discussing with my teammates when the 45 minutes time is remaining in the contest, but I failed in how to implement this logic in a code — How to check in a set of segments having constant speed and atleast three of them have the common overlapping on a point or in a given range? If possible send me the code of the implementation of the same logic:)
•  » » » » 2 years ago, # ^ |   0
•  » » » » » 2 years ago, # ^ |   0 Thanks for providing the code bro.We had the same logic but our code gave us wrong answer and we end up unable to find the left out the missing test case.
•  » » » » » 2 years ago, # ^ |   0 The page isn't opening:(
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 The idea was fairly simple. I'd like to know how to implement it within the time constraints.
•  » » 2 years ago, # ^ |   0 The time given can be considered as infinite time ,hence we only have to consider segments with same velocity .So maintain a map with velocity as key and vector of pairs (l,r) as value. Sort these vectors after all insertions. Create a function for checking overlapping.Traverse and maintain a local bool array for direction initialized with false or true whatever . If length is < 2. nothing to worry. <- -> If length is > 2. Algo : IF : current is overlapping with previous then reverse the direction of segment check no other segment above that should not have same direction with overlapping .If anyone segment found answer will be NO. Else : Assign same direction as of previous and carry on.If no violations occur answer will be YES. Solution
•  » » 2 years ago, # ^ |   +1 We used graphs. Consider the segments as vertices. For every pair of overlapping segments with same speed, we add an edge between the corresponding vertices. Then, just check whether the graph is bipartite or not. If it is, then the answer is "YES", because the two partitions can be sent in opposite directions, otherwise answer is "NO". Time complexity is O(N^2)
 » 2 years ago, # |   0 Any idea where can we test our code now? contest page isn't opening. Thanks.
 » 2 years ago, # |   +9 Btw what is the point of denying access to the contest page now?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8
 » 2 years ago, # |   0 Can somebody share their approach for shortest palindrome superstring. Here is what I tried to do, I first checked if either of the strings contains the other string or the reversed form of the other string as a substring or not. If anyone does, then answer can be obtained by simply converting the string(that contains the other string)to palindrome, and if not then i concatanated both the strings and converted the resultant string into palindrome.For conversion into palindrome I considered both the cases, first appending reversed form of string at the end of the string and using KMP algo to find the longest prefix thats also a suffix and sustracting its length form the the total length and then same I did by appending the reverse string at the start, From the 2 results I chosed the minimum one. For example: s="abb" t="abb" As 1 contains 2 so s1=abbbba and s2=bbaabb,so longest prefix that's also suffix in case 1 is of length 1 and in case 2 it is 2 ans will be min(6-1,6-2)=4. Thank's in advance.
•  » » 2 years ago, # ^ |   0 you need not concatenate the two strings you had to find the super string of the two strings like "abcd" and "bcde" will have the resulting string as "abcde" and you have to convert this string into palindrome. So there were about 8 cases to find the superstring A B , B A , R_A B, B R_A and so onCheck them all and get the minimum length.you will get the answer
•  » » » 2 years ago, # ^ |   0 Thank's for the help.
•  » » » 2 years ago, # ^ |   0 Is there an efficient way of calculating the resultant string? What I am thinking of is using KMP for finding longest suffix which is also a prefix.
•  » » » » 2 years ago, # ^ |   0 Yes even an O(n^2) method is sufficient as per that question's constraints
 » 2 years ago, # |   0 Where can I find the problems?
•  » » 2 years ago, # ^ |   0 here, though they are in private mode as of now
•  » » » 2 years ago, # ^ |   0 Restricted :(
 » 2 years ago, # |   +5 When can we get the final ranklist?
•  » » 2 years ago, # ^ |   0 Don't know about ranklist but surely you won't get any answer here.
•  » » 2 years ago, # ^ |   +1
 » 2 years ago, # |   0 can anyone check my code for moving segment problem, i can't find any problem in my code.https://ideone.com/Dusk4t
 » 2 years ago, # |   +12 Is there any soft-copy of the questions?
•  » » 2 years ago, # ^ |   0
 » 2 years ago, # | ← Rev. 2 →   0 When will result announce?(Approx Date)My team ranked 471. Is there any chance that we can qualify for onsite round of kanpur region?
•  » » 2 years ago, # ^ |   0 Depends on your rank in your college as well.
•  » » » 2 years ago, # ^ |   0 We were 1st in clg.
•  » » » » 2 years ago, # ^ |   0 Then you will make it for sure.
•  » » » » » 2 years ago, # ^ |   0 and my rank is 250 and the college rank is 6. Is there any chance that we can qualify for the onsite round of Kanpur or Amritapuri region?
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 It depends on the choices of rest of the teams from your college. Unless you are very lucky with the sites, the chances are very low.
 » 2 years ago, # |   -46 SUMOR problem should be removed. Ashishgup I would like to hear your views.
•  » » 2 years ago, # ^ |   -36 He gives zero fks to your username and this situation.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +66 Lol, I refrained from commenting on it because people think I'm whining, and to be honest — my team isn't affected in any way by removal or not of the question:However, from a logical standpoint — it should be removed obviously. In my team, for this question, I wrote a bruteforce (n! * n^2) code to check the logic (since we were skeptical of greedy solution), and we generated many testcases with T = 10 & N = 6, and there were testcases we weren't able to pass — so we kept changing solutions and finally submitted a code similar to the intended wrong solution. My point is, it's not fair to penalize teams for not submitting incorrect solutions just because they found the counter-case beforehand or were sure of their solution not passing.
•  » » » » 2 years ago, # ^ |   +11 We submitted codes to 2 problem in last 3 minutes, without much testing as we were running out of time and unsurprisingly we got WA in both. We gave time to come up with similar intended wrong solution for SUMOR but had this problem not been in problemset, it is pretty likely that we would have got last 2 problems AC instead.Point being, it is not obvious to simply discard the problem and it is going to remain unfortunate incident whether or not this problem is discarded.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +16 What about teams who didn't even get much time to think about other problems because they got a counter case for SUMOR? Your team atleast had some time to think of solutions to other problems and even got time to code up some solution to those other problems which passed the sample case. Many teams were stuck on SUMOR because it had a large number of accepted submissions.I agree that it will remain an unfortunate incident, but it is now choosing between two options: the first option is unfair and the second option is more unfair. What would you choose?
•  » » » » » » 2 years ago, # ^ |   +3 ps: whether or not problem is discarded, our qualification remains unaffected. Rather than discussing which of two evils is less, I would rather ask if it is possible to push organizers into increasing total seats as deciding problem is flawed? They could possibly make arrangements as there is quite some time for onsite regionals.
•  » » » » » 2 years ago, # ^ |   +20 I think that the most fair course of action would be to consider two ranklists — one with teams who solved the question, and one with teams who didn't — separately, and do seat allotment (with current or increased seats) according to them.
•  » » » 2 years ago, # ^ |   -46 'He gives zero fks to your username and this situation.' I don't think so.
 » 2 years ago, # | ← Rev. 4 →   +6 They have removed SUMOR (or rejudged) and ranklist has been updated!!UPD: They have now restricted the access to the ranklist.UPD2: They added the problem again
•  » » 2 years ago, # ^ |   +1 Link to the rank list? I am getting access denied.
•  » » 2 years ago, # ^ |   +33 Naah they were just playing with it for a bit.
 » 2 years ago, # |   +2 AnyOne who can help me with Grid Shuffle problem at least the approach
•  » » 2 years ago, # ^ |   0 PS : Idea not tested. Hint : The problem is similar to finding walks of given lengthSay $x =$ value at $(r, c)$. Let's track the position of point with value $x$ during the operations. If neither the column, nor row containing x is chosen then the position remains same, otherwise it changes . The probability of first and latter are $1 - \frac{2}{n + m}$ and $\frac{2}{n + m}$ respectively. Now see that in latter operations the point moves and end at the same position making a closed walk. computing final answerIf there are $i$ operations which do not change the position of $x$.Then probability = ${k \choose i} (1 - \frac{2}{n + m})^i (\frac{2}{n + m})^{k - i}(\text{Probability that walk of length k - i is closed)}$. The latter term in the expression can be calculated in quadratic time by a dp, $dp[i][k] = \text{number of walks of length k, with i, k-i moves in x and y direction respectively.}$
•  » » » 2 years ago, # ^ |   0 Have you tried this also on the test cases ?
 » 20 months ago, # | ← Rev. 2 →   0 Can anyone help me on Moving Segment? I've submitted multiple times overcoming almost all test cases and this is my final code ` Code#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b))) void solve() { int n; cin >> n; int flag=0; vector>> v(n); repi(n) {int l,r,val; cin >> l>>r >> val; v[i] = MP(val,MP(l,r)); } unordered_map> pos; unordered_map> neg; for(int i=0;isecond.F,it->second.S) || inrange(b,it->second.F,it->second.S)|| inrange(it->second.F,a,b) || inrange(it->second.S,a,b)){ if(min(a,b)==max(it->second.F,it->second.S)||max(a,b)==min(it->second.F,it->second.S)){ pos[key] = MP(min(a,it->second.F),max(b,it->second.S)); } else { auto it1 = neg.find(key); if(it1!=neg.end()){ if(inrange(a,it1->second.F,it1->second.S) || inrange(b,it1->second.F,it1->second.S)||inrange(it1->second.F,a,b) || inrange(it1->second.S,a,b)){ if(min(a,b)==max(it1->second.F,it1->second.S)||max(a,b)==min(it1->second.F,it1->second.S)){ neg[key] = MP(min(a,it1->second.F),max(b,it1->second.S)); } else { cout << "NO"; return; } } else { neg[key] = MP(min(a,it1->second.F),max(b,it1->second.S)); } } else { neg[key] = MP(a,b); } } } else { pos[key] = MP(min(a,it->second.F),max(b,it->second.S)); } } else { pos[key] = MP(a,b); } } cout << "YES"; } Code explain~~~~~ Used to maps to keep info of all the segments I'm sending to pos/neg. Key is velocity while value is the range(l,r). First inner loop checkes if there is an intersecting segmenting of same speed out of all the segments of same speed going to positive, if yes then checks same for negative, if yess too then NO. Otherwise place the segment(l,r) respectively in pos/neg map. ~~~~~~Could anyone provide harder testcase?