mohammedehab2002's blog

By mohammedehab2002, 4 years ago, In English

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:-

  1. neal
  2. Savior-of-Cross
  3. Geothermal
  4. cookiedoth
  5. Tlatoani

Div.2:-

  1. alya_wow
  2. DatChelsea
  3. Trump_Constructs_China
  4. Dolodu123
  5. Kazaoka_Mari

Good luck & Have fun :D

  • Vote: I like it
  • +639
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +421 Vote: I do not like it

As a setter give me contribution.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Two types of tester — ( official contest and Round )

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -97 Vote: I do not like it

    And sadly you are in none of them :(

    PS: While(downvotes>0)sad++;

»
4 years ago, # |
  Vote: I like it +58 Vote: I do not like it

mohammedehab2002 and his love for XOR problems.

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

antontrygubO_o for rejecting all our problems without reading them.
LoL

»
4 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

Problem D will be a XOR problem. I can tell.

Can't wait for the contest!

»
4 years ago, # |
  Vote: I like it +54 Vote: I do not like it

As an official contestant, The problems are very interesting and you will enjoy solving them.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    Is it likely that some potential participants have already seen these Egyptian IOI qualification problems long before the contest?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      They will not take part of the contest on codeforces

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

maths problems incoming

»
4 years ago, # |
  Vote: I like it +83 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -53 Vote: I do not like it

    yes, April is full of endsems for me, please delay all rounds by a month, so that I can participate.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +78 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 ! =)

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      If that really is the case, then how about:

      1. Trying to place those contests on weekends, when I guess there'd be no official working hours.

      2. 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).

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Notice the unusual starting time :)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't, which stopped me from getting +100 rating. Oh well, next time I guess!

»
4 years ago, # |
  Vote: I like it +101 Vote: I do not like it

Codeforces Round #716 (Div. 2), writer: mohammedehab2002

»
4 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Div 2 IOI qualifications o_O

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    It is not like what you think. Problems had subtasks in the IOI TST. Also, the problems are really interesting!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      It's just weird not to see div 1 when doing this)

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +106 Vote: I do not like it

        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.

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

NOTICE THE UNUSUAL START TIME.

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

5 problems but 2:15 hours!!!

»
4 years ago, # |
  Vote: I like it -25 Vote: I do not like it

As a nobody give me contribution.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    you are a participant right?

»
4 years ago, # |
  Vote: I like it +63 Vote: I do not like it

xorz

»
4 years ago, # |
  Vote: I like it +94 Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Well don't pity too much because they will be available after contest as well

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    as an official participant I can assure you that that's not gonna happen.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      as an official participant i can assure you this guy is right

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dont talk about noobs please XD

»
4 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

.

»
4 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Good Luck everyone

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

goORd luck XORving problems AND have fun

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Wait only 5 problems? This is weird

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

weird timing for India. This was used to be the timing of my hostel mess.

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Too much bit manipulation convo above...Hoping to learn few new things from this contest.

Do you agree?

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Can the contest be postponed please?

https://codeforces.net/blog/entry/89826

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it will be great contest and thanks for you our firends from EOI all egyptions proud of you

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell my why ratings change are rolled back sometimes before contest. Just want to know out of curiosity .thank you

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    maybe they found cheaters and so they have to update ratings

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Testers with names I can't pronounce :(

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Next time please write that starting time of the round is unusual...

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Noooo I remember that the contest started at 14:35 UTC :((. Miss the contest :((

»
4 years ago, # |
Rev. 2   Vote: I like it +49 Vote: I do not like it

.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    How did you solve it? I couldn't solve it!

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like 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))

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    feeling exactly the same lol

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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...?

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

moduloforces

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I tried solving it using square root decomposition but got TLE. https://codeforces.net/contest/1514/submission/113535222

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Ohh, the random selection step is really good! I was missing that. Thanks for the insight! :)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you mean max(1,2m-n) i think

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

not great, not terrible

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Any hints for E? (please not the solution). I have no clues where to even start.

»
4 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

I solved C by googling "Product 1 Modulo N" lol

edit: well fuck me nevermind :^)

»
4 years ago, # |
Rev. 4   Vote: I like it +30 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve B?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    answer is pow(n,k)%10e9+7.i did it by guessing.as i am not highly rated.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve C?

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem D was basically a sub-problem of 840D — Destiny..

»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I feel that C was an easy score for anyone who is good at math. And so not obvious for others

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I struggled all contest and turned out the answer is in the first google result of Product 1 Modulo N :/

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain for the same. i am noob at math or number theory

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Unfortunately, me too

      I solved it pretty much by some trials, errors and observations

      Not idea whether it will pass system tests :lol:

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 4   Vote: I like it +8 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yeah the brute force can be improved as I've suggested above.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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).

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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).

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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....

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    true

»
4 years ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +31 Vote: I do not like it

    Given that it is a math round, it is a nice one, yes.

    But it is still a math round, so no.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Today I learnt how to generate properly unbiased random numbers... ...about 2 minutes after the contest :/

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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. :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain how to solve C. I am having tough time figuring it out.

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Nice tutorial. It boils down to two observations:

    1. Every number included must be coprime with n (else the product mod n is !=1)

    2. 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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem D can use the similar idea with this problem 840D - Destiny.

»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Problems were not interesting at all specially A,B,C,D

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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..

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I did not like the contest. Very weak pretests.
See this : https://codeforces.net/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.

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

wer ratin chens ?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

weak pretest.........

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :(

»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Create a contest without math.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.net/contest/1514/submission/113525530

»
4 years ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    probably because you are comparing integer with double

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I changed it to double still , see this link

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Put int instead of double

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
Rev. 6   Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    1. 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)

    2. 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.

»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem asks if there is any non empty subsequence that...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I lost pupil, because I also thought so

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
Rev. 3   Vote: I like it -12 Vote: I do not like it

[Deleted]

»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I highly doubt Trump_constructs_China's submissions and rank. Could you take a look?

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.net/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.net/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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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!

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

And what were the results of the Egyptian IOI qualification? How many problems one was required to solve to qualify for the IOI?