Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 12 дней назад, По-английски,

Hello!

This time decided to fill myself in the shoes of the problem writers. It is very exciting! My challenge was to prepare a round in one day. It's really incredible pleasure to surrender to my passion and all day just work on problems!

Despite the fact that in total I've wrote 8 problems, I made it in time. Initially, I prepared 7 problems, but two of them were found to be used before (thank you, 300iq and _kun_ for poining it) and I removed them and wrote a new problem.

Codeforces Round #496 (Div. 3) will start on Jul/09/2018 18:35 (Moscow time). You will be offered 6 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the Div. 1 not be at all interested by this problems. And for 1600-1899 the problems will be quite easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Many thanks to the testers: kevinsogo, 300iq, _kun_, arsijo and adedalic. You really helped to make this round!

Good luck!

UPD 1: The round is over. Thank you for participation!

Official Top-5 (trusted only)

Unofficial Top-5 (+ untrusted)

UPD 2: The editorial is available by the link.

 
 
 
 
  • Проголосовать: нравится  
  • +263
  • Проголосовать: не нравится  

»
12 дней назад, # |
  Проголосовать: нравится +87 Проголосовать: не нравится

You forgot to thank MikeMirzayanov XD

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +235 Проголосовать: не нравится

    I've told him it personally.

    • »
      »
      »
      12 дней назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      is that rated for me?

      • »
        »
        »
        »
        12 дней назад, # ^ |
          Проголосовать: нравится +35 Проголосовать: не нравится

        Common, did you read the text?

        Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

        • »
          »
          »
          »
          »
          12 дней назад, # ^ |
            Проголосовать: нравится +97 Проголосовать: не нравится

          Starting rating is not shown, so it is not so obvious if their rating is less than 1600

        • »
          »
          »
          »
          »
          12 дней назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          So, is the point of trusted participants just that those who aren't such participants will not appear in the Top X table, or they will not affect our ratings also?

          Because if the round will be rated for them, we must affect each other's ratings, mustn't we?

          • »
            »
            »
            »
            »
            »
            12 дней назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            AFAIK, there are two separate rankings, one is for trusted participants and it is the official one, while the other is for the distrusted participants. The lists do not affect nor influence each other in any way. The idea is, if you are a smurf, you'll compete with other smurfs, and people who actually ARE Div3 level will compete against one another. You won't see distrusted participants in the official standings.

            • »
              »
              »
              »
              »
              »
              »
              12 дней назад, # ^ |
              Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

              Thanks for your reply.

              I don't think so, because if, for example, two distrusted participants participated in some contest, according to what you said, the one with higher rank than the other will have a positive change on his rating, and the other one will have the same change but negatively (because, AFAIK, the total sum of the rating changes in a round equals 0), but this didn't happen before.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 дней назад, # ^ |
                  Проголосовать: нравится +1 Проголосовать: не нравится

                You're right, but I think that this (one gets some points, the other loses) will actually discourage people who have smurf accounts because they won't achieve much by competing in such circumstances (they all solve everything, meaning some may even lose rating points as unrated and get < 1500), while the point of them competing in a div3 round is to "dominate" it.

                There are some new unrated accounts that solve all tasks in a div3 round, only they won't get the expected rating change (~+200) but something relative to other unrated folks who are clearly smurf accounts, and that effectively defeats the purpose of anyone having a smurf account (or that how it is supposed to work, anyway, I don't know if it's actually working :), but I guess it is ).

        • »
          »
          »
          »
          »
          12 дней назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

          Why untrustworthy participants appear in top5?

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится -30 Проголосовать: не нравится

    haha, MikeMirzayanov is himself.

»
12 дней назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

MikeMirzayanov a couple div3 contests back there was talk of the reduction in the penalty for wrong answers (20 is too much), any updates on that ?

»
12 дней назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

How can one prepare 7 problems in ONE DAY? Amazing!!! THANKS

»
12 дней назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

I am a simple man I see MikeMirzayanov I "upvote".

»
12 дней назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Hopefully MikeMirzayanov had enough time to make some not so weak pretests.No one would like to see many solutions fail after systests & I wish Vovuh will be back in the next Div-3 round.

»
12 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

This is insane. Thank you so much for putting in effort to make this an awesome site!

»
12 дней назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

6th Div-3 Contest in the history of Codeforces Round. <3

»
12 дней назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

when i will be Expert..

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thanks a lot for making another div3 contest. It would be better if provided with 7 problems. Hopefully, problem statement will be the short description. Best of luck.

»
12 дней назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

MikeMirzayanov Will you make some tutorial on How to become a good problem setter...

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

MikeMirzayanov Any updates about lowering down the 20min penalty time for the 2h/2h30 contests? (For Div3 and Edu)

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So many "MikeMirzayanov"s in this blog. Is it his birthday?

»
12 дней назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

MikeMirzayanov why don't you ever participate in any contest on codeforces, it would be fun to see the CF founder competing with others.

»
12 дней назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Please correct me if I'm wrong, but I remember that edu rounds allow registration at any moment before the end of the contest. Why is it that this contest registration is the same as normal rounds (with extra registration) if its rule is the same as edu rounds?

Edit: my mistake, registration closes for 10 minutes before and after start of contest only

»
12 дней назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Some of the last codeforces contest were so much unbalanced. The questions in this contest were so nicely balanced. Enjoyed it. Looking forward to such more contests.

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was pretest 9 in D?

»
12 дней назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Loved this round. <3

»
12 дней назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

How to solve E2?

  • »
    »
    12 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

    Let s1[l..r] be (number of elements > m) — (number of elements < m) and s2[l..r] be the number of occurences of m.

    You can prove that in order for a range to be valid, 1-s2[l..r]<=s1[l..r]<=s2[l..r].

    If you expand s1/2[l..r] into s1/2[0..r]-s1/2[0..l-1], the problem becomes 2D range sum queries with point updates.

  • »
    »
    12 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится +40 Проголосовать: не нравится

    I solved it by counting number of arrays having median>=m and subtracting from those, the count of arrays having median>=m+1.

    To count number of arrays having median>=X, we can replace all elements < X by -1 and >=X by +1 and count the number of subarrays having a non-negative sum (and taking special case of when the length of the array is even, in that case the sum must be positive), both of which are kind of standard problems.

    • »
      »
      »
      12 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

      Lol, why am I so dumb? I was thinking of 2d segment tree :D

    • »
      »
      »
      12 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      non-negative sum? what does that mean? how sum can be negative?

    • »
      »
      »
      11 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      For E1 after changing m to 0 and numbers less than m to -1 and greater than m to +1 one can iterate though the prefix sum and count answer with the help of a map like here Can a similar approach be used for E2 by accounting for the number of zeros also ? I was not able to think of any O(n)or O(nlgn) solution like iterating and using map in E1. Any help?

    • »
      »
      »
      9 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How to find the no of subarrays with positive sum efficiently?

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    I counted the number of subarrays that don't have the median equal to m, and subtracted that from n*(n+1)/2. There are two cases:

    1) L + ZEROS < R

    2) L >= R + ZEROS

    L: left part (< m), R: right part (>m), ZEROS = number of elements equal to m.

    In the first case, I change the values <= m to -1, others to +1 and find subarrays with strictly positive sum.

    In the second case, I change values < m to +1, others to -1, and find the subarrays with non-negative sum.

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

So, what was that test 11 in D?

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Whatever it was. But I must say it was disastrous.

  • »
    »
    12 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    let's say a are numbers such that a%3==1 and b are numbers such that b%3==2

    if count(a)==3 and count(b)==0 or count(b)==3 and count(a)==0 you have to split.

    { Edit : the complete approach is mentioned below }

    • »
      »
      »
      12 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What do you have to split?

      • »
        »
        »
        »
        12 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        observation 1 : you have to make splits in the array (vertical splits) if the element is 0 or a multiple of 3 . the number of these elements are added to the ans.

        removing these elements creates some segments . within a segment you can encounter elements of two kinds . element type a (a%3=1) and element type b(b%3=2).

        while processing the segment let count of elements type a be |a| and similarly |b| :

        if min( |a|,|b|) == 1 , then we are sure to have encountered a subset of this segment whose sum is multiple of 3. we reset the counts here and continue looking for other such sub-segments.

        if the above doesn't hold either |a|=0 or |b|=0 ,in which case |b| should be a multiple of 3 to yield 3 sum sub-segment and similarly for |a|. if that happens we reset counts and continue.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Try 112, the answer is 1

»
12 дней назад, # |
  Проголосовать: нравится +156 Проголосовать: не нравится

The worst future you can imagine:

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Why I got TLE on E1 test 27 ?

»
12 дней назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

How to solve E2? I thought of an approach to make every number unique by giving them id in increasing order.Now suppose m appears k times in array then all m will have values from some f + 1 to f + k where f is the number of elements less than m. Now solve as the previous problem where median should lie between f + 1 to f + k;

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D? I wrote a DP solution but got WA at test 11 multiple times.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It must be greedy then? I got to the same test using greedy approach.

  • »
    »
    12 дней назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Let dp[i]=answer for prefix of size i. We can see that dp is non-decreasing. And let sum[i] be the sum of prefix modulo 3, and x[i] be the last j then sum[j]=i. Then dp[i]=max(dp[i-1], 1 + dp[x[sum[i]]], sum[i] == 0)

  • »
    »
    12 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I solved D on the fact that given a 3 digit number in which no digit is divisible by 3, there is at exactly 1 segment whose sum is divisible by 3.

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Okay! DP was more intuitive to me as this problem was similar to a classic DP problem of recursive partitioning.

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody please post and explain his/her Solution for D, if it is based on BINARY SEARCH.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    D is just greedy

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    In D you can observe, that every (at least) 3-elements-long subsequence will have correct combination. I swapped all the numbers a for numbers a%3 and then started greedy algorithm. For every i have sum of elements (i), (i + i-1), (i + i-1 + i-2), but first I check, whether any of those numbers was taken previously. For example I store a sum from range (i) (just a single element) and then check if element indexed (i-1) was taken. If it was I don't check further, if it wasn't I can add that in my sum. If my sum%3 == 0, then I mark element i as taken and add +1 to the answer.

    If I checked only one number, correct answer would only occur if it was == 0(mod 3). If I checked only two numbers, then I would have those combinations of modulo: (0, 0), (1, 0), (0, 1), (1, 1), (1, 2), (2, 1), (2, 2). As you can see only three of these are correct. If I checked three numbers then there would always occur at least one correct subsequence.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I solved D by dp

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone can tell what's wrong with my solution in problem C, I got WA test 12. http://codeforces.com/contest/1005/submission/40145706

»
12 дней назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Good Contest.

Can someone share the idea of E2? My Code work when median value exist only once in the array.

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

test case 11 of problem D was nightmare for many contestant including me. :p

»
12 дней назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

The most interesting div.3 round, with the last 2 problems pretty tough in my opinion.

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How did more people solve C than D? D is just classic greedy but I don't even have an idea about C...

  • »
    »
    12 дней назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    If you are currently considering a particular number in the array, there are only log(n) other numbers which, if added to the number being considered, give a power of 2. So we can use hash maps to store numbers and so complexity is O(n*log(2*1e9))

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't solve D because I wrote if (!(digit + temp.front()) % 3), notif (!((digit + temp.front()) % 3)) or simple if ((digit + temp.front()) % 3 == 0). And... I don't find the mistake.

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain greedy approach for D?

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    hint: if x, y, z are integers, then at least one of x, y, z, x + y, y + z, and x + y + z is divisible by 3

    • »
      »
      »
      12 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Couldn't point out this fact during contest , instead I kept on storing them :(

    • »
      »
      »
      11 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      can u provide a proof for the above statement or an idea to get to above conclusion @keima915

      • »
        »
        »
        »
        11 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You may use examples to get the feel of it ! eg : 714|3|0|888|222|57

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Very straight away approach : Iterate over the array , if s[i] is divisible by 3 , increment counter and make num =0 , else store it in num . Each time check if num is divisible by 3 , and if its length crosses "3" , it** must** have already been divisible by 3 => Clear num and increase counter.

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm wondering what would happen if MikeMirzayanov prepared this contest in more than one day.

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Whats making it TLE Im still wondering ?? problem — B

check

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    	while(slen>0 && s.equals(t)!=true)
    		{
    		    count+=2;
    		    s=s.substring(1);
    		    t=t.substring(1);
    		    slen-=1;
    		}
    

    You create new string every time. It is rather suboptimal.

    • »
      »
      »
      12 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But everytime im creating with first character removed from string.

      • »
        »
        »
        »
        12 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Everytime the whole new string is created, not only the first char is removed

        • »
          »
          »
          »
          »
          12 дней назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Can u suggest me alternative for that part of while loop. Thanks

          • »
            »
            »
            »
            »
            »
            12 дней назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            int i=slen-1; while(i>=0&&s.charAt(i)==t.charAt(i)) { --i; count+=2; }
            • »
              »
              »
              »
              »
              »
              »
              12 дней назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              giving WA bro

              • »
                »
                »
                »
                »
                »
                »
                »
                12 дней назад, # ^ |
                Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

                Checking if strings are equal take too much time — solution has square complexity. . WA — because you need to find the first index from the end of both strings, where s[s.length() — index] != t[t.length() — index]. . codeforces and yes — you are looking for s[9] and t[2], then s[8] and t[1] and s[7] and t[0].

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 дней назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Im using substring method of java. Is that making it TLE?? What is time complexity for substring ()?? — is it O(n) or O(1)?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 дней назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  I don't know Java, but I heard that it is O(n) in new versions and nearly O(1) in old versions, maybe I'm wrong. Also I'm not sure about the complexity of method equals — it's more probably that O(n).

»
12 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
»
12 дней назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I thought you said 6 problems "You will be given 6 problems and 2 hours to solve them.".But anyways I enjoyed the round thanks.

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do we solve C? Do we optimise the brute force method or use some other approach entirely?

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Enumerate each number, enumerate the power of 2, and subtract the number by 2 power, to see if the result is in the original set.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    From constraint I think brute force should work. Because for each iteration we r finding for two elements at a time.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There a only 31 powers of two which are less than 2e9, so you can brute-forces over those powers.

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I did a different approach in D, I first removed all 1 digit no.s and stored the rest no. as various segment, and then iterated over the segments for 2 digits and so on. I am not getting TLE, I and I can prove why my algorithm can pass TLE, but instead a wrong ans on TC 11. Code link: http://codeforces.com/contest/1005/submission/40144526 Thanks :)

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Всем привет. Я возможно придумал О(n) решение на Е2, но к сожалению возможности проверить его у меня нет, так что хочу сейчас его рассказать, а вас прошу проверить его. Если есть ошибки и замечания — пишите ниже, неплохо если еще и с тестами. Теперь к сути: Рассмотрим случай с нечетной длиной подотрезка. Очевидно, что число явл медианой, если колво строго больших и строго меньших равны. Число равных в таком случае будет нечетным и наше число можно поставить в серединку. Будем перебирать правую границу интересных подотрезков и походу считать на префиксе пару (колво больших; колво меньших). Теперь при текущей правой границе и префиксной парой посчитаем колво подходящих левых. Очевидно, что подходят такие пары, что разница между ее колвами равна разнице между колвами текущей пары (тогда колва подотрезка с данными границами будут равны, что нам и надо). В итоге получается что можно вместо пары на префиксе хранить разницу между колвом больше m и колвом меньше m. Ограничения позволяют использовать массив вместо мапа. Не забудем так же про префикс нулевой длины (разница 0). Однако стоит напомнить что это только при нечетной длине подотрезка, поэтому храним два разных массива на каждую четность индексов и используем какой нужно на каждом шаге. Теперь рассмотрим для подотрезков четной длины. Решение на самом деле остается таким же (помимо других нужных четностей), но с рассмотрением еще одного случая, а именно: колво меньших должно быть на 1 меньше, чем колво больших. Довольно понятно, почему и как надо рассматривать такой случай (считаем колво разниц на префиксе отличающихся на 1 от текущей. +1 или -1 зависит от реализации). Почему же все равно надо считать колво позиций на префиксе с такой же разницей? Потому что в таком случае колво равных m будет четно и мы можем поставить число на левую середину, чтобы данный отрезок подошел. Вот собственно мое решение, прошу оценить. Если есть вопросы, то задавайте.

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Привет. Ты возможно придумал O(n) решение на E1

»
12 дней назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

An awesome round!

»
12 дней назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve E1?

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Note that, in any sequence of numbers that satisfy the condition, m should be included. Also, in total we only care that the number of numbers greater than m minus the number of numbers less than m is 0 or 1. Now, just find for each indez the greater-lesser factor, separately, for indices before the value m and after the value m. Now, just compute using the condition

»
12 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

There is other input similar to test case 11 in problem D? Just to check why I'm getting WA.

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E2?

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Got Wrong Answer on Test 11. What wrong am I doing here ? My Submission: 40139802

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

mike's contributor is oo

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone give a Dp solution of problem D and why we are using only 3 values i didn't undertand any solution.

»
11 дней назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have some questions regarding Problem C:

  1. Consider these 2 solutions: *Sol1 *Sol2

In Sol1 on line 36, I have used mp[y]>0 check to see whether y exists in the map mp or not, here y can be negative as well but I have not checked that. This solution results in Memory Limit Exceeded error on 7 test case. However, if I use mp.find(y)!=mp.end() to check whether y is in the map of not, it passes.

Can someone please point out why is this happening?

  1. If we use unordered_map then the approach in Sol1 will give an infinite loop. Why is this happening?

Thanks a lot in advance.

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Mp[y] will insert y in map with default value 0.While Mp.find(x) return iterator to the key x without inserting it. Try this

    for(i = 0;i <  = 10000000: i +  + ){if(Mp[i] =  = 0){};}

    And check the memory used.

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But even after the insertion of elements, only 120000*32 elements will be stored in the map, so why does it give memory limit error? As long long is 64 bit, it will be 29 MB roughly in the worst case. Please correct me if I am wrong.

      • »
        »
        »
        »
        11 дней назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        you are iterating on the map and simultaneously inserting an element in it. This will cause the invalidation of references. Read this

        Here, I have submitted your code just by storing the array in the different map and iterating over it.

        I have made the same mistake once in a div2 contest. And, BTW your calculation is wrong it is more than 150MB(See This).

        • »
          »
          »
          »
          »
          10 дней назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Oh, I understand it now!

          But can you please tell me where I went wrong with the calculations?

          Thanks a lot for your generous help.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Its v.nice

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I am getting runtime error with "Exit code is -1073741819" message on solution for D.

here is my code : http://codeforces.com/contest/1005/submission/40144266

Can anyone point my mistake out??

  • »
    »
    11 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I don't think you can clear a set/list while iterating through it. So if you remove s.clear() from line 39 (from the first submission you linked) and only clear it if p is set to 1 after the loop, it should work without crashing.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My last submission to problem C in the round has passed test 7 and 11 and it was AC and after system testing it's now WA on test 7 ! And I also want to know that why unordered_map worked her and map was so slow I didn't face such issues in a CF problems before !

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My code of problem C got accepted on testcase 7 in contest time but gave TLE in system testing. Can anyone help. I total made 5 submission in which third one got accepted. In which 4 gave runtime error at testcase 7 while third submission got accepted. But in system testing got TLE. Please anyone explain.

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Can anybody help me out I can't understand why my same solution is both TLE and AC. AC:40160742 TLE : 40160895 It has cost me a problem in this contest which I was sure would pass the test cases.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please tell me what's the error in this approach from Problem D? Solution

»
11 дней назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

WoW! I get rank 2!

I pass E2 with Balanced_Tree in Segment_Tree. But in fact using fenwick tree can pass E1 and E2, in this way, the length of code can be reduced much.

»
11 дней назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Your crafting.oj.uz ratings are updated!

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my code coincided with one of the other coders and i dont know how it got copied . I generally code on ideone but i dont know much about its settings . would i be penalised for that ??

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

if x, y, z are integers, then at least one of x, y, z, x + y, y + z, and x + y + z is divisible by 3 ****__ can anybody provide a proof for the above statement or an idea to get to above conclusion

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There aren't so many cases: 1) one of the numbers x, y and z is divisible by 3. 2) all of them aren't divisible by 3 — the variants for the rests of division are: (x % 3 = 1, y % 3 = 2) or (x % 3 = 2, y % 3 = 1) — then (x + y) % 3 = 0.

    Other cases: 111, 112, 221, 222. that's all.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For E1 after changing m to 0 and numbers less than m to -1 and greater than m to +1 one can iterate though the prefix sum and count answer with the help of a map like here Can a similar approach be used for E2 by accounting for the number of zeros also ? I was not able to think of any O(n)or O(nlgn) solution like iterating and using map in E1. Any help?

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any help will be appreciated, WA in test 11 problem D Link.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't know how halyavin was successful in hacking so many of our solutions for problem C. Can someone explain me the Generator Algorithm he used? It would be great to understand what that algorithm did to exploit the weakness in so many solutions. Thanks!

His generator

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It creates O(n2) test for Arrays.sort in Java. Only sorting of primitive arrays can be exploited — sorting Integer[] or Object[] is fine. All the complications are needed so that generator doesn't require O(n2) time itself.

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please explain me of problem C. I also read editorial. But still i didnt get it that how can it do easily to using map. Thanks.

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For every element you need to find , whether there is another number which on summing gives a number of the form 2^d (i.e.,a number which is a power of 2 ) . So , first create an array which stores all the powers of 2 till 10^9 , then for every element , iterate over this array (powers of 2) and take the difference between both and check whether this difference exits in your original array excluding the current index (You can do this using a map/binary_search). If there is no such element increment your count value and finally print it !

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry, I'd like to ask you. How can I solve problem D in DP?

I can't understand why we solve this problem in DP.

»
9 дней назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

https://drive.google.com/file/d/1uBBOkG7DvJsU-W2NQV3q-TaurdH1XRGd/view?usp=sharing Is it a error? I test the program on my computer give a correct answer and the web give me a wrong answer.Can you test and check that ?

  • »
    »
    8 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In your solution the problem is with int t = log(i) / log(2). log() and power() works with double. Just remove this string and change to return i==pow(2,log(i) / log(2)). The type will be double and all will be OK.