Ashishgup's blog

ICPC Amritapuri 2020 Regionals — Live Updates
By Ashishgup, 3 years ago, In English

Hello everyone!

T1duS, kshitij_sodani and I will be capturing the live updates of the Amritapuri 2020 Regionals, for teams to later refer to first-solves and the state of ranklist after various times. It is inspired by similar blogs in the past, like this, for example.

Important Information:

Announcements:

  • All problems have a memory limit of 1GB, and solutions that exceed this would be marked as RTE instead of MLE due to some memory usage issues.

Live Updates:

  • 17:50 — The contest is delayed by 30 minutes to 18:30, to ensure that everything is working fine.

  • 18:30 — Contest starts! There are a total of 11 problems for the round. We have our first submission of the contest less than 1 minute in, but compilation error :'(

  • 18:32 — Team Agla_ICPC_Phod_Denge from Indian Institute of Technology — Varanasi is the first team to solve the problem Thanos the Teacher to claim rank 1. (Ranklist)

  • 18:40 — 310 teams have now solved Thanos the Teacher. Team Pay Attention from Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar is the first team to solve the problem The Invasion of Balaji. (Ranklist) Balajiganapathi has been successfully invaded.

  • 18:50: Team ShaamTakKhelenge from Indian Institute of Technology — Bombay is the first team to solve Hackerland. (Ranklist). Not having solved The invasion of Balaji, they claim the 18th spot.

  • 18:55: Team ShaamTakKhelenge from Indian Institute of Technology — Bombay claims Rank 1 by solving 3 problems! (Ranklist)

  • 19:00: Team Pay Attention from Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar has claimed the first spot by having lower penalty with 3 problems solved! 5 teams have solved the same three problems. (Ranklist)

  • 19:05: Team That's what she said (brownie points for the name) becomes the first team to solve Peace, Freedom, Justice, and Security and claims rank 4. Quite a few teams in the top 20 seem to be getting penalties on problems as well! (Ranklist). Team TeemCheems becomes the second team to solve Problem D, but is at rank 125 because they have only solved this problem along with the easiest problem!

  • 19:20: Holy Trinity claims the first rank by solving DFS Sequence, also being the first team to solve that problem. Many other teams are still stuck at 3 solves. There are now 5 distinct problems that have been solved by atleast 1 team. This is the state of the scoreboard: Ranklist.

  • 19:30 It's 1 hour into the contest. There is no change in the top rank, but we have 2 new distinct problems solved: Team ACassins from Indian Institute of Technology — Kanpur solved Lord of the Group. Team Amigos from solved Blizzard Blitz. This takes the count of distinct problems solved to 7. Problems dashboard after 1 hour.

Ranklist after 1 hour

  • 20:00: 1 hour 30 minutes into the contest, Area151 from Indian Institute of Technology — Roorkee claim the top spot by solving Blizzard Blitz, with ACassins from Indian Institute of Technology — Kanpur following closely solving Lord of the Group, which takes them both to 5 solved problems! All other teams in top 10 have solved 4 problems. (Ranklist)

  • 20:30: 2 hours into the contest, Area151 from Indian Institute of Technology — Roorkee retain their first spot and consolidate it for the near future by solving the 6th problem! Cheese Maggi joins ACassins with 5 solved problems to claim the third spot, while all others in top 20 have 4 solved problems. Problems Dashboard after 2 hours.

Ranklist after 2 hours

  • 20:50: ACAssins solve Peace to reach the 2nd rank. GuptCoders and EvilGenuines solve 5th problems as well, to rise through the ranks! 4 problems still remain unsolved. (Ranklist)

  • 21:30: The ranklist is now frozen. Cheese_Maggi from Indian Institute of Technology — Guwahati solves their 6th problem 15 seconds before the ranklist is frozen to reach rank 3! Pay Attention from Dhirubhai Ambani Institute of Information and Communication Technology, Gandhinagar is the first team to solve The Lag which takes them to Rank 6, and puts the number of distinct problems solved at 8. 3 problems still remain unsolved. We will update the future ranks/first problem solves (if any) after the results are announced! Problem dashboard after 3 hours.

Ranklist after 3 hours

Update: The final ranklist after plagiarism checks, etc, will tentatively be revealed along with winners at the discussion / ceremony on 21st August, Saturday. (Source)

Update 2: To not keep the contestants waiting, we have decided to release the ranklist early. Congratulation to all the teams!

Update 3: ICPC Asia Amritapuri Site Regional Round Problem Discussion

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

Comments Comments (59)
| Write comment?
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

We'll be posting the setters'/testers' pre-round predictions after the round too.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +67 Vote: I do not like it

Credits: Balajiganapathi

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +49 Vote: I do not like it

will the final scoreboard be revealed today only ???

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

    It will be revealed along with winners at the discussion / ceremony on 21st August, Saturday.

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

      How many teams would qualify for the world finals?

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

will the updated ranklist come at 10:30?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +67 Vote: I do not like it

How many of you guys solved 7+ questions? We got 7 solves (thayir_sadam_lovers: Lain, lolok123 and I).

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +147 Vote: I do not like it

Removed

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

    how many you guys did?

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

    Am I the only one who doesn't mind a good story? I feel it is a lazy excuse if someone says they did not solve a problem just because of long statements :)

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

      statement was in English and who is native speaker here, Statement should be made crystal clear not a complex story which is difficult to understand for many :)

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

      I don't mind a good story but in this contest the stories were: boring, annoying, unnecessary, irritating, bad, confusing, lengthy, misdirecting and (in some problems) counterintuitive.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it -53 Vote: I do not like it

        Personally I always like good story based problems. I would feel giving a contest with 11 problems just of the form "Given a tree blah blah", "Given an array blah blah" very bland and boring.

        Speaking as a chief judge, there are many authors on the team from different backgrounds and with different views. Some like having stories in their problems; and some don't. I don't like to force an author to have / not have stories. I leave it up to their judgement. As long as I have participated, been on setting panel and been chief judge at ICPC Amritapuri, there has always been stories in the problems :) The feedback was always positive about those. I think this might be a new trend over last couple of years in the community of not wanting stories.

        Coming to your point: "boring, annoying, unnecessary, irritating, bad..., lengthy" -> Notice how all are very subjective terms and hence difficult to argue against. While some testers did suggest having no stories, that was more on general principle than on the stories being boring or anything.

        "confusing,..misdirecting and (in some problems) counterintuitive" -> The intent behind stories, when present, are not to make it misleading (or as the meme above seems to imply — reduce ACs for the problem — that couldn't be more wrong. I highly doubt the solved counts would be any different if we removed the stories.). We have a few proof readers go through the statements to ensure this and none gave feedback that the statements were misdirecting. So I have to disagree with this point.

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

          Personally I always like good story based problems

          When you are creating contest you should think from majority perspective. Most people like short and to the point statements. There are better things to read compared to Duc de Puce, Duc Beauregard, and Duc Truffe.

          It's contest organizer/setter responsibility to talk with lot of people and read comments on competitive programming platforms to know what people like and not just enforce your own thoughts.

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

            I know my responsibility. Did you read my comment in full?

            ...there has always been stories in the problems :) The feedback was always positive about those. I think this might be a new trend over last couple of years in the community of not wanting stories

            Also, we would really, really love to have the newly graduated contestants from this year join the setting/testing team for the next ICPC contest. And if they want to set short statements without stories, they are most welcome to do so :)

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

          "misdirecting"

          Let's take G for example. If I read the whole story carefully. There are some gamers connected in form of a tree and during a maintenance day "a subset" of tree edges is marked as laggy. and so on

          That's what one would understand from the story. Later you plainly tell us that only 2 edges per maintenance day.

          That's exactly what I meant by "unnecessary" also. The story fails to explain the key details of the problem. At least include it in the story that somehow it's not possible to repair more than 2 wires in a day or something.

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

            Moreover... Here's a paragraph:

            "Formally, we say that the connection between districts i and j is smooth if there is a series of wires starting from i and ending at j such that none of the wires is under repair. Otherwise, it is laggy. Under a laggy connection, gamers on districts i and j unfortunately have to be polite to each other, even though the lag is really to blame."

            Notice how the statement which starts with formally leads to something that is totally useless to the problem. When I read this part, I got confused and started figuring out if there is something related to blame.

            AT LEAST, change the paragraph after a formal statement before adding useless bullshit.

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

              Don't waste your time in suggesting these people. They would just downvote and won't take feedback constructively. I mean just see in codeforces contest announcement comment section how much people dislike stories and useless statements. Still they ignored. Don't know which world they are living in.

              If we see regionals mirror contests on codeforces we can see they have to the point and short statements.

              I mean what orgasm on gets from writing Duc de Puce, Duc Beauregard, and Duc Truffe ?

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

          I think you should consider this thumb rule- Only add parts of story in statement which you would use to explain the problem to someone else.

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

    I don't like long statements myself and did raise this point while testing.I heard that long statements were used because thats similar in style to ICPC World Finals

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

      You should try Cat though.It is intended to be the hardest problem in this set.It has an elegant solution.Maybe around div1e difficulty

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

        Can you please tell what's wrong in this approach in problem "the cat"

        At first just check answer will be zero or not-

        -> Make decomposition DAG by merging all SCC into single nodes.

        -> Check ans is zero for a DAG or not as everything is connected number of edges should be n-1 if n=number of nodes in new graph

        -> check ans is coming zero from any single SCC by taking all SCC individually and making a dfs tree then there should be at most 1 back edge covering any other forward edge and there should not be any useless edge going from ancestor to children.

        -> Last part if answer is not zero then calculate the number of ways: In the DAG For any node count x=indegree and y=outdegree Then number of ways will be -Summation of C(x,i)*C(y,i)*factorial[i] 0<=i<=min(x,y) and multiply this result for all nodes in the DAG.

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

          "-> check ans is coming zero from any single SCC by taking all SCC individually and making a dfs tree then there should be at most 1 back edge covering any other forward edge and there should not be any useless edge going from ancestor to children."

          Replace atmost 1 back edge with exactly one back edge.There should not be any cross edges also

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

          "-> Last part if answer is not zero then calculate the number of ways: In the DAG For any node count x=indegree and y=outdegree Then number of ways will be -Summation of C(x,i)*C(y,i)*factorial[i] 0<=i<=min(x,y) and multiply this result for all nodes in the DAG."

          We take the graph with edges (u,v) such that u,v in different scc(not edges between compressed scc graph).Solve for each tree(in undirected) form seperately and multiply the answer

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

      Blizzard was intended to a easy problem but teams got misleaded by the scoreboard(only 4ish solves before freeze) into trying dfs sequences instead which is way harder than blizzard.

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

        Lol, I read that problem now and it seems very easy problem compared to dfs sequences, maybe some powers of 3 and slight case work.

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

          That's what. Most of the times, teams get mislead by current scoreboard. If the difficulty were known or sorted in order, our predictions would have been close. :(

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

Did anyone solve HackerLand? If yes, can you explain your approach?

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

how to solve D Peace, Freedom, Justice, and Security

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

    It is always optimal to select one point on origin and other on X-axis and then find the third point, you can simply try all permutations for selecting the order of points.

    Diag for sample

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

      never mind , I am unable to get though. But did you mean?

      fix the base of the triangle , then binary search for maximum height or something else?

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

        You can draw the locus of third point based on the earlier two points, if there is intersection you get the third point, subsequently permute on the order.

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

          okay thanks!

          I guess I missed some high school math classes xd!

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

      Can you look at this code please.. https://onlinegdb.com/eM719pYcP

      I have taken the minimum length on the x axis.

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

How many teams are expected to be selected after this round ?

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

Hello. This is a report of injustice. My apologies for the poor writing, as my English is not very good and I have to go through translation.

One of the teams asked me for the solution during the contest. I also didn't know that this contest existed, so I gave them the solution. In addition to that, there was a problem that I had been asked to solve and code before that was held in this contest. problem: https://codedrills.io/contests/icpc-amritapuri-2020-preliminary-round/problems/strings-and-lis code: https://github.com/kiyoshi0205/-/blob/main/problem2.cpp

Unfortunately, I don't know their real name, only their email address and account ( https://codeforces.net/profile/anachor_99 ). I am willing to disclose my email address to the administration if necessary. If you need that information, please contact me on codeforces.

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

How to solve the problem The Invasion of Balaji? We failed after trying it for a long time.

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

    Take the input from about the training of each candidate as an pair from with its index. It is optimal to take only one T[i] and do it q times. Prepare two more arrays, say left and right which would store the best possible sum while coming from left(and from right) and including that element. If this increase (T[i] > 0), For each of those index find the max value by U[i] + (T[i]>0)?(T[i]*q):0 + (i>0)?left[i-1]:0 + (i<n-1)?right[i+1]:0

    Time complexity: O(n) [You do Linear time preprocessing to create left and right + Final Traversal through T with O(1) usage of left and right]

    Would love to see how others solved it.

    eg. U = [-3 2 1 -20 3] left = [0, 2, 3, 0, 3] right = [0,3,1,0,3]

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

    You can see that in every optimal case we can use 2nd operation on a single index q time (or will not use at all). Now iterate on every index from 0 to n — 1 and find maximum ans if we will use 2nd opertion q times on this index (or will not use at all). After performing 2nd operation on this index we have to take subarray with maximum sum starting from next index (Or 0 if all subarrays have negative sum). Same way we have to take suffix subarray ending at previous index with maximum sum. Subarray with maximum sum starting at an index can be found in O(1) by using suffix array sum and suffix minimum array i.e if you have to find maximum sum subarray starting at index i it can be written as sum[i... n — 1] — min(sum[i... n — 1], sum[i + 1 ...., n — 1], sum[i+2.... n — 1], sum[n-2.. n — 1], sum[n-1]). Link

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

Hey Balajiganapathi, any updates about the T-shirts?

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

How to solve problem A — A Cubical Romance? I read the only accepted code for this problem but didn't understand what they've done.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the approach to solve hackerland? Didn't get it during the contest

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

What is the main purpose behind putting the problems in unsorted way(random difficulty order)? (seriously asking)

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

Are we getting a T-shirt or goodies for solving at least 1 problem in (India ICPC — Amritapuri 2020 Regionals)?

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

    Same doubt.The mail initially said we'll be getting a t shirt . But then no more talk about goodies .

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

Any hints for the lag?

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

ICPC Asia Amritapuri Site Regional Round Problem Discussion

→ Reply