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)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | SecondThread | 150 |
| 8 | -is-this-fft- | 149 |
| 9 | pajenegod | 145 |
| 10 | BledDest | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 16.04.2024 19:50:08 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Does there exist a "correct" solution for the SUMOR question, or is the question approximate?
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:
1
3
20 12 19
Admins are also not responding. Don't know. -_-
Maybe they are trying to find a correct solution!
Is the answer to this test case:
81
1 2 3
Just curious...
I think either this is an approximate problem or the tester solution is wrong.
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.
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.
This doesn't work for 12,19,20 as pointed out above
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.
Can somebody share their approach for the Beautiful Partition Problem?
Prefix sum and then Longest Increasing Subsequence
Does it involve use of AVL trees?
No
Instead use segment tree.
How to solve Pen pineapple problem. Please share approach if someone has solved it. Thanks.
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.....
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".
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:)
https://ideone.com/3OkFmh
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.
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)
Btw what is the point of denying access to the contest page now?
AnonymousBunny
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.
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 on
Check them all and get the minimum length.
you will get the answer
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.
Yes even an O(n^2) method is sufficient as per that question's constraints
Where can I find the problems?
here, though they are in private mode as of now
Restricted :(
When can we get the final ranklist?
Here it is:-
https://www.codechef.com/public/rankings/ICPCIN19
Is there any soft-copy of the questions?
When will result announce?(Approx Date)
My team ranked 471. Is there any chance that we can qualify for onsite round of kanpur region?
Depends on your rank in your college as well.
We were 1st in clg.
Then you will make it for sure.
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?
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.
SUMOR problem should be removed. Ashishgup I would like to hear your views.
He gives zero fks to your username and this situation.
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.
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.
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?
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.
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.
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
Link to the rank list? I am getting access denied.
Naah they were just playing with it for a bit.
AnyOne who can help me with Grid Shuffle problem at least the approach
PS : Idea not tested.
Say $$$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.
If 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.} $$$
Have you tried this also on the test cases ?