### kjain1810's blog

By kjain1810, history, 3 months 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

 » 3 months ago, # |   +15 Does there exist a "correct" solution for the SUMOR question, or is the question approximate?
•  » » 3 months 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. -_-
•  » » » 3 months ago, # ^ |   +19 Maybe they are trying to find a correct solution!
•  » » 3 months ago, # ^ |   +5 I think either this is an approximate problem or the tester solution is wrong.
 » 3 months 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.
•  » » 3 months 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.
•  » » » 3 months ago, # ^ |   +2 This doesn't work for 12,19,20 as pointed out above
•  » » » » 3 months 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.
 » 3 months ago, # |   0 Can somebody share their approach for the Beautiful Partition Problem?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +6 Prefix sum and then Longest Increasing Subsequence
•  » » » 3 months ago, # ^ |   0 Does it involve use of AVL trees?
•  » » » » 3 months ago, # ^ |   0 No
•  » » » » 3 months ago, # ^ |   0 Instead use segment tree.
•  » » » 3 months ago, # ^ |   0 Isn't longest increasing subsequence n^2
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 You can find it in O(nlogn) using Segment Tree or Fenwick Treen or Binary Search.
•  » » » » » 6 weeks ago, # ^ |   0 How does longest increasing subsequence for prefix sum give the answer.Can u explain please?
 » 3 months ago, # |   +4 How to solve Pen pineapple problem. Please share approach if someone has solved it. Thanks.
 » 3 months 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.....
•  » » 3 months 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".
•  » » » 3 months 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:)
•  » » » » 3 months ago, # ^ |   0
•  » » » » » 3 months 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.
•  » » » » » 3 months ago, # ^ |   0 The page isn't opening:(
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 The idea was fairly simple. I'd like to know how to implement it within the time constraints.
•  » » 3 months 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
•  » » 3 months 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)
 » 3 months ago, # |   0 Any idea where can we test our code now? contest page isn't opening. Thanks.
 » 3 months ago, # |   +9 Btw what is the point of denying access to the contest page now?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8
 » 3 months 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.
•  » » 3 months 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
•  » » » 3 months ago, # ^ |   0 Thank's for the help.
•  » » » 3 months 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.
•  » » » » 3 months ago, # ^ |   0 Yes even an O(n^2) method is sufficient as per that question's constraints
 » 3 months ago, # |   0 Where can I find the problems?
•  » » 3 months ago, # ^ |   0 here, though they are in private mode as of now
•  » » » 3 months ago, # ^ |   0 Restricted :(
 » 3 months ago, # |   +5 When can we get the final ranklist?
•  » » 3 months ago, # ^ |   0 Don't know about ranklist but surely you won't get any answer here.
•  » » 3 months ago, # ^ |   +1
 » 3 months ago, # |   0 can anyone check my code for moving segment problem, i can't find any problem in my code.https://ideone.com/Dusk4t
 » 3 months ago, # |   +12 Is there any soft-copy of the questions?
 » 3 months 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?
•  » » 3 months ago, # ^ |   0 Depends on your rank in your college as well.
•  » » » 3 months ago, # ^ |   0 We were 1st in clg.
•  » » » » 3 months ago, # ^ |   0 Then you will make it for sure.
•  » » » » » 3 months 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?
•  » » » » » » 3 months 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.
 » 3 months ago, # |   -46 SUMOR problem should be removed. Ashishgup I would like to hear your views.
•  » » 3 months ago, # ^ |   -36 He gives zero fks to your username and this situation.
•  » » » 3 months 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.
•  » » » » 3 months 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.
•  » » » » » 3 months 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?
•  » » » » » » 3 months 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.
•  » » » » » 3 months 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.
•  » » » 3 months ago, # ^ |   -46 'He gives zero fks to your username and this situation.' I don't think so.
 » 3 months 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
•  » » 3 months ago, # ^ |   +1 Link to the rank list? I am getting access denied.
•  » » 3 months ago, # ^ |   +33 Naah they were just playing with it for a bit.
 » 6 weeks ago, # |   +2 AnyOne who can help me with Grid Shuffle problem at least the approach
•  » » 6 weeks 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.}$
•  » » » 6 weeks ago, # ^ |   0 Have you tried this also on the test cases ?