Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

By awoo, history, 5 years ago, translation, In English

Hello Codeforces!

On Oct/24/2019 18:05 (Moscow time) Educational Codeforces Round 75 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hello Codeforces,

We would like to invite all of you to Mike Mirzayanov's course Advanced Algorithms and Data Structures, which will take place in Barcelona, from the 6th to 24th of January, 2020.

The course will consist of three weeks of training, 5 training days each week. The program includes daily lectures and practical exercises. It will be quite educational, insightful and entertaining!

And you will have the opportunity to meet and talk with Mike, who will be happy to share his knowledge and stories about the history of Codeforces.

We are happy to offer a special price of 1,000 EUR* for all Codeforces users.

Register on the page below and we will contact you for the next steps. Hurry up! Only 10 spots available.

* The cost does not include travel or accommodation.

REGISTER HERE→

We would also like to recommend you an article published on our blog last week about the 5 reasons why traditional universities can’t keep up with humanity.

UPD: The start of the round is postponed by 30 minutes.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 199
2 Anadi 7 205
3 risujiroh 7 208
4 imeimi 7 229
5 jiangly 7 273

96 successful hacks and 196 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A cxk0707 0:02
B wangziji 0:05
C Bohun 0:06
D guyan 0:16
E1 TwentyOneHundredOrBust 0:15
E2 TwentyOneHundredOrBust 0:14
F Radewoosh 0:19

UPD: Editorial is out

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the statement will be clear and simple this time .

»
5 years ago, # |
  Vote: I like it +104 Vote: I do not like it

We are happy to offer a special price of 1,000 EUR* for all Codeforces users.

Is it more expensive for Codeforces users than for other people? 1.000 EUR without accomodation and travel. Wow

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

Can anybody tell me the difference between Educational Codeforces Round XX and Codeforces Round XX? Thanks in advance.

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

Please try to put an interactive problem.

They are interesting to solve.

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

    Problemset has already been prepared

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

    Yes, I agree on some part with you, they are interesting to solve, but the very code for maintaining the query limit, and doing query at various steps is a bit frustrating,not to forget the flushing of output.I cannot copy paste the test cases :(

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

      Don't name it as frustrating call it as challenging.

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

I think MikeMirzayanov should once conduct a course on DSA in India.

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

    Yes, it would have much registrations.

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

    Any particular reason why you mentioned India?

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

      "Because everyone wants to learn".

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

        So other countries people don't want to learn?

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

          Did I say that? I am saying that he should also conduct once in India.

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

            Some people just want to watch the world learn.

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

      Because India has highest number of people who want to do coding. Maximum participation is always from India

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

        Yeah, but how many people will participate because it certainly will not be free

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

          As enthusiastically as they participate in ICPC(" It is also not free ").

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

            See charges in the blog entry a special price of 1000 euros, I don't know how this charges will translate into INR but it will be high, how much are you ready to pay if you get a training from him?

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

          Yeah, you are right at this

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

Is it just me or nobody can see any top rated users??? not a single user in the page.!

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

delayed!

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

The start of the round is postponed by 30 minutes.


Начало раунда отложено на 30 минут.

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

I don't like when contests are delayed

It ruins the organization of our days. 30 minutes is a lot.

But I can understand, if there's an issue with the problems. Better to delay + fix. :/

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

I wanted to give the round badly but it looks like I can't :( because I have to catch a train by 23:00 IST. All the best to everyone out there and I wish everyone a high rating :)

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

It's frustrating to wait for another half n hour.

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

    But it was life saver for me as the prev time for contest was clashing with the dinner time in my college XD

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

      It nearly clashes with every college's dinner timing...but we can manage

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

Why delay :/ Now I won't be able to participate.

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

Delayforces is back 8)

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

Hooray! Now i can finish my dinner.

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

In fact, I had to go to sleep later because of the contest been put off :( (start at 23:05 here)

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

I think it is better to delay the contest, than to have huge queue time's or unresponsive contest page....

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

    let's look at the timeline

    CF has bad performance lately

    everyone is mad about long queue and 504

    13000 registrants for this round, incredibly high

    the lovely pikmisha delays the round

    bunch of people have to go sleep or leave for other things

    less people participating in the round

    this time 504 only lasts for a minute

    coincidence? i think not

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

A Bad Day :(

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

    I had a very bad day too. Didn't have a good idea for B & C. That's strange because these days I spend hours practicing on much harder problems. I found D much easier than C. I spent too much time on C and B and couldn't come up with a solution.

    Finally, near to the end of contest, I submitted solutions for B & D and it got Accepted. However, my ranking is currently 1900 something and I would probably get back to blue. It was a really bad day!

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

    Well,I think my template of NTT needs changing :(

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

I am still unable to solve C in Contest. WTF am I?

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

    I wasn't even able to solve B, even though I believe I came up with a correct solution! Such a disappointment for me as well. :(

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

      Let's practice more together :'(

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

How to solve D?

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

    Binary search for the answer.

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

      I was doing the same(binary search) but Wa on test 2 can you explain your idea ?

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

        Yes, of course. So, to check if one answer $$$X$$$ is valid, we need to have at least $$$n/2 + 1$$$ numbers >= $$$X$$$ in our set of numbers. After having all this numbers, we exclude the ones that decrese the most our sum (from $$$X$$$ to $$$l_i$$$).

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

        maybe u missed that for employees that you are assigning as >= median they may have L more than the median value thats what stuck me on test 2.

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

I thought E1 was pretty pointless, it would be better if it was replaced by a task with difficulty between D and E2?

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

The questions were really nice they challenged my implementation skills, kudos to the setter

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

Is F solvable without FFT? I know a solution where you need to calculate $$$(1+2 \cdot x)^a \cdot (1 + 2 \cdot x + x^2)^b$$$ or something like that—is it the only way to do it?

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

    I solved it using NTT in $$$\mathcal{O}(kn \log{} n)$$$.

    First if we look at coefficient of $$$x^j$$$ in $$$(1 + 2 \cdot x)^a$$$ then it is equal to $$$\binom{a}{j} \cdot 2^j$$$. Similarly coefficient of $$$x^j$$$ in $$$(1 + 2 \cdot x + x^2)^b$$$ is $$$\binom{2 \cdot b}{j}$$$.

    Now it's enough to use one NTT/FFT to evaluate this multiplication. But I think it was possible to get accepted on solution you described.

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

What would be the right way to approach E1 or E2?

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

    We can approach it in a greedy fashion.

    First of all, consider each voter as a pair (Mi, Pi) and sort all the pairs in ascending order of the Mi values.

    Now lets iterate in the reverse order (i.e from the voter with highest Mi value to the one with the least).

    We want to be sure that we are buying a vote only when its necessary, do be sure of this lets define whats the necessary condition of buying a vote.

    Suppose we are at index i (when iterating backwards), and have purchased cnt votes from the suffix of voters [i + 1, n], and in the worst case scenario we can buy votes from every voter in the prefix [1, i — 1], thus getting a total of i-1 votes from them. So at best we can have (i — 1 + cnt) votes.

    If (i — 1 + cnt) < Mi, we are forced to buy a vote thus this is our necessary condition.

    To buy a vote we can use a minheap which at any index j stores the values Pk for all voters k from j to n, whose vote we have not bought yet. If after checking for the necessary condition to buy a vote at index i, there is a need to buy a vote, we can take the minimum value of Pk from the heap and increment cnt and add this cost to our result, otherwise we keep iterating backwards.

    Implementation of the above idea: 63349135

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

      I found that sorting cost $$$p_i$$$ for the same $$$m_i$$$ dont matter, but I cant tell why. Some one have idea?

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

      Can anyone provide more formal proof? Thank you

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

WA test 2.

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

    Checked your submissions on your profile, TC 2 hit you hard.

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

      Darn. I got WA on TC 2 for each of B, C, D too before AC, but this was...

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

How to solve C ?? and D, was it binary search ?

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

    For C, note that if you divide the number into vectors of odd and even integers, you can see that you will always be able to get any merged sequence of those two vectors. Then just merge as in mergesort. For D, you can just binary search and use greedy.

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

      I did the same, but why this code gives TLE? any help.

      https://mirror.codeforces.com/contest/1251/submission/63335135

      Thank you :)

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

        You were making a vector of a large size for every test case. In this case, it would be easier to push_back elements, and would also pass the limits.

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

      Can you explain 'D' in good detail?

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

        For D, you do a binary search on the value of the median. The upper and lower bounds on the median value can be deduced from the minimum and maximum possible values of the medians without the constraint of the sum. Now we need to check whether the median m is achievable. For that we need to check if we can add some w_i's to the l_i's so that w_i + l_i <= r_i and the sum of the w_i's is not more than the total money — sum of l_i's, and the median is equal to m. So find those i's with l_i < m <= r_i, and also those j's with l_j >= m. We can find how many numbers we need to set equal to m using this, and the best way would be to choose the i's with the largest l_i's from the first set of i's we had. This is the essence behind the solution.

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

    C: Make a vector for even numbers and vector for odd numbers

    Now we can see that the number who will print first is the first number of odd numbers or the first number of even numbers

    And same for the second number.

    Be careful when you use all of odd numbers or all of evens numbers

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

My solution for B that passed the pretests-

Count the number of 1's in all the strings ( let's call it c1) Count the number of 0's in all the strings ( let's call it c2) If c1 and c2 are both odd and there is no string given of odd length — answer is n-1 else answer is n.

Is this correct and if yes can someone please explain why?

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

    For B, for the n-1 strings, we can do this - For each of the first n-1 strings, traverse towards the middle and check if it is a palindrome. If there is a change, just swap with the first element of the nth string. This gives you n-1. Now the answer can only be n or n-1. If there is any odd length string, you can do the operation mentioned above keeping that string as the last string and doing stuff to the middle element (instead of the first element). If there is no odd length string, you can get away with parity arguments and show that the answer is n-1.

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

      Why is that strategy always optimal though?

      Can't there possibly be some setup where there is no odd string and picking greedily from the last is sub-optimal?

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

        From the strategy given, the answer is either n-1 or n, as in the earlier post. My solution was to check if the last one had an even number of 1s or not. Let us suppose that the last string has an even number of ones. Construct the string from the ends and towards the middle. Let r be the reference to the first element of the first string. If you find a difference, at the left and the right indices, then one of them must be equal to the element at r, wlog, let it be 0. Now since there is an even number of ones in the last string, between the indices left and right (both exclusive) there must be an odd number of both 1s and 0s. So we can swap the element (element at right or left) that was not equal to the element at r with the element at r, and then swap the digit (which was originally at r) found between the indices left and right with the element currently at r. This whole operation keeps the element at r fixed, and also preserves the fact that the substring from 0 to left is the same as the reverse of that from right to size-1. We can keep doing this till left and right are separated by at least 2 elements. If the number of 1s is even, we would end up with 00 or 11 in the end, and this would provide a construction for n. Now suppose that the number of 1s is odd, and there exists a construction where all n strings are palindromes. In that case, every string would have an even number of 1s and even number of 0s because every string is of even length. But this is a contradiction, and hence we are done. The answer is thus < n, and therefore must be n-1.

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

At a certain time during the contest, there are more people who have solved E2 than that of E1, that's interesting.

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

    It's because of people with rating more than 2100. They don't need to care about rating as the round is unrated for them. So maybe some of them didn't bother to submit their solution of E2 at E1.

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

    In the last contest I was using an already deleted pointer, and this solution passed E2, but gave RE on E1. I was going nuts before I found that mistake.

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

How to solve problem B?

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

    Pure bruteforce works lmao https://mirror.codeforces.com/contest/1251/submission/63319464

    Notice that to construct a palindrome you need two of the same character so each time subtract two. I am pretty sure the answer is either n or (n — 1) but I was too lazy to think.

    Oh and also length 5 palindrome = length 4 palindrome + any character so just let it as length 4 :) (ABCBA) <-> (ABBA) + (C)

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

    if there is an string with odd length then all of the strings can become palindrome.(ans =n) else (all lengths are even) you count number of 0's if its odd you can fix at most n-1 strings else (its even) you can fix all of them and answer is n

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

      Why if there is an string with odd length all of the strings can become palindrome?

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

        Because the middle digit in the odd palindrome becomes kind of an option so you can use it to help other strings become palindrome.

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

          I got this, but the second case when number of zeros are odd, why we can fix at most n-1?

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

            when you have odd number of zeros there will always be a string with odd number of zero and odd one (since all string are even o+o=e).. This string cant be a palindrome, hence n-1.

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

solutions for A,B and C

hint for A
hint for C
hint for B
»
5 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

I can't write binary search in a proper manner. $$$Binary\, search$$$ gods, take me.

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

    I can't either, it never converges >:(

    Workaround: make break condition (r — l > 3) and check each value from [l, r] after that instead. Always works :) :) :)

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

      I ended up doing this sh*t too:

      int can[7] = {mid-3,mid-2, mid-1, mid ,mid+1, mid+2, mid+3};
      
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    If you are looking for a maximum $$$x$$$ that satisfies certain condition ($$$func(x) = true$$$), always keep the range such that $$$func(left) = true$$$, and $$$func(right) = false$$$. It is then quite easy to update:

    while (right - left > 1) {
          int middle = (left + right) / 2;
          if (func(middle)) {
            left = middle;
          } else {
            right = middle;
          }
        }
    
    answer = left;
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can u tell the condition for finding minimum value... Thanks..

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

        func(i) = arr[i] < arr[i + 1]

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

        Just reverse the condition for left and right;

        Always keep the range such that $$$func(left) = false$$$, and $$$func(right) = true$$$

        while (right - left > 1) {
              int middle = (left + right) / 2;
              if (func(middle)) {
                right = middle;
              } else {
                left= middle;
              }
            }
        

        answer = right

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

    check out the topcoder tutorial

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

E is duplicate of a canadian problem: https://dmoj.ca/problem/cco17p5

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

Can any one help me to find the test case where Exactly my code is failing?

Problem A : https://mirror.codeforces.com/contest/1251/submission/63335924

UPDATE:Found The test case :aaakka ->Ans : a

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

Why are contestants allowed to hack their own submissions? Shouldn't this be disallowed? You should be able to hack anybody else's test case but not your own.

»
5 years ago, # |
Rev. 3   Vote: I like it -53 Vote: I do not like it
Can someone hack it. It's solution for B.
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Been scratching my head for over an hour, trying to find out a mistake in my D solution. The idea of my solution is the same as discussed by many in the comments. Got WA on test case 2.

Can someone please help me find it?

My submission: 63336144

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

    I did the same thing and got WA :(

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

    mid_sum += (mid_ls.size() - (n / 2) + lc)

    Maybe cast mid_ls.size() to int? Maybe an overflow happens, because size() is unsigned.

    It probably isn't this, but maaaybe?

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

      I'm surprised, it worked! Thanks!

      Earlier I had the practice of typecasting size_t every time I used it, but then sometimes I used to think that anyways, it's going to typecast by itself, then why bother! Well, I guess I know now why to bother!

      Thanks again!

      AC submission: 63345119

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

This guy https://mirror.codeforces.com/submissions/amr_abdelazim is hacking his solutions of his own fake account https://mirror.codeforces.com/profile/Amr_Abdelazim01 . He tried very hard to hide the coding style of both account but it is revealed to be same in these 2 solutions https://mirror.codeforces.com/contest/479/submission/59876211

https://mirror.codeforces.com/contest/474/submission/63271187 Kindly look into the matter cheaters like these are ruining the platform.

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

In problem D i did not find the function to be monotonic as for many cases I found the function to be discrete.Can anyone help me how there is solution by binary search for such a case.

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

    Start with the lowest possible answer. That will be the case, when all the employees get their lowest possible salary, and the median salary will be the median of the list of l of all employees.

    Now try to increase the answer by 1. For the sake of simplicity, imagine that currently, all the employees have distinct salaries.

    CASE 1: Now if the r of employee having salary = median salary is greater than median salary, then you can directly increase that employee's salary by one, and your overall median salary will increase by one.

    CASE 2: Otherwise, let's suppose that the r of the employee having his salary = median salary is itself equal to median salary. In this case, we will try to find an employee whose current salary is less than median salary, but whose r is greater than median salary, then increase that employee's salary to median + 1, so that the overall median salary will increase by one.

    If neither of the above case is possible, then it is just not possible to increase the median salary anymore.

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

    Suppose that the maximum median is $$$m$$$, and you sorted employees in ascending order of their given salaries, where the $$$\lceil\dfrac{n}{2}\rceil^{th}$$$ employee is given salary $$$m$$$. To show that you can achieve all the medians down to the lowest one, you will always need to decrease one or more of the salaries of the first $$$\lceil\dfrac{n}{2}\rceil$$$ employees so that their maximum becomes $$$=$$$ the new median. If a new median $$$m_2$$$ can't be obtained because $$$l>m_2$$$ for some employee, you can swap him with an employee among the last $$$\lfloor\dfrac{n}{2}\rfloor$$$ employees whose $$$l\leq m_2$$$ (and his $$$r$$$ is obviously $$$\geq m_2$$$ because it is $$$\geq m$$$). If no such employee exists, then there are at least $$$\lceil\dfrac{n}{2}\rceil$$$ employees with $$$l>m_2$$$, and the median can't be decreased more.

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

https://mirror.codeforces.com/contest/1251/submission/63338046 https://mirror.codeforces.com/contest/1251/submission/63344390

These are two of my submissions for problem D. The 1st one gave run-time error on test-2 and the 2nd one got accepted. The only difference between these 2 submissions was in cmp() function. (I used > in 2nd one whereas >= in the 1st one)

Can anyone please help me figure out why did 1st one give run-time error whereas the 2nd one got accepted?

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

Help! What does "Unexpected verdict" mean in the verdict of hacks? This verdict comes out at hack #594802.

Does that mean I have hacked the std solution or the validator?

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

    It is fixed now.

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

      Thanks! Now up to 16 solutions of F were hacked by me. It's amazing that there are no such tests prepared by the authors.

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

This guy is just unbelievable see this hacked solution https://mirror.codeforces.com/contest/1251/submission/63344943

He deliberately put the if condition to print 1 so that he can hack his own fake account solution . and see this https://mirror.codeforces.com/submissions/Amr_Abdelazim01

He hacked his fake account solution almost 12 times with different if conditions to print 1. Strict action needs to be taken against users like this https://mirror.codeforces.com/profile/amr_abdelazim

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

These are all the fake accounts that I have discovered so far whom the owner have hacked by putting a if condition to print something nonsense when the input is something specific like if(string=="dfsfdfh45") print("456");

https://mirror.codeforces.com/contest/1251/submission/63335128

https://mirror.codeforces.com/contest/1251/submission/63316807

https://mirror.codeforces.com/contest/1251/submission/63342216

https://mirror.codeforces.com/contest/1251/submission/63341635

https://mirror.codeforces.com/contest/1251/submission/63344050

God people will do anything for the rating . People like these should be banned.

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

    They punished themselves by spending time on the most useless effort in the world, because hacking does not even influence rating in Educational rounds.

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

      Oh I didn't know that seems like they are also unaware about it . But this tactic is brought to light now who knows for how long people having been using tactic to gain rating through hacking in other rounds.

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

.

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

    Is it wrong? Why so many negative votes. Please correct me atleast

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

      Let the number of strings with odd number of ones and odd number of zeros be $$$a$$$, and the number of strings with odd length be $$$b$$$. Answer is $$$n$$$ if $$$b \geq a\ \%\ 2$$$, else $$$n-1$$$.

      Reason: Only strings with an odd number of both bits can't be made into palindromes by themselves, but two such strings can swap bits to make each other palindromic. That leaves at most one string if we have an odd number of such strings. This string can only swap bits with strings of odd length, which will make the number of both bits even, and hence make the string potentially palindromic. So at most one string can be left potentially non-palindromic if we do not have strings of odd length.

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

      It is not wrong. Maybe it's too lengthy to read. Also, when a negative vote comes, lot of people just pounce on downvoting. Like when there is one piece of garbage on road, everyone starts throwing the garbage at that place, thinking thats the designated place.

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

        This is sad, as it was the first solution that I've ever written here on Codeforces. I thought that I should explain it in complete detail.

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

in problem D why almost all solution use the same formulae in binary search that is mid=(l+r+1)/2 and the low=mid and high=mid-1?? My question is why not they use mid=(l+r)/2 and then low=mid+1 and high=mid-1 based on the condition.. But second give wrong answer..Why?? Pls help Thanks in advance

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

    low = mid + 1, high = mid — 1 works

    first thing you need to take while(low <= high) because you are changing low = mid + 1 and you need to check case when they equal

    and second thing is answer would be low — 1, why, because you are every time taking low + 1 when it works then, low would be final answer + 1, then result is low — 1

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

    I prefer 2nd Style :v

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve E1 with DP?

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

Can someone explain the solution for problem C in easier manner.. Thanks in advance...

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

    the order of appearance of even\odd numbers in the sequence will never change because you cannot swap two even\odd numbers so it remains the same. so the easiest way is to make two sequence of even and odd number and every time display the smaller

    Example:-
    
    input : 2531764
    the even sequence : 264
    the odd sequence : 5317
    
    step #1 : we choose the smaller 2 or 5 its 2 "2"
    step #1 : 6 or 5 its 5 "25"
    step #2 : 6 or 3 its 3 "253"
    step #3 : 6 or 1 its 1 "2531"
    step #4 : 6 or 7 its 6 "25316"
    step #5 : 4 or 7 its 4 "253164"
    step #6 : only 7 remains so the answer will be "2531647"
    
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the binary search for D with an example, it will be really helpful. Thanks in advance!

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -21 Vote: I do not like it
    you have to binary search on the median, the range of median is from 1 to 1e9 you will binary search on that, each iteration in the BS you pick the middle and check if it can be the median or not, in-case of yes make the start = middle+1 in-case of no make the end = middle-1 
    

    link to Ac code

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

Ok. Looking through the hacks of the round, I've noticed that there are some users who are hacking submissions made by accounts that are clearly their own alt accounts.

Though this isn't a huge deal in Educational Rounds, where hacking is mostly irrelevant, but I think it amounts to cheating in regular rounds, where you get 100 points for a successful hack. Imagine creating 10 accounts, who all submit 5 hackable solutions, and then your main account hacks them all to gain points.

What do you guys think?

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

    It isn't possible to hack just anyone's solution — they must also be in the same room as you. Getting 10 alts in the same room as you claim has extremely low probability. Anyway, would be better if you could post examples.

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

      That is seriously a stupid way to increase the rating. I would rather spend time improving myself rather than spend time getting my alt accounts in the same room :p

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

please publish the editorial

»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

editorial pls

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

Please publish editorial

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

Can anybody please explain to me why this code is giving TLE. (Question C) Link: https://mirror.codeforces.com/contest/1251/submission/63324481

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

    Use ans += odd[b] instead of ans = ans + odd[b]. For strings always use += to append.

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

      Thank You. Can you please explain the reason behind this?

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

        Suppose we have two strings, s and t of and we want to append t to the end of the s. If you write s = s + t what it does is that it creates a new string (that is invisible to you which means you don't have access to it by a variable name but it exists) which holds the resulting concatenated string. To create that invisible string it will copy s and t which basically means it iterates over both of them once which again means the time complexity would be $$$O(|s| + |t|)$$$. On the other hand when you use += it does not need to iterate over s, it just allocates enough amount of memory to append t which is like iterating over t once, with time complexity of $$$O(|t|)$$$. Your TLE solution was $$$O(n^2)$$$ because of the reason that you were basically iterating over ans while appending to it.

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

          Thank You so much.

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Will there be an editorial published?

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

Thanks for fast editorial.

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

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Can someone please help me finding bug in my solution for the problem E2. It's giving WA on test case 3, the test case is really large so I'm not able to find out which input is giving WA.

UPD: Debugged it now

Link to my code

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

    Can u explain your idea? pls, thanks in advance.

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

      We will approach the problem in a greedy fashion.

      • First of all sort the pair vector(input) in increasing order of the number of votes required.

      • Now make a multiset (it's similar to set but it can store multiple elements which are same) which is initially empty.

      • Traverse from the bottom, and one by one push the current element into the multiset. Note that, say if you are at an index $$$i$$$, and the candidate requires minimum votes, $$$M_i$$$ and the cost of buying it is $$$P_i$$$. And you have currently bought a total of $$$v_1$$$ voters.

      • To be sure that by the end of the traversal the current guy will vote us, we need to check if $$$(i — 1 + v_1) >= M_i$$$. If the condition is not satisfied, buy the vote of the guy in the starting of the set (cheapest till now), add his cost to your answer and erase this guy from the multiset.

      • Iterate backwards.

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

balanced problems, thank you.

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

Please link the editorial directly to the contest dashboard.

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

Problem D has a greedy tag on it. Can anyone please provide a greedy solution?

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

http://mirror.codeforces.com/contest/1251/submission/63422680 can some one tell why this code is giving me tle to problem 3 thanks in advance