Gordian Knot is a Project Euler styled contest that challenges you to untangle the intricate enigmas of mathematics. Feel free to deploy your programming skills to make your life easy. Variety of problem set is slightly different from typical Project Euler styled contests, so we hope that you find the problem set crisp and enjoyable :)
Gordian Knot belongs to same chain of technical events called Threads, which recently organized : Codecraft (on codeforces) & Fool's programming (on codechef). You can follow Threads blog on Quora too, on which we will be adding more articles soon. Presently, we have a unique system design contest called 'SysCraft' running and 'Kings of Machine Learning' lined up too.
Contest Link : https://felicity.iiit.ac.in/threads/gordian-knot/
Start Date : 25th January , 08:00 IST
Duration : 24 hours
Prizes : T-shirts for Indian residents in top 20
NOTE :
- We will release short editorial for 5 most popular problems.
- You can ask for hints here if you are stuck on some problems, during last few hours we will provide hints on selected problems. Others strictly refrain from discussing/commenting about problems or posting hints/solutions.
So, can you solve 24 problems in 24 hours? (We have extra bonus problems)
Get your maths and programming skills brushed up by taking on our challenge and grab one of 20 T-shirts :)
UPDATE :
- Problem statements for P6,10,12,13 have been simplified. Please re-check.
- Solutions for P21 have been re-judged.
- Hint Phase begins! Ask us for hints, We wish to help you solve whole of the problemset :)
- EXTENDED CONTEST till 8 pm today. We really want to see someone solve whole of problemset, hope you make best use of it!
- J.T.J.L. & zimpha unlocked level-7!
RANKLIST :
- zimpha
- J.T.J.L.
- zeliboba
- rkm0959
- akashdeep *
- jtnydv25 *
- usaxena95 *
- triveni *
- xenny *
- Pokeylope
- hitman623 *
- amwat *
- cerberus97 *
- Golovanov399
- teja349 *
- djdolls
- Vercingetorix
- eyg
- pulkitjain41 *
- shubhiks1032 *
*will get T-shirts! Congratulations. It was great to see a lot of people putting most of their day to the 36hr long contest, thankyou all for that. We had to re-write problem description for clarity in few problems, sorry for the inconvenience. We hope that you enjoyed solving the problems. Feel free to pm if you have suggestions/comments.
We will be publishing 5-popular problems' editorial as promised sooner this week :)
Auto comment: topic has been updated by phpduke (previous revision, new revision, compare).
Auto comment: topic has been updated by phpduke (previous revision, new revision, compare).
Can you share link of last year's contest?
No. But you can see ranklist of past contests.
2017 : min_25 won with quite a difference. Endagorion, anta, Arterm, W4yneb0t, geniucos, Golovanov399, geniucos, Lewin,etc were in top 25.
2016 : tourist, fhlasek, rng_61 finished in top 10.
Is anyone from top 20 eligible for T-shirts or only Indian residents?
How to submit an answer for the 6th question?
is it resolved now ?
no, now it's 500 internal server error
Can you go to home page and refresh once ? Is the error still there ?
I don't know what the home page is, I refreshed everything many times, still this error
Its fixed now for all. Check P6 now.
Guys, I'd like to note that Q12 is incorrect right now... Solve the problem with i 1,5,9 .. etc.
I hope the IIIT ppl look into this problem while I go for lunch :P
This is fixed now, so no need to look into this comment.
Q13: a, b, c should be positive integers, otherwise the answer is not rational.
Yes, we missed typing this detail. Updated statement.
Auto comment: topic has been updated by phpduke (previous revision, new revision, compare).
can you give hints for problem primality testing
Carmichael Numbers
Can you please explain Q4: Recurring Tournament.
How is the game being played ?
A round robin game is one in which each player plays with every other player. Then how can one player be left ?
It would be better if I get an explanation with example.
Problem Statement is updated . Please check again . Apologies for the inconvenience caused
Should we fill every cell in Q15? Or we could we leave some empty?
Every cell should be filled
I think answer of 8th problem is wrong!!! Please check it again.
Re-checked. It is correct. Please try again.
Can you please explain the question a bit more.
I think there is no upper bound on value of M. But the question asks to maximize M.
How can that be possible. And for given n and m pair if more than 1 triplet of (a,b,c) occurs then which one to choose.
What is the probability space in q16?
It's mentioned in the question : Find the probability that a randomly chosen line in R**2 cross both circles given that the chosen line crosses C1
I repeat: what is the probability space? Even if we calculate aposterior probability, we need to know what the relative (under the condition that the first circle is intersected) probability distribution is. I can think of several distinct distributions, and each of them seems to me equally possible to be meant.
I agree, statement is unclear
The space which is being meant here is the angle with X-axis, and value of y at x = 0, which makes sense but should be mentioned clearly.
What do you mean by "angle and value at x = 0"? One can derive from this that 1) there are no vertical lines (and we haven't fixed the positions of the circles), and 2) the angle is distributed equiprobably on [0, π) (which indeed makes sense)
Can we replace the "y(0)" parameter by the "distance to the first circle's center"?
We can replace y(0) by distance from origin. For lines except those of form x = c, it is the same as choosing y(0), as there exists a bijection from distance from origin to y(0) in case of such lines.
Ok, so the prior distribution of this parameter is "uniform over the reals", but this definition becomes good after taking the posterior distribution, thanks.
If a line is tangent to C2, do we consider that it "crosses" C2?
Yes we consider that it crosses C2
In problem 13, is (a,b,c) an ordered triplet or unordered triplet?
unordered
Strange, as I got it right assuming ordered!
EDIT : Unordered doesn't make any sense unless you specify a <= b <= c, or something of that sort, as the bases which they are raised to, are different and order matters here.
PS : It is ordered .
There was some confusion among us . Sorry for the inconvenience caused .
In Q4, what do you mean by match? As there can be 1 person in group, do we count this as match?
If there is only 1 person in group , he is the winner then . Thus there are no matches . Since , it is a knockout tournament , there is a match/game between two individuals and winner of that match goes along and the other is knocked out of the tournament . In case some person is left out i.e he does not get a partner to play with because all other partner in that round are playing with someone else , he automatically goes to the next round . This process continues until one person is left . To know more , you can read up about knockout tournaments .
I think solving all four problems of one level to enter the next is a little too much! Won't be able to attempt a lot of harder problems if you are stuck somewhere
Q21:
Is it correct that ranges such as [-100000, 100000] are inclusive?
Yes , they are inclusive
Is it correct that A = [g(-1000000), ..., g(1000000), h(-100000), ..., h(100000)] and we couldn't change order of its elements? Word "bag" is confusing.
Yes , it is correct
Could you explain the definition of B more clearly?
B is just a array of integers whose elements are in strictly decreasing order . The motive is to find such a B that k is minimised .
Darn.. that solves the problem :(
just a small request. After contest is done reveal all the questions and answers.They are very interesting.
Q22
Should we find F(g(N)) or F(g(N)-1) ?
F(g(N)).
Small request: Please extend the contest by 12-24 hours (I wanna sleep)
I could only work on this contest for 10 hrs :(
Cool. That would do. Thanks.
I think u are mistaken or in need of some sleep.Please check above comment properly.
Absolutely. My bad. :P
Can you atleast open the last section for everybody? I think no one has access to it right now. It'll be such a waste if no-one even tries the problems.
Due to ambiguity in certain problem statements, contest has been extended by 12 hours . It will now end at 20:00(UTC +5:30) . Formal update on the blog to be made soon
I am not sure about correctness of judge answers for Q21 and Q24.
UPD. Q24 is ok.
Q21 has been rejudged
Constraints for unlocking level 7 has been reduced to solving 3 problems in level 6 as of now . Formal update on blog to happen soon . Stay tuned !
Please Note : Q21 , "Functional Enigma" , answer has been verified and updated on the judge . Please submit again . Apologies for the inconvenience caused . Also the minimum number of questions to advance to level 7 has been put back to 4 . Formal update on blog to happen soon . Stay tuned !
PS : Q21 has also been rejudged for all submissions
Can you explain this line for Q21:
Let B be the set of integers made from corresponding elements in bag A such that its elements should be in strictly decreasing order
How is this example working?
A = {2,5,2} then B can be {6,2,1}
Check this conversations : http://codeforces.net/blog/entry/57311?#comment-409832
In question 19, Intersections : Is it given that function g is continuous ? Nothin is written about g, please clarify.
No such condition is given.
Q27: How many decimal digits should the answer be rounded upto?
upto 6 decimal places.
Auto comment: topic has been updated by phpduke (previous revision, new revision, compare).
can you give hint for problem simple primality and problem recurring tourament
Hint: For recurring tournament, Try to think in opposite direction. i.e Given number of people what will be number of matches.
Is the answer of 28-th problem correct? Can you check it?
It is correct.
Q25: Can the polygon be self-intersecting?
Also should it be convex or not?
No. Polygon cannot be self-intersecting.
Should it be convex or not?
No. It it needn't be convex.
Should we count polygons which shapes could transformed one into another by rotation?
Any hint for Q13: Unusual Fraction and Q16: Art ?
And please explain Q8: Drunken Mathematician more clearly. I asked for it yesterday but no response.
For Q13 think of substituting something in place of (a,b,c)
Hi. On your request, problem statement was updated to simpler and concise explanation yesterday. Check it :)
Several methods. Imagine one circle as composition of several hollow circles(rings). Simulate.
Q28
Are there 302 swaps with equal probability or 30·29 / 2 + 30 ? In other words are swaps (a, b) and (b, a) considered equal or not?
We can select 2 random indices i,j where i=j or i>j or i<j and swap them.
Any hint for the triangle problem ? Aren't there infinite options for (a,b,c) ? Is the sum convergent ?
It is convergent :) It's also very similar to a math competition problem held a few years ago.
https://artofproblemsolving.com/community/c7h1171039p5624386
PUTNAM 2015 B4 is pretty much the same problem.
Thank You . I will look into it.
Actually I also can't make a sense out of Q8. Maybe I'm just stupid but I already spent a lot of time trying to figure it out and grasp how all other people could possibly get it :) Could you please somehow clarify the statement?
Нужно мерять весами с двумя чашками.
I will restate , let me know if this clears it up. You have to choose N containers. You can also choose capacity of each of these N containers. Example : for N=3, you can choose 3 containers with capacities as {1,2,3}. Or you could have chosen {5,5,500}.
You need to measure volume of a given liquid using the N containers you chose. You have to dispose a container after you pour liquid on it. Hence ,there's a range on volume of liquid you can measure for some set of N containers you choose. You optimally choose capacities of containers so as to maximize range of liquid-volumes (which varies from 1 to M) you can measure with your chosen containers.
In this case, following equation holds: a*M — bN — c = 0, where a, b, c are non-zero constants & M,N are positive integers. Find 100a + 64b + 36c.
I still don't understand. Suppose I have a set of containers of volume : {1,2,4}
I can measure 1 L using 1 L container. 2 L using 2 L container. 3 L using (1 and 2 L) container. 4 using 4 L container. 5 using (1 and 4 L container). 6 using (4 and 2 L container) and 7 using (1,2 and 4 L container).
Am I wrong ?
No, you aren't wrong here.
Ahhh, what I did not understand was that a,b,c are constants for which the equation holds for any N. Not sure how but I got it after reading your answer even though this part is exactly the same as in the statement. Thank you)
Q27 : Please explain how the cake is cut. Do the slices have the center as common point or the chosen point as the common point? Also, how is the numbering done? As in, where do we start numbering?
No , the slices may not necessarily have center as common point . Numbering can be done starting from any slice (0-indexed or 1-indexed , your wish) , then next number is the slice which is next in the clockwise order and so on . It is just that one guy eats the odd number slices and the other even numbered slices .
I would say
Q24 Trapped Constraints
is the best problem I have seen in modular arithmetic. Wow. Wish I had more time to try the last level.How is multiplicative order defined without stating what is the mod ? Do we need to assume things mod n ?
they are just primitive roots of unity. There is no mod atleast for counting the sum of primitive roots.
And the sum of those is just mobius function. This can be shown by cyclotomic polynomials and mobius inversion. So once you get t = - 1 the rest is simple.
How did you solve the max(gcd(pq+1, qr+1, pr+1) part?
If gcd(pq+1,qr+1,rp+1)=T, it is easy to show that p, q, r are all same mod T and p^2+1 is a multiple of T.
With this observation, set q=p+T, and r=p+2T. We now have p+T<=n/3, and we aim to maximize T.
First note that the easy sol p=14919, T=14919^2+1 works.
Let's prove that no larger T exist.
If such T existed, p<=n/3-T<=n/3-14919^2-1<=20000.
Also note that p^2+1 cannot equal to T in this case (that case is covered by p=14919, T=14919^2+1) so T must be at most (p^2+1)/2.
So T<=(20000^2+2)/2<14919^2+1. Done.
We are looking at primitive roots of unity, the complex number , where .
I was trying to do the same mod n -_- Now I get this. Thanks :)
How was Q23 supposed to be solved?
For snooker problem Q23, just solve (2, 3) + (A, B) = 20(u, v) + (x, y), where (x, y) is either (5, 6), (5, 14), (15, 6), (15, 14) and . The direction will be the direction of (A, B) wrt origin. This can be shown by reflecting the diagram. (very well known I guess)
Find all possible (A, B) with A2 + B2 ≤ d2, and calculate the number of directions. I did this by using std::set.
How to solve Q25, Q28? For Q28 I tried analyzing the number of cycles and tried to relate it with the probability but it didn't seem to work :(
Q28: only the length of cycles are useful. you can sort the length and consider it as state (there at most 5600+ states). code
Is Q3 Lehmer's totient problem? Or am I missing something?
Just run brute force of what has been written in the problem.
It's http://mathworld.wolfram.com/CarmichaelNumber.html which is well-known.
Okay thanks!
How to solve triangle infinite series problem?
How to solve Q.13 Unusual Fraction?
see my comment above :)
How to solve "Ache din"?
Were we supposed to find (a,b) such that gcd(a,b)>1?
Total blue points within a square is equal to the number of unique slopes which is equal to number of unique y / x values. Every point x, y where gcd(x, y) is 1 will gives a unique slope. Euler Totient Function for each x (or y since it is symmetric) will give us number of irreducible fractions of the form y / x and that is the number of unique slopes that particular x or y contributes. Summing totient function from 1 to n / 2 will give us number of blue points in 1 / 8th of the square (why?). Multiplying this value by 8 gives us total blue points and subtracting from (n + 1)2 - 1 gives us number of green points for a square of side n.
Got it now! Thanks a lot for the response
Could you publish the problems for the entire set, since the contest is done now?
Auto comment: topic has been updated by phpduke (previous revision, new revision, compare).
It was a nice contest. I enjoyed all the problems that I could attempt. Thanks for the interesting problems :)
Please make the problems for practice. Or upload them to some judge. That will be so nice of you guys :)
Thanks for the contest. I participated in this contest last 5 years (or may be more, I don't remember). Good to see that contest became much less buggy than several years ago. Also now you have much better feedback system, updates for unclear statement published rather fast, it was good idea to allow all participants ask about statement right here on codeforces, it was very convenient. You still have issues with last problems like in previous years, probably it is because you are preparing them at night before competition or may be during competition =)
In this year problems were easier than in previous years (this is not good), but I like some of them: Q24, Q21, Q13, Q18 (and may be something else, but I could'n see problems now)
I'd like to give thanks too, but I want to make some notes about thinks which can be better next time. The list of problems is closed now, so I'll not list everything I could.
The problem about 100a + 64b + 36c. First of all, it'd be great if you mentioned what you mean by "measuring". As I understood (only after I passed this task), you meant "one can measure x iff it's possible to put some masses we have onto two parts of a balance scale in such a way that one is heavier than another by exactly x". This definition is far from obvious.
The problem Q15, dracarys. When you write "a rectangular board with dimensions 5x10^18" I imagine a (5·1018) × (5·1018) board. You could write "a rectangular board with dimensions 5 and 10^18" or "a rectangular board 5 × 1018". I don't want to get the correct definition just because you used "rectangular" instead of "square" (actually, I asked the correct statement to my friends, they told me).
The problem Q16. Every time you talk about probabilities, you must specify the distribution. Otherwise your words make no sense. One can omit this if there is somewhat default distribution (for example, one, reading "chosen randomly from [0, 1)", can accept that the distribution is likely to be uniform), but it's not the case. You can choose a point uniformly from the first circle and then pass a line through it and orthogonal to the radius with this point, and it's one distribution; you can choose angle and distance to the center of the circle uniformly and independently, and this is another distribution. I don't know what you mean by "randomly, given that it passes the first circle". There is NO distribution over lines where the angle is chosen uniformly and the distance to the origin is chosen uniformly. There is no prior distribution for the meant statement.
Mathtype. You need it. It could help in the 5 × 1018 problem, it could make the formula "a*m + bN + c = 0" look "am + bn + c = 0, etc.
This is certainly not everything I wanted to say, but it is about everything. If talk about the essence of problems, they were good, and some of them were great, so thank you for this.
zeliboba. Golovanov399.
Thanks for value feedback. We have taken them positively. Here is screenshot of problem-list raw from portal if you wish to add more to your comment or you can wait for a day, we will put up all problems in our new judge we are making to standardize it for upcoming contests.
And yes, we agree that we should have spent some time on problem statement itself rather than just spending our times to come up with good ideas for essence of problem setting. Apologies for same.
My name is not starred, even though I'm Indian.
And djdolls is starred. I doubt, if he resides in India.
Yeah, same for me. I'm also Indian and my name is not starred.
Yeah, mine too, (because of my handle, I guess).
Fixed. Pardon for our bad stalking skills :P
I think the contest was pretty good overall. I have a few complaints though:
(i) The problem statements were terrible. In almost every problem, I had to make assumptions not clear from the statement.
(ii) I really don't like the rule where you have to solve all of the previous level to move to the next level. Maybe someone doesn't have much time and only wants to try hard problems, or they are stuck at one problem and can solve all other problems of the set. Here, one problem has WAY more impact than it deserves. I think most of the participants would agree here.
(iii) The levels were not decided appropriately. There was a problem in level 7 which deserved to be in level 4, and there was one in level 4/5 that deserved to be in 7. There were a lot of such pairs of problems which could easily have exchanged the levels.
I agree with all the above points.
I was stuck for a long long time in the circle problem. And very late I found out about the probability distribution mentioned here.
Similarly, I wished I could solve the harder problems and leave the one problem which I was not getting right. Frustrated enough, I had to leave the contest and when I woke up I realized what was wrong with my approach, but then I had only few minutes (around an hour) time left to solve remaining 7 hard problems.
Since not all the participants in top 20 are indians.
Why don't you extent your list a bit. May be till Rank 22 :P
It was supposed to be a joke -_-
Turns out that we have 2 extra T-shirts left. Congratulations for winning T-shirt :)
Am I being joked back ? :P
"We will be publishing 5-popular problems' editorial as promised sooner this week :)" ?
Still waiting.