### mohammedehab2002's blog

By mohammedehab2002, 3 weeks ago,

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:

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

• +639

 » 3 weeks ago, # |   +421 As a setter give me contribution.
•  » » 3 weeks ago, # ^ |   +15 ok i upvoted. i am sure this round will be great!
•  » » » 3 weeks ago, # ^ |   0 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.com/contest/1514/submission/113537817 I just changed 1 line and it was accepted.
•  » » 3 weeks ago, # ^ |   0 Definitely
 » 3 weeks ago, # |   0 Two types of tester — ( official contest and Round )
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -97 And sadly you are in none of them :(PS: While(downvotes>0)sad++;
 » 3 weeks ago, # |   +58 mohammedehab2002 and his love for XOR problems.
 » 3 weeks ago, # |   +26 antontrygubO_o for rejecting all our problems without reading them. LoL
 » 3 weeks ago, # | ← Rev. 2 →   +29 Problem D will be a XOR problem. I can tell.Can't wait for the contest!
 » 3 weeks ago, # |   +54 As an official contestant, The problems are very interesting and you will enjoy solving them.
•  » » 3 weeks ago, # ^ |   +53 Is it likely that some potential participants have already seen these Egyptian IOI qualification problems long before the contest?
•  » » » 3 weeks ago, # ^ |   0 They will not take part of the contest on codeforces
•  » » 3 weeks ago, # ^ |   0 Ummmm..ok
 » 3 weeks ago, # |   +16 maths problems incoming
 » 3 weeks ago, # |   +83 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.
•  » » 3 weeks ago, # ^ |   -53 yes, April is full of endsems for me, please delay all rounds by a month, so that I can participate.
•  » » » 3 weeks ago, # ^ |   +78 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.
•  » » » » 3 weeks ago, # ^ |   +22 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.
•  » » 3 weeks ago, # ^ |   +15 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 ! =)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +22 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.
•  » » » 3 weeks ago, # ^ |   +15 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).
 » 3 weeks ago, # |   -29 IslamForces
•  » » 3 weeks ago, # ^ |   -36 It ain't funny, got a problem with muslims?
 » 3 weeks ago, # |   +6 Notice the unusual starting time :)
•  » » 3 weeks ago, # ^ |   0 I didn't, which stopped me from getting +100 rating. Oh well, next time I guess!
 » 3 weeks ago, # |   +101 Codeforces Round #716 (Div. 2), writer: mohammedehab2002
 » 3 weeks ago, # |   +46 Div 2 IOI qualifications o_O
•  » » 3 weeks ago, # ^ |   +7 It is not like what you think. Problems had subtasks in the IOI TST. Also, the problems are really interesting!
•  » » » 3 weeks ago, # ^ |   +28 It's just weird not to see div 1 when doing this)
•  » » » » 3 weeks ago, # ^ |   +106 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.
•  » » » » » 3 weeks ago, # ^ |   -12 Another div1.5 goes brrrr
 » 3 weeks ago, # |   +9 NOTICE THE UNUSUAL START TIME.
 » 3 weeks ago, # |   -18 Although the same age (2002), they are red and I am black :"(
•  » » 3 weeks ago, # ^ |   -45 RACISM Intensifies
 » 3 weeks ago, # |   +11 5 problems but 2:15 hours!!!
 » 3 weeks ago, # |   -25 As a nobody give me contribution.
•  » » 3 weeks ago, # ^ |   +5 you are a participant right?
•  » » » 3 weeks ago, # ^ |   -6 I am nobody(even if I'm a participant).
 » 3 weeks ago, # |   +63 xorz
 » 3 weeks ago, # |   +94
 » 3 weeks ago, # |   +30 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.
•  » » 3 weeks ago, # ^ |   +37 Well don't pity too much because they will be available after contest as well
•  » » » 3 weeks ago, # ^ |   +12 Yeah, but solving it officially has another taste.
 » 3 weeks ago, # |   0 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.
•  » » 3 weeks ago, # ^ |   +11 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.
•  » » » 3 weeks ago, # ^ |   +7 Nah i didn't it was for egipt participants.
•  » » » » 3 weeks ago, # ^ |   +9 egypt
•  » » 3 weeks ago, # ^ |   +14 as an official participant I can assure you that that's not gonna happen.
•  » » » 3 weeks ago, # ^ |   +1 as an official participant i can assure you this guy is right
•  » » 3 weeks ago, # ^ |   0 dont talk about noobs please XD
 » 3 weeks ago, # | ← Rev. 2 →   +14 .
 » 3 weeks ago, # | ← Rev. 2 →   +10 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
 » 3 weeks ago, # |   +9 Good Luck everyone
 » 3 weeks ago, # |   +6 goORd luck XORving problems AND have fun
 » 3 weeks ago, # |   +6 Wait only 5 problems? This is weird
 » 3 weeks ago, # |   0 weird timing for India. This was used to be the timing of my hostel mess.
•  » » 3 weeks ago, # ^ |   +6 I have to sacrifice my dinner
•  » » » 3 weeks ago, # ^ |   +3 me too
•  » » 3 weeks ago, # ^ |   +12 Wait what. Are colleges opened?
 » 3 weeks ago, # | ← Rev. 2 →   +1 Too much bit manipulation convo above...Hoping to learn few new things from this contest.Do you agree?
 » 3 weeks ago, # |   -11 Can the contest be postponed please?https://codeforces.com/blog/entry/89826
•  » » 3 weeks ago, # ^ |   +18 Anything else?
•  » » » 3 weeks ago, # ^ |   0 No nothing else
 » 3 weeks ago, # |   0 it will be great contest and thanks for you our firends from EOI all egyptions proud of you
 » 3 weeks ago, # |   0 Can someone tell my why ratings change are rolled back sometimes before contest. Just want to know out of curiosity .thank you
•  » » 3 weeks ago, # ^ |   +3 maybe they found cheaters and so they have to update ratings
 » 3 weeks ago, # | ← Rev. 2 →   0 .
•  » » 3 weeks ago, # ^ |   0 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
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 .
 » 3 weeks ago, # | ← Rev. 2 →   0 ❤❤❤
 » 3 weeks ago, # |   +3 Testers with names I can't pronounce :(
 » 3 weeks ago, # |   +26 Next time please write that starting time of the round is unusual...
 » 3 weeks ago, # |   +10 Noooo I remember that the contest started at 14:35 UTC :((. Miss the contest :((
 » 3 weeks ago, # |   -17 Solve 4 problems easilycan't solve Etry to hack someonefind that everyone hacks a lot but every program in my room is perfect
 » 3 weeks ago, # |   +49 Me after passing pretests in problem C without knowing why
•  » » 3 weeks ago, # ^ |   +6 How did you solve it? I couldn't solve it!
•  » » » 3 weeks ago, # ^ |   +3 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))
•  » » » 3 weeks ago, # ^ |   0 for [1,n-2] add i to ans if (gcd(i,n)==1) also do product modulo at same time, now if (product*(n-1))%n => add n-1 to ans, else if(product%n==1) => print ans, else cout<<"1";But i think it may FST ;)
•  » » » 3 weeks ago, # ^ |   0 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.
•  » » 3 weeks ago, # ^ |   0 feeling exactly the same lol
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 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...?
 » 3 weeks ago, # |   +2 moduloforces
 » 3 weeks ago, # |   0 How to solve D ?
•  » » 3 weeks ago, # ^ |   +6 I tried solving it using square root decomposition but got TLE. https://codeforces.com/contest/1514/submission/113535222
•  » » » 3 weeks ago, # ^ |   0 I used this https://github.com/krnbatra/SPOJ-Solutions/blob/master/FREQ2.cpp, it passed the pretests but don't know about systests.
•  » » » » 3 weeks ago, # ^ |   +1 Lol even I was trying to find soln to FREQ2. After that it was trivial
•  » » » » » 3 weeks ago, # ^ |   0 Yeah same, I was also looking for the solution to this problem during contest.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +9 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.
•  » » » 3 weeks ago, # ^ |   +5 Ohh, the random selection step is really good! I was missing that. Thanks for the insight! :)
•  » » » 3 weeks ago, # ^ |   0 you mean max(1,2m-n) i think
 » 3 weeks ago, # |   -21 Very balanced set according to me. I had a lot of fun.
 » 3 weeks ago, # |   +3 not great, not terrible
 » 3 weeks ago, # |   +8 Any hints for E? (please not the solution). I have no clues where to even start.
 » 3 weeks ago, # | ← Rev. 2 →   +7 I solved C by googling "Product 1 Modulo N" loledit: well fuck me nevermind :^)
•  » » 3 weeks ago, # ^ |   0 Can you share the link?
•  » » » 3 weeks ago, # ^ |   0 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
•  » » » » 3 weeks ago, # ^ |   0 Thanks
•  » » 3 weeks ago, # ^ |   +3 Funnily D is pretty much googlable too
 » 3 weeks ago, # | ← Rev. 4 →   +30 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.
 » 3 weeks ago, # |   +3 How to solve B?
•  » » 3 weeks ago, # ^ |   +3 answer is pow(n,k)%10e9+7.i did it by guessing.as i am not highly rated.
•  » » 3 weeks ago, # ^ |   +1 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?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   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
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 how can you be sure that all n^k would have maximum sum UPD: GOT IT
•  » » 3 weeks ago, # ^ |   0 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).
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 Since numbers can be equal, it is best to choose all the numbers equal which is 2^k-1. But we also have to make sure that the AND of all the chosen number is 0, which greedily can be thought as choosing one number whose all the bits are 0. So, if we had n=4, k=3, this would be our selection 1 1 1 1 1 1 0 0 0 This is just one possible arrangement of bits, for all possible arrangements, we can shift the 0 bit in each position to (n-1) other positions in the previous numbers. Similarly every 0-set 'k' bits can be assigned to 'n' numbers. Therefore, the total number of ways to assign 0's is the answer, which is n*n*n*n..(k times).
 » 3 weeks ago, # |   +3 how to solve C?
 » 3 weeks ago, # | ← Rev. 2 →   0 Problem D was basically a sub-problem of 840D — Destiny..
 » 3 weeks ago, # |   +30 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.
 » 3 weeks ago, # |   +19 I feel that C was an easy score for anyone who is good at math. And so not obvious for others
•  » » 3 weeks ago, # ^ |   +3 I struggled all contest and turned out the answer is in the first google result of Product 1 Modulo N :/
•  » » 3 weeks ago, # ^ |   0 can u explain for the same. i am noob at math or number theory
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Unfortunately, me tooI solved it pretty much by some trials, errors and observationsNot idea whether it will pass system tests :lol:
•  » » » 3 weeks ago, # ^ |   +3 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.
•  » » » 3 weeks ago, # ^ | ← Rev. 4 →   +8 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
•  » » » » 3 weeks ago, # ^ |   +1 Yeah the brute force can be improved as I've suggested above.
•  » » » » » 3 weeks ago, # ^ |   0 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).
•  » » » » 3 weeks ago, # ^ |   0 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).
•  » » » » 3 weeks ago, # ^ |   +1 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.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 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....
•  » » 3 weeks ago, # ^ |   0 true
 » 3 weeks ago, # | ← Rev. 2 →   -14 .
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +31 Given that it is a math round, it is a nice one, yes.But it is still a math round, so no.
 » 3 weeks ago, # |   +3 Today I learnt how to generate properly unbiased random numbers... ...about 2 minutes after the contest :/
•  » » 3 weeks ago, # ^ |   0 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. :)
 » 3 weeks ago, # |   0 Can someone please explain how to solve C. I am having tough time figuring it out.
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   0 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.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 If a number is not coprime with n, then that doesn't necessarily make the product%n 0
•  » » » » 3 weeks ago, # ^ |   0 You are right, corrected that part.
•  » » » 3 weeks ago, # ^ |   +3 The product of all the coprimes is always amongst those coprimes, so that is always the solution in case 2
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 spookywooky Could You Prove it, please...
 » 3 weeks ago, # |   0 The problem D can use the similar idea with this problem 840D - Destiny.
 » 3 weeks ago, # |   +31 Problems were not interesting at all specially A,B,C,D
 » 3 weeks ago, # |   0 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..
•  » » 3 weeks ago, # ^ |   0 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
 » 3 weeks ago, # |   -6 Solutions for Problem A :- https://www.youtube.com/watch?v=1IUBsnat5nE Problem B :- https://www.youtube.com/watch?v=cLyzvl2IUq4
 » 3 weeks ago, # |   +1 I did not like the contest. Very weak pretests. See this : https://codeforces.com/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.
•  » » 3 weeks ago, # ^ |   0 res%(-mod)
•  » » 3 weeks ago, # ^ |   0 That statement does not do anything. It's like writing this statement 5;
 » 3 weeks ago, # |   +7 wer ratin chens ?
 » 3 weeks ago, # |   0 weak pretest.........
•  » » 3 weeks ago, # ^ |   0 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 :(
•  » » » 3 weeks ago, # ^ |   0 matter of regret brother......
 » 3 weeks ago, # |   -14 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?
•  » » 3 weeks ago, # ^ |   +28 Create a contest without math.
•  » » » 3 weeks ago, # ^ |   -8 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
 » 3 weeks ago, # |   0 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.com/contest/1514/submission/113525530
 » 3 weeks ago, # | ← Rev. 2 →   +46 To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
•  » » 3 weeks ago, # ^ |   +1 thank you this really saves the time people waste looking for rating change
•  » » 3 weeks ago, # ^ |   +43 Trump_Constructs_China solve C in 10 seconds with different code style?Looks weird
 » 3 weeks ago, # | ← Rev. 3 →   0 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.
•  » » 3 weeks ago, # ^ |   0 probably because you are comparing integer with double
•  » » » 3 weeks ago, # ^ |   0 I changed it to double still , see this link
•  » » » » 3 weeks ago, # ^ |   0 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
•  » » 3 weeks ago, # ^ |   +1 Put int instead of double
•  » » » 3 weeks ago, # ^ |   0 yeah my bad !! realised error
 » 3 weeks ago, # |   0 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.
 » 3 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 It seems the only python submission with decent timings is thishttps://codeforces.com/contest/1514/submission/113542503Slightly above the requsted 2 seconds, but with wide margin until tle
 » 3 weeks ago, # | ← Rev. 6 →   +5 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.
•  » » 3 weeks ago, # ^ |   +33 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.
•  » » » 3 weeks ago, # ^ |   0 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.)
•  » » 3 weeks ago, # ^ |   0 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.
•  » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   +15 D is from COCI 2009/2010 contest #3 https://hsin.hr/coci/archive/2009_2010/contest3_tasks.pdf
 » 3 weeks ago, # |   0 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?
•  » » 3 weeks ago, # ^ |   0 The problem asks if there is any non empty subsequence that...
 » 3 weeks ago, # |   0 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.
 » 3 weeks ago, # |   0 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
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 I lost pupil, because I also thought so
•  » » 2 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   0 Why does it show as unrated on my profile?
 » 3 weeks ago, # | ← Rev. 2 →   -12 Regarding the same submission matter, 3 months back when i forgot the password of my codeforces id, I created a new user account on codeforces but someone told me that you can reset the password so I reset my password of first id and stopped using my new codeforces id. You can check the new id for less problem submission and inactivity. During yesterday's contest my auto login of new id was saved I forgot that and submitted the solution for 1st problem. After realising that I immediately switched to my old id and started giving the contest due to which my only submission for 1st problem matches. Sorry it was an unintended mistake.It'll never repeat in future.Kindly delete my other id I_Love_Mia You can check mine this id that I've Given many contests and problem solved . Kindly give my rating back MikeMirzayanov
 » 3 weeks ago, # |   +27 I highly doubt Trump_constructs_China's submissions and rank. Could you take a look?
•  » » 3 weeks ago, # ^ |   +1 You have amazing graph (*_*)