Блог пользователя kjain1810

Автор kjain1810, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody share their approach for the Beautiful Partition Problem?

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 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.....

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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".

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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:)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +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)

»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 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 on

    Check them all and get the minimum length.

    you will get the answer

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Where can I find the problems?

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

When can we get the final ranklist?

»
5 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Is there any soft-copy of the questions?

»
5 лет назад, # |
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?

»
5 лет назад, # |
  Проголосовать: нравится -46 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -36 Проголосовать: не нравится

    He gives zero fks to your username and this situation.

    • »
      »
      »
      5 лет назад, # ^ |
      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          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?

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +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.

»
5 лет назад, # |
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

»
5 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    PS : Idea not tested.

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