Creating this blog for discussion of problems/solutions from Indian ICPC Regionals
Onsite Contest Standings:
- ICPC Asia-Kharagpur Onsite Contest 2018
- ICPC Asia: Gwalior-Pune Onsite Contest 2018
- ICPC Asia: Kolkata-Kanpur Onsite Contest 2018
Online Replay Contests:
- ICPC Asia-Kharagpur Onsite Replay Contest 2018
- ICPC Asia: Gwalior-Pune Onsite Replay Contest 2018
- ICPC Asia: Kolkata-Kanpur Onsite Replay Contest 2018
There is also the whole issue with test cases in the regionals so far:
Gwalior-Pune:
- "Flipping Polygons" had wrong TCs which affected a few teams, with 3 of them getting AC later. Converting WA -> AC after contest is alright, but the time wasted by teams in trying to correct their codes could have been utilized in solving a different question.
- "Three Strings" had really weak TCs, considering that solutions taking max prefix and max suffix only get AC as well. (Breaking test case: 1 abc cde bcde)
Kolkata-Kanpur:
- "Chef and Alien Invasion" again had wrong TCs, and teams were affected, with even the teams qualifying for World Finals changing places. ACs were converted to WAs after the contest (although that doesn't affect the ranks), not to mention that it was announced that the problemset for the regional was made 1 day before the contest, which is not what is expected of an ICPC regional.
Kolkata-Kanpur had an issue with the test data of READCOST. I don't know how many other teams were affected, but we lost around 20 mins before solutions were rejudged and our previously TLed solution was accepted.
Also the problem SNOWMAN is simply Fibonacci nim, which is extremely lazy problemsetting. For someone who happened to know of it beforehand, it would literally take 2 mins to solve versus someone who would have to analyze the game.
can you please share your code for the READCOST Problem? The editorials are not available and the solutions from the replay are also not public.
We solved it onsite so I don't have the code, but you can see accepted solutions of the practice problem. I can also share the approach here. The problem is to calculate
for x, n ≤ 1000 and m ≤ 1015. The idea is to find the smallest k for which 
, for each i starting at 1. You can do this mathematically or with binary search. Accumulate sums in a variable and keep count of how many terms were added. Repeat until m terms are done. You will have to do the above procedure O(n) times.
https://www.codechef.com/viewsolution/22072489
Here's the code that implements the exact same idea. Hope it is readable-enough.
Apparantly it could be solved simply by brute force after exchanging N and M. I don't know why it works, but I got an AC in the onsite like this.
this is the hermite theorem.
This can be solved by brute force by interchangin n and m.
Let,
,
and
.
Now first make the observation that, remainder of x + (k - 1)n on dividing by m is periodic with period
. Hence each remainder appears either 0 or gcd(m, n) times.
Now, if for some k, x + (k - 1)m is divisible by n for some k. Then there will exist t such that x + (t - 1)n is divisible by m.
Now, collecting all those, f(x) - f(x - 1) will be 0 when x + (k - 1)m is not divisible by n for any k and gcd(m, n) otherwise, similar is the case with g(x). And hence f(x) - g(x) = constant = 0 as f(0) = g(0).
The series to be summed is simply an AP with some correction factor. It is easy to find a pattern in the correction factor series. Subtract the sum of correction factor series from the sum of AP to get the answer. I used Python because with this algorithm, long long will overflow in C++.
Python solution for READCOST:
VASTLIFE was also a copy of a Google Foo Bar Challenge. So yeah. Very lazy problem setting.
Lol are Kolkata-Kanpur setters more lazy than me? Since nobody has pointed it out last year, here it goes.
Club of Riders was copy of BearCavalry. I was so surprised to see a problem at ICPC Regional which I solved few weeks back before that regional.
https://codeforces.me/blog/entry/64035
We were also affected similarly. We made 4 submissions and wasted nearly 30 mins before seeing our first submission getting AC. I complained but to no avail.
IIIT Pune shouldn't be a host for ICPC.
They don't even have their own campus — they just seemed to have leased two buildings in some other college. They provided bare minimum food, hardly gave a fuck about the participants' needs (they didn't seem to have a working printer at times during the contest, Codechef distributed their t-shirts AFTER the prize distribution ended when half of the teams had already left!) and ffs the campus was in the middle of nowhere. Getting an Uber/Ola was a pain in the ass and we had to scamper to make it to the airport.
Same thoughts
Why did they announce it? :D
So if they are changing the ranklist after the contest ended, are the prizes given to the wrong teams?
Yes, the official results which were declared are different from the current results.
The problems were prepared on the night before the contest for gwalior-pune regionals. Anup (Lead at Codechef) himself announced that during the prize distribution ceremony.
Yes. He said that in Kanpur regionals as well.
I have also been to Amritapuri regionals, and the problemset there was really good (i.e., testing and required good skills). The gwalior problemset was really not good. Such a thing is not acceptable for ACM-ICPC, and CC must take care of it in future...
Bhai tera wf nhi hua kya (I m from Codechef)
Then you might be knowing it already if you are from codechef, don't you?
that's what I would expect from pipmri chinchwad
Can anyone explain the solution of GRAPHAND question from kharagpur regional contest ?? link : https://www.codechef.com/KGP18ROL/problems/GRAPHAND
The idea is to consider acceptable AND values of the final path, which must be ≥ K. For a particular AND value x, you can find the shortest path in the graph with Dijkstra considering only edges that have v as "supermask" of x (v & x = x). This is a candidate answer.
But you don't need to repeat this for all x ≥ K. There will be only a few "minimal" x for which you must find the shortest path, because if a x is acceptable then all supermasks of x will also be acceptable. You can find these minimal x by flipping exactly one 0 in K to 1 and 0-ing all lower bits. x = K must also be checked. As an example, for K = 001101, you must try x = {100000, 010000, 001110, 001101}. So you would have to run Dijkstra ~30 times to find the overall answer.
Basically fixing the value "x" (>=k) will ensure that the final "and" value of path b/w source and destination will be >=k right ? But how can we ensure that only those minimal "x" values are needed to get the minimum path cost (if exists) ? Can you give some explanation on this ?? Everything except this is clear .Thank you :)
I should have explained more about minimal x probably. So we want to choose some x such that x ≥ K, let's call these good. Running Dijkstra on a graph with only those edges whose v are supermasks of a good x will result in a shortest path with AND value also a supermask of the good x used. Since the value of a supermask of x ≥ value of x, the shortest path obtained is a possible answer.
Now the edges that are traversed with a particular x, will also be considered for all submasks of that x. If x' is a submask of x and both x and x' are good, it is pointless to run Dijkstra once for each. Just using x' will take into account all paths you would get with x.
So the smart thing to do is to find certain minimal good x, so that running Disjktra with each will cover all possible good x. I hope this explains why only using the minimal values work. A minimal good x will be good but not have any good submask.
Let me also explain why the minimal values are what they are.
Let's try to find the minimal good x among all good x. Of course K itself is a minimal good x. If you flip any bit in K, it is no longer good. Is K + 1 a minimal good x? For K = 01010 say, K + 1 gives 01011, which is not minimal since K is a submask. But the next value 01100 is indeed a minimal good x. The next 3 values 01101, 01110, 01111 are not minimal. But when the 1s flip again, 10000 forms a minimal good x. It should be clear now why the minimal good x can be obtained how I've described in my previous answer.
Forgive me if I'm being dumb, but I wish to clarify if my understanding is correct.
If V&X = X, then V is a supermask of X, and X is a submask of V?
So K = 10, in your example. So we need to find numbers in the range [10, 1000000000] (lets call them P) such that P has no submasks in the range [10, P-1]. If that is possible, then we can claim that P is a minimal good x.
Yes, you are correct on both counts.
Based on my observations, ranting about Indian regionals is the easiest way to farm contribution xD
And it has been a monopoly so far xD
Korea have dotorya
China have matthew99
Romania have geniucos
Russia have Um_nik
India have its own dumb version of whining kid Ashishgup
This comment should be taken as funny/light-hearted.
You love whining don't you? Edit: for edit, okay :P
Come on man, don't compare this idiot to these people. None of them do it for the sake of contribution, and I for one find Um_nik's comments hilarious. :)
.
Also Indian regionals are the easiest to get to the WF as well.! :D
[Deleted]
I didn't mock anybody. I just simply stated out a fact.
Indian people do not have much opportunities and resources as many western countries.
Indian people don't have the internet? India has the cheapest 4G in the world right now. They don't have Codeforces or Codechef or past year world finalists in their college? And the top performing countries in the WF's are Russia, China etc who are not western
India was a colony for around 300 years and all of its resources were exploited.
Did britishers take the brains of the people who weren't born in 1947 with them as well?
Good luck with the learning.
[ Deleted ]
yes its true ,not only for indians but for many in the community, because system for calculating contribution is weird i think so,becos how the hell? Ashishgup has contributed more than tourist,Petr,rng_58,neal,etc for the community? in my opinion ,contribution should only be calculated by any editorial or educative discussing comment ....
btw , i respect Ashishgup cos he is more than me ....no personal offense...
this guy can literally do anything for contribution
Some fake Indian accounts that don't admit their fault
LOL, you were not even close to qualifying for world finals, just accept it and focus on improving rather than crying like a baby/bitch every time you don't do well.
I'm not crying about anything, and I never said anything about being eligible to qualify for World Finals. I'm just posting a discussion blog and stating what happened.
PS: I know I'm not close to qualifying for World Finals.
For those of you who think I'm making this blog for contribution, I'm not. I just made one because nobody else did in the past 10 days.
We all know.
So, you are doing this just for contribution? :P
If you didn't want contribution, one of your your team mates could have written the same blog.
PS : You wrote the contribution thing in reply to my comment not in reply to Swistakk's to avoid downvotes.
Lol, I don't control the actions of my teammates, or anyone else in India.
As for Swistakk, his and kr_abhinav's comments are light-hearted and funny, and not offensive, as opposed to yours.
"For those of you who think I'm making this blog for contribution, I'm not. I'm already Rank 3rd in Contribution, and Rank 2 is too far away. I just made one because nobody else did in the past 10 days."
This is the comment I am talking about, I didn't even mention contribution in my first comment, only Swistakk did. So it was a reply for him. :P
Anyways, you know you are a greedy bitch. You only have the sympathy of people, you don't have their respect.
Damn! That last line.
He got sympathy from winners + respect from loosers.
Respect from losers? But you don't respect him...
but you do.Thats why anyway,i have sympathy for him and now you too.
You are not a winner if you don't even compete...
Hyouka is the gayest anime out there.
Sir, I really don't get the point of making a "post" specifically for raising up concerns over wrong test data of contests being organised by CODECHEF on codeforces. What do you exactly want ? The CC team arent going to be reading your blog posts as quickly as they might read one on Discuss. I dont believe you want to discuss solutions , you only want contribution.
MikeMirzayanov,How can people be #3 on the contributers list by writing DOGSHIT posts which are just Ranting codechef that too twice.
I guess we both can agree that ashish is a karmawhore.
AIex_2oo8 Putting people down does not make you a strong person, you are just another bully, a coward who is just jealous of him. I don't know why people like you exist. Why do people like you enjoy judging and putting down or belittling other people? STFU loser, and stop being jealous of others.
ok Ashishgup, I guess you are the brave one here with a throwaway account.
Codechef's discuss is so awful that it's more likely that the CC admins will answer on CF
Be a good guy like me. I could grab +127 upvotes(probably more if it was from my original account) with my blog post for my original account.
Don't go for contribution, Go for Rating. Boom!!!!!
So you're not the regional director for Kharagpur after all!
Can anyone explain whether this idea about the BUCKETWA problem of Kolkata-Kanpur regionals is correct or had anyone this idea? It seems like the optimum path is like refraction of light from vacuum to a medium of refractive index -k, like a metamaterial. This follows from Fermat's principle of least time. Thus we can say sin(theta1)/sin(theta2)=k and dH*cot(theta1)+dL*cot(theta2)=dR. Solving these simultaneously,the answer is dH*cosec(theta1)+dL*cosec(theta2). Because these equations are difficult to solve, we generate values for sin(theta1) using a loop, and detect theta1 and theta2 for which, the two equations hold.This should work, but my program isn't printing anything. Link: https://www.codechef.com/KOL18ROL/problems/BUCKETWA Sorry for bad typing, I am relatively new to all these, and I am commenting for the first time
What is this refraction stuff?The problem is this.
Now you have to go from the house to the river and then to the land. So basically you have to cover some distance with empty bucket(k times faster) and the remaining distance with water(k times slower). You will obviously fill the water from the river at some point between the lines dh and dl. So the path will be go from house to this point and then from this point to the land.
Since there is a factor of k binary search the most optimal point at which you should fill the bucket. Once you get the point calculate the distance appropriately.
Not sure if binary search can be used because the function is not always decreasing. Can you expand on your conditions for binary search?
The function is strictly convex (time taken decreases, reaches a minimum and then increases), so you can use ternary search on it.
Can you prove the function will be convex? I was getting an equation of degree 4 which I couldn't reduce.
Suppose the distance at which you touch the river is at a vertical distance x from the house, as per the above picture.
. Now, the first term is an increasing function, and the second is a decreasing function. Initially, the rate of decreasing function dominates over the rate of increasing function (see the trend of differential of both terms), and is eventually overtaken, thereby providing a convex function.
Now, the function to minimise would be
However, I think it's highly intuitive to imagine a point moving across the border of river, causing the function to decrease then increase and thus I did not prove convexity during solving, hence the weak explanation, sorry about that :(
Rearrange a bit to get
We only care about the roots in [0, dr] . f(0) < 0, f(dr) > 0, and f'(x) is obviously monotonically increasing from the second equation. This implies that f(x) was a convex function as f'(x) will have exactly one root in [0, dr]
Yeah, we also solved it by intuition based on the number of solves. This prove doesn't seem enough to me. We get a cubic derivative and it can also have the same property (f'(0) < 0, f'(dr) > 0) and have > 1 root.
Yes, it can. However, if it is monotonic is [0, dr] then it must have exactly one root in that region. Not that we do not care about the roots outside the region
Maybe you should not be so dismissive? The problem is actually equivalent to refraction of light where the relative refractive index of the two media is k.
rupayan if you provide your solution it will be easier to figure out the problem. Ternary search is a possible solution as mentioned by Beebabalooo.
The question asks for minimising the time and not the distance so this approach cannot be used.
My approach involved ternary searching along the river to find the optimal point from where minimum time will be taken.
The question asks for minimising the time and not the distance so this approach cannot be used.
Is there some kind of physics where minimizing the distance does not minimize the time?
The factor of K will come into account while minimising the distance as speed will decrease after touching the river.
I have used binary search and Snell's law to solve the problem. Basically, I take a distance from the base and find the corresponding sin(i) and sin(r). Then, I compare sin(i)/sin(r) to k and do a binary search as it is a monotonous function.
https://www.codechef.com/viewsolution/22050337
1,2,3,4 Ashishgup is karmawhore.
5,6,7,8 AIex_2oo8 can only h8
9,10,11,12 SoSooding has a loose screw.
13,14,15 AIex_2oo8 is 16
17,18,19 SoSooding solves div3A in 20.
Lol, I think this is a compliment for him. :P
Your username is hilarious.
How is it possible that teams that topped one regional were BOTH not even in top 5 of the other regional? Were the harder problems from Kolkata regional more hard than the harder problems from Pune Regional?
The best regional this year will be Amritapuri. They have taken the top teams without any best from the college bullshit criteria. Also the problemset will be more nice because last year they had akashdeep and GlebsHP as the problem setter.And if I remember correctly, last year, nobody solved any of the problems that were set by GlebsHP.
Just searched through the net and collected problems for the contest Typical 'Indians'
SORRY.
Typical Indians are the ones who copy problem ideas from other sites (like old Topcoder Contests and CF Contests) and use them as their own (while setting wrong test cases sometimes)in Indian Regionals and making money for the same.
.
SORRY.
Why are this all haters are ignoring the fact that it is true CC has rrally messed up experience of the candidates. Team ToLazyToPropagate was 2nd in kolkata regional but after changing AC to WA they are 3rd and might miss the chance to WF. If the judgement was right at that time they could have performed well to maintain their rank. Instead of saying he just wants contribution say CC gave him chance to do so and no one else had balls to put this up so he did. There is nothing wrong in it.
SORRY.
That wouldn't change the fact that team were affected. Pehle original account se comment kar then we will talk
SORRY.
A bully can never be a friend. Didn't know people can go to such extent that they are creating fake accounts just to bully someone. The only loser here is YOU.
T-Gay
Guys, seriously, what is going on in these comments? I see a lot of unfair disrespect towards Ashishgup. Why do you use such words as "idiot" :|? RejectByLifeCompanyGirls the_pacifier1 AshishChup AIex_2oo8 and maybe some other guys as well — who do you think you are? Get your behaviour straight. By the way, saying things like "This comment should be taken as funny/light-hearted." or "No offence, but (...)" or "it's a prank bro" doesn't invalidate what you say and doesn't justify you offending other people or acting in any other inappropriate way.
My previous comment was to be treated humorously, but of course there is substantial difference between what I wrote and following comments using words like idiot or whore. All people that complain seriously that someone just wants contribution or whatever is a huge cancer and adding unjustified offending to this is next level. If someone gets contribution it means that community appreciates his content /eot
I think codeforces should start banning accounts like quora does.
Thanks for opening my eyes Swisknife.
We are sorry for our inappropriate behaviour, Swischeese
Hi, I participated in the Gwalior regionals (for schools). I couldn't figure out the last two problems, Flipping polygons and polygon and Strings. Could someone elaborate the solutions?
Polygon and strings: It is given that the convex hull of the given set of points is the set of points itself. Also no 3 points are in a line and no 2 points have same X or Y coordinate. One more important constraint is that in the solution no line segment should intersect with other line segment. Imagine you sorted the points clockwise/counter clockwise ( does not really matter which ) . We know that our solution has to include all the given points since query length is N-1.
Now imagine you have taken the 1st point in the answer to be the jth point in the sorted order. what can be the possibilities for the 2nd point? If you take the Kth point in sorted order and there are >0 number of points between jth to kth point AND >0 points in between kth to jth point ( points array is circular so there are two intervals between jth and kth points ), then at some point in the future you will have to intersect the segment j to k because you must cover all points.
What this tells us is that after taking jth point the only possibilities for the next point are j+1 or j-1. Which tells us that at any instant, the set of "taken" points forms a contiguous segment in the sorted order. If the segment L to R is taken then the next point can be either R+1 or L-1 and nothing else. However,information which one of L and R was placed in previous step is also needed. this leads us to a simple DP solution bool dp[which][L][R] where "which" tells us if L was placed in previous step or R. dp array tells us whether it is possible to proceed with these parameters or not. To print the actual solution just store the optimal next moves for each state. Total time complexity is n*n*m, given constraint on n*m makes this solution optimal.
Flipping polygons: I do not know why the setter has given Fibonacci numbers in the problem. Interpret updates in this manner: instead of rotation points, let us rotate the y axis. So the y axis will have a direction, and a counter indication which point (or side in case when N is even) it is passing through. So rotate polygons in L to R by X rotations means basically adding X to all elements in L to R. However if some polygon is flipped X rotations mean subtracting X from it counter instead of adding.Fortunately, this can be done using a single segment tree with some smart lazy propagation. I recommend you to look at the AC codes on codechef in the replay contest ( look for the ones which have a single seg-tree). The code is quite simple to understand.
I dont think your solution for flipping polygons is correct. when u invert, not only do u change the state to subtraction, but also shift the y axis rotation by a certain amount. This shifting information is based on the number of sides of the polygon. This is why i think the fibonacci numbers was given because, upto 1e9 , there are only around 43 fibonacci numbers, so in our segtree we can store the information regarding all different types of polygon.
thanku for the solution of polygon and strings though :D
Well i think my solution for flipping polygons is correct, and i am just not able to explain it properly..that is my bad..take a look at this code : https://www.codechef.com/viewsolution/22006349
You can also checkout Praran's code which does the same thing with 43 segments trees but his solution does not really required 43 seg-trees. The same thing can be done in a single seg-tree.
Edit: i think i understand what you are saying now, however simply subtracting if flipped is still correct. We do not have to shift anything. We can handle that during the query.
Can someone please explain their solution for this expectation based problem from the Kolkata-Kanpur regionals: TILEBAG ?
A tile with number S can be formed: This means that atleast one of X or Y is of the form S / (2^k).
X and Y are not divisible by each other: This (along with the previous statement) means that exactly one of X or Y can lead to S.
Assume X can lead to S in 2^k moves. Expected number of turns before you get an X is 1 / p. So expected number of turns to get 2^k X's is 2^k / p.
Do a similar analysis for Y (replace p by 1 — p).
Sorry, it is not clear to me still.
This means that atleast one of X or Y is of the form S / (2^k): I didn't get it.
This means that exactly one of X or Y can lead to S.: But what if say X = 3, Y = 5, S = 15.
A tile with number S can be formed: Does this mean that X = 3, Y = 5, S = 8 is an invalid case since the tile may or may not be formed ?
Please elaborate a little.
So the only numbers you can encounter by getting tiles of type X are: X, 2X, 4X, ....(2^k1)X, ....
Similarly due to Y, you can get Y, 2Y, 4Y, .... (2^k2)Y, ....
Now because the solution exists (**A tile with number S can be formed**), S must be of the form (2^k1)X or (2^k2)Y.
But what if say X = 3, Y = 5, S = 15.: This is in invalid case since you can never reach S using those 2 tiles. Even your other example in invalid for the same reason.
Thanks a lot. I seem to have misunderstood the problem slightly. But your comment was very helpful. :)
Rather than showing hate, can't we discuss the problems?
How to solve Yet another shortest path problem from Kanpur regionals YASPP
Use 0-1 BFS while maintaining the set of colors of previous edges(corresponding to only shortest path) for each node. Code
So this code is wrong as pointed out by sauravray2587. Here is the test case provided by him for which the code fails.
5 5
1 2 1
1 3 2
2 4 1
3 4 2
4 5 2
1 5
Answer should be 0 but the code outputs 1.
This wrong code passes on codechef which means another case of weak test cases in regional.
[Deleted]
Another approach is as follows: Modify the given graph as follows. For each node present in the graph, make some copies of the node equal to the number of distinct colors attached to it. Let the copies of the node (say u) be numbered v1, v2, ... , vk. Connect these nodes to u with weight 1. These edges represent changing of color. Now, for an edge some color, connect their corresponding copies with weight 0. Now, run any shortest path algorithm from S to T and let it be L. So, ans = (L — 2) / 2. Complexity: O(n + m) if you use 0-1 BFS, or O((n + m) * log(n + m)) if you use dijkstra. See my code: https://www.codechef.com/viewsolution/22043601.
Can anybody tell me how to solve Subset Sums Revisited SUBSUMX from icpc Kharagpur regionals? Also if somebody could explain me how to extend my idea that I have explained below, it would be of great help. It happens that the same solution was explained after the contest in regional site but that person too explained only upto the point I had already solved. So it was of not much help for me :(
(
× dp[i-1][2 × (j-m)]). 
ways and the rest (j-m) 2i are taken from 2(i - 1) s. Now to obtain (j-m) 2i s we require 2 × (j-m) 2(i - 1) s which we can obtain in dp[i-1][2 × (j-m)] ways. We do this for all m from 0 ... j and sum them to obtain the final answer.
MY SOLUTION
We can easily construct an array x[64] from a[n] given such that x[i] = frequency of ith bit 'on' in B[0 ... n].
For example if A[] = {1,1,2} then B = {2,2,4} hence x[1] = 2, x[2] = 1 and every other x[i] = 0.
DP State : dp[i][j] = j number of 2i s required.
Recurrence :
dp[i][j] =
Base Case
dp[i][0] = 1EXPLANATION OF MY DP : dp[i][j] = we want j number of 2i s. So we take m number of 2i s from x[i] in
PROBLEM IN MY DP
My dp works well if k has only one bit set in its binary representation and so I could just call
dp[log2 k][1]but I don't know how to generalize this idea for any k. Can you please help me?Can anyone please explain their solution to GAMOFNUM from Gwalior-Pune regionals?
First observation which is really important here is that for a number Ai in the array, say it's prime factorization is Ai = p1 * p2 * .. * pk. Then, you can treat each prime as a different pile and solve. You can consider the moves as choosing a prime factor of Ai and replacing it with some number x which can in turn be decomposed into more piles. Now, basically you have to calculate the grundy of a prime number. Another observation is that the grundy of the kth prime number is k. Why? This is because from a prime p, you can go to any prime less than p and 1 itself. So when you do the mex operation, grundy comes out to be k. See the code: https://www.codechef.com/viewsolution/22010093.
Thanks for the explanation. But I have a doubt, let's say Ai = 21, so we are considering this as a nim game with piles (7,3). If I choose p=7,i=4 I end up with the state (2,2,3) and not with (4,3) as it should happen in a nim game. So, how can we treat each prime as a different pile of nim?
Yes, you would end up with the state (2,2,3) and Grundy of its state is g[(2,2,3)] = g[2]^g[2]^g[3].
Another issue was that there were lot's of announcements for the problems that were not reflected in the printed statements (Almost every problem had an announcement). Thankfully, they weren't mid contest, but was still annoying.
Can someone explain their solution to Chef and Alien Invasion? ALIENCOW
We just need the areas of the closed regions formed by the fences. (The answer then is just the sum of squares of areas over the total area.) Imagine that all of the rectangles' edges are extended both ways — the field now looks like a grid of kit-kat pieces. Any regions formed by the fences must be a disjoint union of these small pieces of land, which are only at most O(k^2). So we can use a DSU / perform a DFS to join adjacent pieces of land that don't have a fence between them.
Thanks. That makes sense. I'm guessing each piece of land would represent a node and each free side would correspond to an edge in the graph. What would be an efficient way to build this graph? Any hints? Edit: Nvm. Got it.
How to solve Palindromic Paths (PALPATH) from Amritapuri regionals?
Consider any valid walk. The ith edge on the walk and the ith edge from the end have the same character on them. So try building the walk from both directions. Define dist[a][b] as sum of lengths of the shortest walks from s to a and from t to b such that the concatenation of the (ordered) edge set of these walks is a palindrome. Then min(dist[x][x]) gives us the shortest even length walk. Odd length walks can be considered by enumerating every edge in the graph.
We were the only team significantly affected at the Gwalior-Pune regionals. We finished 7th with 9 problems solved but our rank increased to 5 after the contest since the test data for NGONS was wrong. We would have had at least half an hour to solve POLYSTR (which is similar to a problem from Indiahacks 2017) and managed to come second, thus qualifying for world finals.
We spoke to Anup in person but he smiled and said nothing can be done about it. We also emailed the regional directors but to no avail. Since we're the only team affected, everybody seems to be ignoring the issue. It's our last attempt for ICPC and we're potentially missing out on qualifying because of someone else's mistake. Isn't Codechef's credibility in question if they can do whatever they want without being answerable to anyone?
Indian Regionals are a joke.
As much as I agree with you, unfortunately ICPC rules state that "In consultation with the judges, the Regional Contest Director determines the winners of the regional contest. The regional contest director and judges are empowered to adjust for or adjudicate unforeseen events and conditions. Their decisions are final."
It's really sad we can't do anything.
Perhaps we can appeal to the regional directors to ensure necessary problem quality rather than leave it to CodeChef to prepare the night before the contest?
What makes you think RCDs will be responsible?
Since RCDs are the ones who are all-powerful here, that seems to be the only course of action available.
We emailed the RCDs, they dismissed the issue immediately. I don't think appealing is a thing in India lol.
Not that it would matter, but you have to email to [email protected] for an official appeal. (within 1 day, it's too late now)
Yeah we did at that time, but no proper response. We were told about the error late as well. But yeah, nothing can be done now. Thanks though. :)
How to solve SQRTRI of Kharagpur regional.
Problem Link : https://www.codechef.com/KGP18ROL/problems/SQRTRI
Just pure mathematics. Find the intersection of lines in all 4 directions and check the coordinates of that point to the boundary condition of the square.
Can anyone tell me how to solve ALIENINV from Amritapuri regionals. I have been struggling with this for days.
Anyone please?
anyone?
This problem was discussed here. You can refer to it.
How to solve INFDIV from KGP onsite. Editorial/link to discussion thread is also fine.