Hi everyone!
Codeforces round #716 will take place on Apr/19/2021 16:35 (Moscow time). It's rated for the second division, but, as usual, first division participants can take part out of competition.
The problems are based on the Egyptian IOI qualification, and they were created by me and mahmoudbadawy. I'd like to thank:
- KAN and budalnik for their excellent coordination.
- antontrygubO_o for improving a problem, then rejecting all our problems without reading them, then testing the round.
- Yousef_Salama, Mohammad_Yasser, Noureldin, and ahmad_salah for testing the official contest.
- 74TrAkToR and psevdoinsaf for testing the round.
- MikeMirzayanov for the great codeforces and polygon platforms.
This may be the most and only balanced round I've ever set. You'll be given 5 problems and 2:15 hours to solve them.
UPD: the scoring distribution will be 500-1000-1500-2000-2500.
UPD: the editorial is out.
UPD: congratulations to the winners:
Div.1:-
Div.2:-
Good luck & Have fun :D
As a setter give me contribution.
ok i upvoted. i am sure this round will be great!
I don't think it was great. Pretests were very weak. Code of problem D can be directly copied from internet by just changing 1 line.
See this : https://ideone.com/kTZH6K
See my solution : https://codeforces.me/contest/1514/submission/113537817
I just changed 1 line and it was accepted.
Definitely
Two types of tester — ( official contest and Round )
And sadly you are in none of them :(
PS: While(downvotes>0)sad++;
mohammedehab2002 and his love for XOR problems.
antontrygubO_o for rejecting all our problems without reading them.
LoL
Problem D will be a XOR problem. I can tell.
Can't wait for the contest!
As an official contestant, The problems are very interesting and you will enjoy solving them.
Is it likely that some potential participants have already seen these Egyptian IOI qualification problems long before the contest?
They will not take part of the contest on codeforces
maths problems incoming
Hello!
There is an important month-long religious activity ongoing right now for Muslims. Most of the people in Bangladesh (including me) are Muslims, and generally most of them participate in at least the main events of it, which happens everyday from around 12:00UTC till 16:00UTC. It's quite unfortunate that the Codeforces rounds are usually scheduled at 14:35UTC and thus I'm sure a lot of the participants can't help but miss them. Missing most of the rounds for a whole month is pretty sad.
I'd be very grateful if the admins could vary the schedule a bit more often, so that everyone can enjoy the contests at their convenient times. A few of the CF rounds in the past have actually happened at 9:05UTC(#1, #2, #3, #4 from the first page). If some of the rounds can be scheduled at that time more often, then I believe the contests will be more accessible to many participants.
yes, April is full of endsems for me, please delay all rounds by a month, so that I can participate.
I'm sorry If my message came out wrong. I'm not requesting for the contests to be delayed/moved/cause inconvenience to the other participants in any way. But since people from a lot of different timezones participate in CF rounds, it's natural that some of the participants in every round would find it at an inconvenient time. So, I think it's fair to request the schedule to be a bit more varied, so that people who miss don't have to always keep missing.
Your point is valid, however keeping the same time for almost each contest helps the particiapant to Adjust his/her schedule accordingly. For instance, if the timings were varied then the person would constantly have to check and try to be free at the time the contest is. Whereas if the contest time is fixed, he just has to free himself at that point of time in the entire day. So in order to accomodate with all communities around the world and keep the above stated CF should think of fixing, say 3 points of time during the day when a contest might occur. I think this could be beneficial.
Hello, as a Muslim, I accept this and also the people of my country (Iran) and the Muslims of all Islamic countries should fast this month. My suggestion is to change the time of the contests with a poll ! Codeforces will definitely get more participants in this month's contests. Thank you very much ! =)
I guess current time was chosen, because in the European part of Russia, it is the end of the working day.
Codeforce is not a commercial project, people that administer and support it are enthusiasts. They spent their free time, that just happens to always start at 12:00UTC, after the official working hours in Russia.
If that really is the case, then how about:
Trying to place those contests on weekends, when I guess there'd be no official working hours.
I read CF had ~600k users a few years back, it's surely well past a million now. If the admins needed some help to scale it further, they should comfortably be able to find a few trustworthy/veteran users from appropriate time-zones who'd be more than willing to help out by overseeing those contests (just for the duration when the contests are running).
Notice the unusual starting time :)
I didn't, which stopped me from getting +100 rating. Oh well, next time I guess!
Codeforces Round #716 (Div. 2), writer: mohammedehab2002
Div 2 IOI qualifications o_O
It is not like what you think. Problems had subtasks in the IOI TST. Also, the problems are really interesting!
It's just weird not to see div 1 when doing this)
Well, the original contests can be best described as div 1.5, but when you actually set on CF, you can only round that number up.
Another div1.5 goes brrrr
И более важный вопрос, как трактор стал тестером :/
А что не так?
А как?)
Меня попросили протестировать раунд
NOTICE THE UNUSUAL START TIME.
5 problems but 2:15 hours!!!
As a nobody give me contribution.
you are a participant right?
xorz
I pity you because you only have two hours to enjoy solving these problems instead of enjoying them for five hours as an official participant.
The only thing I can assure you is that the problems are really interesting.
Well don't pity too much because they will be available after contest as well
Yeah, but solving it officially has another taste.
Wait .. The problems are the same or something is changed ? I'm sure that if they aren't changed we'll see many noobs solving a,b,c,d.
im assuming you took the official contest? come on, don't spoil it :(
I'm sure they changed some stuff around to fit it into a 2 hour contest.
Nah i didn't it was for egipt participants.
egypt
as an official participant I can assure you that that's not gonna happen.
as an official participant i can assure you this guy is right
dont talk about noobs please XD
.
As an official participant .....i suppose that you don't submit a problem unless you are 100% sure of your submission...yeah,XOR is good for your health,too
Good Luck everyone
go
ORd luckXORving problemsANDhave funWait only 5 problems? This is weird
weird timing for India. This was used to be the timing of my hostel mess.
I have to sacrifice my dinner
me too
Wait what. Are colleges opened?
Too much bit manipulation convo above...Hoping to learn few new things from this contest.
Do you agree?
Can the contest be postponed please?
https://codeforces.me/blog/entry/89826
Anything else?
it will be great contest and thanks for you our firends from EOI all egyptions proud of you
Can someone tell my why ratings change are rolled back sometimes before contest. Just want to know out of curiosity .thank you
maybe they found cheaters and so they have to update ratings
.
Yeah Google kickstart time was so early morning, but I think contest timing is fine, it's 1 hr before usual 8 pm right, so what's the problem
.
Testers with names I can't pronounce :(
Next time please write that starting time of the round is unusual...
Noooo I remember that the contest started at 14:35 UTC :((. Miss the contest :((
.
How did you solve it? I couldn't solve it!
I include all the numbers from 1 to n-1 which have a modular inverse modulo n, which is distinct from the numbers itself. I'm not sure how to deal with the numbers which are self invertible(i.e. numbers which satisfy x^2=1 mod(n))
Take all numbers $$$i$$$ from $$$1$$$ to $$$n-1$$$ which have $$$\text{gcd}(i, n) = 1$$$, and also compute their product. Now the product modulo $$$n$$$ will be one of the chosen numbers, and if that is not $$$1$$$ then remove it. Modulo cannot be from other numbers otherwise the gcd of product will be not 1, so contradiction.
feeling exactly the same lol
Yeah, honestly, I don't know either whether and why my solution passed pretest. After looking at some low-n solutions which i brute-forced I did an educated guess: I chose all numbers which are coprime to the input, multiplied them from lowest to biggest and stopped at the highest count with modulo equal to 1. Hoping for more insight in the editorial.
Edit: At first i thought I should multiply all coprime numbers, but for some cases the biggest coprime sometimes didnt fit in...?
moduloforces
How to solve D ?
I tried solving it using square root decomposition but got TLE. https://codeforces.me/contest/1514/submission/113535222
I used this https://github.com/krnbatra/SPOJ-Solutions/blob/master/FREQ2.cpp, it passed the pretests but don't know about systests.
Lol even I was trying to find soln to FREQ2. After that it was trivial
Yeah same, I was also looking for the solution to this problem during contest.
Say the segment you're querying has length $$$n$$$ and the most common element appears $$$m$$$ times, then the answer is max($$$1,2m-n$$$) because on average odd segments give us $$$+\frac{1}{2}$$$ of the length and even segments give us $$$0$$$ (you have to check based on the parity of $$$m,n$$$ to be sure but it works out).
The problem reduces to finding the # of times the most common element appears quickly. If we store the positions of every element of value x in a vector, we can find out how many times it appears on [l,r] in O(log(n)) with binary search. Then, select 30 elements at random and query how many times they appear in [l,r], and take the maximum of those as your $$$m$$$.
This works because the problem is only 'interesting' when the most common element appears >n/2 times in the segment, so if we select at random the probability that it doesn't appear after selecting $$$30$$$ elements is <(1/2)^30 which is very small.
Ohh, the random selection step is really good! I was missing that. Thanks for the insight! :)
you mean max(1,2m-n) i think
not great, not terrible
Any hints for E? (please not the solution). I have no clues where to even start.
I solved C by googling "Product 1 Modulo N" lol
edit: well fuck me nevermind :^)
Can you share the link?
I read the upvoted answer in particular https://math.stackexchange.com/questions/441667/the-product-of-integers-relatively-prime-to-n-congruent-to-pm-1-pmod-n
Thanks
Funnily D is pretty much googlable too
A randomised solution for D:
For each segment let the frequency of the mode be f, now if $$$f$$$ $$$\leq$$$ $$$ceil((r-l+1)/2)$$$ the answer is 1, to calculate f we can select 40 random indices take the maximum of the frequency of the elements, the probability of the an element present on more than half the segment and not occurring in our search will be around 2^(-40).
Once we know f, if it is greater than $$$ceil((r-l+1)/2)$$$ we can binary search to calculate the number of parts.
How to solve B?
answer is pow(n,k)%10e9+7.i did it by guessing.as i am not highly rated.
Is this statement correct? - the sum of its elements is as large as possible. Is it means that we could put only 2^(k-1) and the last one 0?
We have n numbers and k bits for each number. For the AND of all numbers to be 0, for each of the k bits, there must be atleast one 0. For maximum sum, we take exactly one 0 in each of the k bits over all the n numbers. So, the total no. of arrays is n^k
Create a table with n columns and k rows. Fill every cell with either 0 or 1. Every column would represent one of our array's numbers in binary. Every row must have at least one cell with a value of 0 assigned to it. A row can't have more than a cell with 0, because our answer won't be maximum anymore. So we have to choose the cell with the value 0 in every row. So the first row has n possible case. The second one also has n possible cases and so on... So the answer would be pow(n, k).
how to solve C?
Problem D was basically a sub-problem of 840D — Destiny..
What kind of cancer is D. Why don't we all just optimise all day for the rest of our lives instead of actually solving problems ffs.
I feel that C was an easy score for anyone who is good at math. And so not obvious for others
I struggled all contest and turned out the answer is in the first google result of
Product 1 Modulo N:/can u explain for the same. i am noob at math or number theory
Unfortunately, me too
I solved it pretty much by some trials, errors and observations
Not idea whether it will pass system tests :lol:
For any x such that gcd(x, n) = 1, there is a unique inverse y in the modulo n field. Now, there are two possibilites: 1. y != x: We can include x, y in our set as x*y = 1 mod n 2. y = x: We cannot include x two times. Note that if x^2 = 1 mod n, (n-x)^2 is also 1 mod n. So, for every such x, we also have (n-x). Now, x*(n-x) = -1 mod n. So, we need another -1 mod n to compensate for this. So, we can pair up such (x, n — x) pairs to include them in our subsequence. Finally, (1, n — 1) is a special one. 1 can always be included. If there is some pair (x, n-x) left out after the above pairing, then we can include(x, n-x, n-1) in our subsequence.
I found the solution through this observation (admittedly it took me way too long to get the details right....):
So we know that every number we pick must be coprime with n (otherwise, we have some product * gcd(term, n) = 1 mod n, and this is not possible by some theorem of linear congruences). After this, we can recognize that every number that is coprime with n must have a modular inverse, and there are two cases here:
modular inverse != itself : then both should appear in the subsequence. (I think there is some intuition here, I had a stronger proof here but I forgot it : probably something like if one of the elements is in the subsequence, then the other one must be otherwise the product will not be = 1 mod n)
modular inverse == itself : I want to claim that we can separate this case by taking all of the numbers with this property, then picking some subset of this where the product = 1 mod n. I want to claim this set does not grow that large, since it's finding solutions to a^2 = 1 mod n and I think the solutions to this does not go past 4 (EDIT: maybe this can grow a bit larger? like 2 * distinct prime factors because of CRT, but I still don't think this grows very large). After this, just brute force over all combinations (I think I missed some observation here to make this simpler)
DISCLAIMER: My approach here is wrong.... Copy pasted from comment below: I think my method of brute forcing is just incorrect (the case that I am missing, apparently there are 31 integers such that x^2 = 1 mod n, x is coprime to n, and where n = 2 * 3 * 5 * 7 * 11 * 13, and it would not be possible to brute force all 2^31 of this (I would've expected TLE, but oh well).
This is kind of hand wavy, but I think the intuition is right and I can appreciate any other comments and whether or not it's correct.
NOTE: Apparently I failed system tests.... I feel like this approach is mostly correct though and maybe I just did something dumb somewhere here
Yeah the brute force can be improved as I've suggested above.
Yeah you're right, I can't believe I missed that...
And also, I think my method of brute forcing is just incorrect (the case that I am missing, apparently there are 31 integers such that x^2 = 1 mod n, x is coprime to n, and where n = 2 * 3 * 5 * 7 * 11 * 13, and it would not be possible to brute force all 2^31 of this (I would've expected TLE, but oh well).
yeah thanks for amazing insights...
i also feel like this approach is mostly correct...
but definitely added this type of thinking in my thinking set(thanks for this).
This is close, but the correct way is to notice that there are only two possibilities:
1) All coprime elements will be in the final array. This works iff their product is 1.
2) All except one coprime elements will be in the final array. If the product is P, then P itself must be coprime to N, and hence is in the array. If we remove P, we divide our product by P, and we are left with 1.
Yeah I realized this shortly after the round.... Not sure why I missed this observation, but it is definitely safer than what I tried. Do you know the fault in my "proof"? I found that the test case I am missing is exactly n = 2 * 3 * 5 * 7 * 11 * 13, and so there has to be something regarding my intuition on the number of solutions to x^2 = 1 mod n (even then, I can't see why I would miss a possible solution) or something else, but I'm missing it....
true
.
Given that it is a math round, it is a nice one, yes.
But it is still a math round, so no.
Today I learnt how to generate properly unbiased random numbers... ...about 2 minutes after the contest :/
Ouff, I now see what you meant. Did a solution after the contest using rand() and it failed testcase 3. With mt19937 it passed. (Well,
rand()only giving random numbers up to $$$2^{15}-1$$$ is somehow unfortunate...)Better luck next time, we all are learning. :)
Can someone please explain how to solve C. I am having tough time figuring it out.
Nice tutorial. It boils down to two observations:
Every number included must be coprime with n (else the product mod n is !=1)
If the product of all coprimes is among those coprimes, then simply remove it to get a product of 1. There cannot be a better solution since we cannot remove less than one number.
If a number is not coprime with n, then that doesn't necessarily make the product%n 0
You are right, corrected that part.
The product of all the coprimes is always amongst those coprimes, so that is always the solution in case 2
spookywooky Could You Prove it, please...
The problem D can use the similar idea with this problem 840D - Destiny.
Problems were not interesting at all specially A,B,C,D
for C, should p (product of all coprime in [1,N-1]) be 1 or N-1 ?? because I assumed it and accepted but couldn't prove it yet..
nvm I found the link bit above. Thanks! https://math.stackexchange.com/questions/441667/the-product-of-integers-relatively-prime-to-n-congruent-to-pm-1-pmod-n
I did not like the contest. Very weak pretests.
See this : https://codeforces.me/contest/1514/submission/113505545
By mistake I typed %- in place of %= in binpow function and it passed the pretests. Also if anyone know the meaning of %- then please tell me.
res%(-mod)
That statement does not do anything. It's like writing this statement
5;wer ratin chens ?
weak pretest.........
I don't know why C only had 9 pretests. I did a typo in my my sieve instead of 1e5 I wrote 1e4 still it passed pretests :(
this round and previous round both are insisting me to leave cp. As I think that cp=MATH and brain no place for programmers. What shall I do?
Create a contest without math.
Well you are grilling me.!
Well my contest is already on progress and we need E and F level div2 problems and our coordinator is too strict and you know who!
If someone is having E and F
My non randomized solution for D. The complexity is O(n * log^2(n) ). First maintain a sparse table which stores the an element which might appear more than [n/2] times.It does not store the most frequent element but what it stores is if an element appears more than ceil(n/2) times then it has to be this element. If that is not the case, then it might not be the most common element, THe sparse table is constructed as follows. for every i from one to n, sp[i][0] = a[i]; Then from every j from 1 to log2(n), sp[i][j] = either the element at the range is sp[i][j-1] or sp[i+pow2[j-1][j-1]. The element out of those two that is maximum can be calculated with lower bound ( by maintaining the pos vector array which stores the pos of a[i] ]. Then the query is just the same like constructing sparse table but instead we go from sp[l][l2[r-l+1]] or
sp[r-pow2[l2[r-l+1]] + 1 ][l2[r-l+1]]. This works because if the element appars more than ceil(n/2) times in a range, then the sparse table stores that element in that range. Please look at my submission https://codeforces.me/contest/1514/submission/113525530
To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
thank you this really saves the time people waste looking for rating change
Trump_Constructs_China solve C in 10 seconds with different code style?Looks weird
Can some one please tell me why I am getting wrong answer on testcase 1(for A question) only when I ran it in Codeforces machine , but getting correct answer when I ran in my machine or codechef ide ,this is the link for my submission , can some one please help me.
probably because you are comparing integer with double
I changed it to double still , see this link
In my experience using relational operators on real point numbers is very tricky. Sometimes 8.0 is not equal to 8.00000. Things like these happen. Thus I try to avoid it or use epsilon in dire cases. It would be great if someone else shares how they compare doubles
Put int instead of double
yeah my bad !! realised error
Doubt in Problem D (MO's Algo solution):
Can someone give a possible reason of why this 113542641 gave AC and took 717ms while this 113538699 gave TLE.
Can anyone share a python solution that can pass all the test in problem 4, within 2 seconds? It seems that nobody pass problem 4 during the contest with python solution.
It seems the only python submission with decent timings is this
https://codeforces.me/contest/1514/submission/113542503
Slightly above the requsted 2 seconds, but with wide margin until tle
The time limit for problem D seems too tight for slower coding lauguage, especially python.
The problem D time limit is 3 seconds, and it is based on random sampling. The number sampled per query should be at least 30 to make the probability of success per test set be at least 99.99%. Other solution with no sampling will get TLE in python.
However, if you use pyhton, there is no pypy3 users to pass all the tests, and only 1 user passed pypy2, with 2870ms, very close to time limit.
Therefore, There will be dilemma for python users. If you decrease the sampling number per query, you will increase the probabilities to get WA, if you increase the sampling number, you will be more likely to get TLE. You need to adjust your sample number per query very very carefully, maybe between 25 and 30.
So, I think it will be better if they can re-judge solution with higher time limits. If not, the problem can state (solution with slower programming language may not pass) in the end, to let the python user switch language for this problem before wasting too much time on it.
After all, It will be frustrating for them to get TLE from time to time only because they use the wrong language, not because they use inefficient algorithm.
I'm not sure where you got the impression of "Python should pass somewhat hard problems comfortably", but it's wrong. Problem authors can't let python pass without allowing other more inefficient solutions in efficient languages (such as sqrtlog MO's in this case) to pass. As I've previously mentioned, I believe that it is up to you to find a language which will get AC for a problem.
As mentioned in that thread, we could increase the time-limit for python to compensate for the constant-multiple slowdown compared to other languages. Many other online judges increase time limit for python (not sure how much... 1.5x? 2x?). As someone who really likes python, I would love it if codeforces did this as well. (Of course, I understand the difficulties of doing so: like figuring out what the proper constant multiple is in order to make sure the python limit is appropriate.)
OK, it seems that letting the contest be python friendly is not feasible, thanks to @skittles1412 's statement, I have looked around and see many suggestions to increase the time limit for python are down voted heavily, maybe my comments will be down voted too.
I just hope anyone who complain about the slowness of python or increase the time limit for python will not be down voted heavily. Since they have already been frustrated when they get TLE in python, they will be more frustrated if they get many down votes and ruined their reputation.
I think that the TL was somewhat tight, even if you didn't try to solve it in Python.
As for solving this problem in Python, there are 2 things which you want to consider here:
Random.randint is slow in Python. Normally you don't notice it, but on problems like this you probably want to get around that somehow. (I think all the random calls takes > 1 s)
Import random is kind slow in Python (like 200 ms). There is a "hack" to get around this.
With these two fixed my PyPy2 solution runs in 2.2 s. 113542503.
Btw note that I TLE uphacked my own in contest PyPy2 solution. It kind of abused early exits to get under the TL, and was hackable with a randomized max test case.
D is from COCI 2009/2010 contest #3 https://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf
For Problem A — Perfectly imperfect array If the array is 2 2 3 3 , the product of the subsequence is 2*2*3*3= 36 which is a perfect square. But the solution is otherwise. Can anybody explain?
The problem asks if there is any non empty subsequence that...
Did you have a way to generate test that defeat the Hilbert curve MO optimization ? When I ran D with Hilbert it just TLE but when I use up down query sorting it worked fine.
I understood B by the n^k approach but below is the approach which I thought and I think it is correct but unable to spot the fault in thinking. So this is what I thought, As we want the sum of array to be max and also bitwise AND of all elements to be 0, I considered the array, 0,2^k-1,2^k-1...(n-1 times 2^k-1 and 1 time 0) we will have n type of such array because we can put 0 in n different positions the next array is 1,2^k-2,2^k-1,2^k-1....(n-2 times 2^k-1 and 1 time 1 and 2^k-2)which also results in same max sum and AND of the whole array to be 0. we will have nC2 i.e. n*(n-1) Similarly the next array will be: 2,2^k-3,2^k-1,2^k-1....(n-2 times 2^k-1 and 1 time 2 and 2^k-3) ''' again we will have nC2 type of such arrays. If we observe we will have (2^k — 1)/2 of such arrays(excluding the 0 2^k-1 array). Therefore our answer will be:```
ans = n + (2^k — 1)/2 * n * (n-1); If anybody knows what goes wrong in this approach, help would be appreciated Thanks in advance
I lost pupil, because I also thought so
for n=4; k=3; Your solution doesn't consider the case 3 5 6 7 (sum=21) (same as 0 7 7 7). you are taking 2^k -1 as many times as possible and compensating the AND criteria by taking a very small number(such as 0) but we also have to look at the case, where we can take all the elements from a middle range such that the sum is still maxed, and the AND criteria is also satisfied.
[Deleted]
I highly doubt Trump_constructs_China's submissions and rank. Could you take a look?
You have amazing graph (*_*)
My contest was skipped as some of the solutions were found similar. These are the issues I received:
For Question A:
Attention! Your solution 113490501 for the problem 1514A significantly coincides with solutions blue_meth/113489968, 123thunderbuddie/113490501. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked
The question was pretty easy and small so quite a few people come up with the same logic and it was a clear case of coincidence.
For Question D:
Attention! Your solution 113518019 for the problem 1514D significantly coincides with solutions blue_meth/113516368, 123thunderbuddie/113518019. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
For this question I used the open source code found at the following link: https://github.com/krnbatra/SPOJ-Solutions/blob/master/FREQ2.cpp
I kindly ask the testers and the setters to look into this and tell me if I have indeed made a mistake.
Like it can be true that the solution for A is basic and it can be same for you and blue_meth. But how it can be possible that you both got same intution for github repo solution ?
That is the first link that comes up when you search about the FREQ2 question of SPOJ. That's the most famous question on Mo's Algorithm
I second this.
It indeed is sheer coincidence that our submission to 1514A is similar. I believe it is a pretty straightforward question and many people have come up with similar implementations. Nonetheless, our coding style is different.
For 1514D, I have used the same template which was published and available online before the contest began. I have cited the same in my submission. I can see many others using the same template in the ranklist.
I request the setters to rectify this!
.
And what were the results of the Egyptian IOI qualification? How many problems one was required to solve to qualify for the IOI?