MikeMirzayanov's blog

By MikeMirzayanov, 12 days ago, In English,

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.

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

»
12 days ago, # |
  Vote: I like it +87 Vote: I do not like it

You forgot to thank MikeMirzayanov XD

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +235 Vote: I do not like it

    I've told him it personally.

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

      is that rated for me?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        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 days ago, # ^ |
            Vote: I like it +97 Vote: I do not like it

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

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

          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 days ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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 days ago, # ^ |
              Rev. 2   Vote: I like it +1 Vote: I do not like it

              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 days ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                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 days ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          Why untrustworthy participants appear in top5?

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What do you mean?

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              They participated in less than 2 rated rounds, so they should not be in the official table. So why are they included in the winner list?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    haha, MikeMirzayanov is himself.

»
12 days ago, # |
  Vote: I like it +54 Vote: I do not like it

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 days ago, # |
  Vote: I like it +54 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +55 Vote: I do not like it

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

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

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

»
12 days ago, # |
  Vote: I like it +24 Vote: I do not like it

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 days ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it -9 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it -28 Vote: I do not like it

when i will be Expert..

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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 days ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +26 Vote: I do not like it

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 days ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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 days ago, # |
  Vote: I like it +37 Vote: I do not like it

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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What was pretest 9 in D?

»
12 days ago, # |
  Vote: I like it +29 Vote: I do not like it

Loved this round. <3

»
12 days ago, # |
  Vote: I like it +34 Vote: I do not like it

How to solve E2?

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    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 days ago, # ^ |
    Rev. 2   Vote: I like it +40 Vote: I do not like it

    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 days ago, # ^ |
      Rev. 2   Vote: I like it +12 Vote: I do not like it

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

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

        You're not dumb at all, I got AC with this approach for both E1 & E2

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry, there was a formatting mistake in my comment! I have corrected it

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

      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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

So, what was that test 11 in D?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you have to split?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try 112, the answer is 1

»
12 days ago, # |
  Vote: I like it +156 Vote: I do not like it

The worst future you can imagine:

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Why I got TLE on E1 test 27 ?

»
12 days ago, # |
  Vote: I like it +14 Vote: I do not like it

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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah it is greedy

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And whats the problem with test 11?

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what is your code doing exactly?

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I first make prefix sums of digits in array pf. prvi[i][j] stores the nearest position k to the right such that pf[k] % 3 = j. Then I greedily choose the nearest number to go to,while updating the solution.

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's a very long number

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Correct answers for 824 (1) and 824824 (2) let me pass test 11.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got the mistake in my implementation. dp always works!

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

    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 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      LINK. Can you tell what kind of case will this solution fail. I have used a recursive approach. EDIT: GOT AC!

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

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D is just greedy

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

    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 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I solved D by dp

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Good Contest.

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

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      let x, y, z be the three left-most integers first check x then check y and x + y last, check z, y + z, and x + y + z

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ??? I solve this problem after the competition by adding two brackets, as I said before.

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

      Because !(digit + temp.front()) % 3 equals (!(digit + temp.front())) % 3

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain greedy approach for D?

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

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

    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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

check

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    	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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But everytime im creating with first character removed from string.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

            int i=slen-1; while(i>=0&&s.charAt(i)==t.charAt(i)) { --i; count+=2; }
            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              giving WA bro

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

                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 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • »
    »
    11 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Do you even read that problem? They ask different thing to do. You waste my time.

»
12 days ago, # |
  Vote: I like it -8 Vote: I do not like it

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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same approach. Couldn't pass it

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what was your ans for TC11

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        At first I was getting TLE but my implementation was crazily bad. Then when I implemented properly I'm getting RTE on tc1.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I too did the same . But there is no need to store segments of size more than 3 , as explained in above comments . So , its just wastage of memory....

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

An awesome round!

»
12 days ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve E1?

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

    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 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E2?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A counter case: 382845 The answer should be 3 but it prints 2.

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

mike's contributor is oo

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Its v.nice

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

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 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have a sort of similar query too:

      Consider a map map<long long,long long>mp. and now you are iterating it and using it like below:

      for(auto x:mp){
        x.s=1;
      }
      

      This produces errors and undefined behaviors. Why? Thanks a lot in advance.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

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 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Your crafting.oj.uz ratings are updated!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 days ago, # |
  Vote: I like it -8 Vote: I do not like it

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 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.