kjain1810's blog

ICPC India Online Round 2019 Discussion
By kjain1810, history, 5 years ago, In English

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)

  • Vote: I like it
  • +113
  • Vote: I do not like it

Comments Comments (52)
| Write comment?
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Does there exist a "correct" solution for the SUMOR question, or is the question approximate?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +31 Vote: I do not like it

    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. -_-

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think either this is an approximate problem or the tester solution is wrong.

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      This doesn't work for 12,19,20 as pointed out above

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody share their approach for the Beautiful Partition Problem?

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve Pen pineapple problem. Please share approach if someone has solved it. Thanks.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.....

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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".

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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:)

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

    → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Btw what is the point of denying access to the contest page now?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes even an O(n^2) method is sufficient as per that question's constraints

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I find the problems?

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

When can we get the final ranklist?

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Is there any soft-copy of the questions?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When will result announce?(Approx Date)

My team ranked 471. Is there any chance that we can qualify for onsite round of kanpur region?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Depends on your rank in your college as well.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We were 1st in clg.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Then you will make it for sure.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
5 years ago, # |
  Vote: I like it -46 Vote: I do not like it

SUMOR problem should be removed. Ashishgup I would like to hear your views.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -36 Vote: I do not like it

    He gives zero fks to your username and this situation.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +66 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it +16 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

            → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

          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.

          → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Link to the rank list? I am getting access denied.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Naah they were just playing with it for a bit.

    → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

AnyOne who can help me with Grid Shuffle problem at least the approach

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    PS : Idea not tested.

    Hint : The problem is similar to finding walks of given length
    computing final answer
    → Reply