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:
- Rank List (Scoreboard): https://codedrills.io/contests/icpc-amritapuri-2020-regional-round/scoreboard
- Contest Page: https://codedrills.io/contests/icpc-amritapuri-2020-regional-round
- Contest Blog: https://codeforces.net/blog/entry/93818
- There are 726 qualified teams who will be competing for the world finals slots from this regional!
- Contest Duration: 4 hours.
- Tentative Start Time: 18:30 IST
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.
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.
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.
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
- Timing: Today 6 PM IST.
- Link: https://zoom.us/j/96036709555
We'll be posting the setters'/testers' pre-round predictions after the round too.
Credits: Balajiganapathi
will the final scoreboard be revealed today only ???
It will be revealed along with winners at the discussion / ceremony on 21st August, Saturday.
How many teams would qualify for the world finals?
will the updated ranklist come at 10:30?
How many of you guys solved 7+ questions? We got 7 solves (thayir_sadam_lovers: Lain, lolok123 and I).
orz
:orz:
orz :)
Removed
how many you guys did?
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 :)
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 :)
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.
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.
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.
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 :)
"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.
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.
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 ?
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.
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
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
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.
"-> 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
"-> 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
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.
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.
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. :(
deleted
Did anyone solve HackerLand? If yes, can you explain your approach?
DSU find prime factors of a node, group all the nodes which are having at least one prime factor in common, .
Finding these components and merging optimally will give the optimal answer.
Just handle case when 1 is present in the array one or more times.
Can you give the solution?
https://codedrills.io/submissions/279107
A link to your submission may be to clarify things.
https://codedrills.io/submissions/279107
how to solve D Peace, Freedom, Justice, and Security
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
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?
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.
okay thanks!
I guess I missed some high school math classes xd!
Can you look at this code please.. https://onlinegdb.com/eM719pYcP
I have taken the minimum length on the x axis.
How many teams are expected to be selected after this round ?
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.
How to solve the problem The Invasion of Balaji? We failed after trying it for a long time.
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]
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
Hey Balajiganapathi, any updates about the T-shirts?
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.
If you know some consecutive numbers, you can figure out the whole array.
Try to solve for quadratic case first
For quadratic case, either the smallest 3 or the largest 3 numbers will be together in some permutation. Try to extend this idea.
What was the approach to solve hackerland? Didn't get it during the contest
What is the main purpose behind putting the problems in unsorted way(random difficulty order)? (seriously asking)
Are we getting a T-shirt or goodies for solving at least 1 problem in (India ICPC — Amritapuri 2020 Regionals)?
Same doubt.The mail initially said we'll be getting a t shirt . But then no more talk about goodies .
Any hints for the lag?
ICPC Asia Amritapuri Site Regional Round Problem Discussion
Could you share the editorial too?