Vovuh's blog

By Vovuh, history, 11 days ago, translation, In English,

This time I have nothing to say except that this round will consist of 7 different problems!

<almost-copy-pasted-part>

Hello! Codeforces Round #552 (Div. 3) will start at Apr/16/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too 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 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

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.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD: Thanks to le.mur for idea of one of the problems.

UPD2: Editorial is published now!

UPD3:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 ysluo2000 7 229
2 fake_delete_pls2 7 251
3 KefaKuma 6 178
4 Zhao-L 6 222
5 haimiaoyuzhao 6 240

Congratulations to the best hackers:

Rank Competitor Hack Count
1 wzw19991105 49:-4
2 ScreaMood 42:-1
3 I_love_Maria_Krylova 35:-5
4 Hacked_ 31:-1
5 Zombie358 30:-7
949 successful hacks and 502 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A MinatoYukina 0:01
B MinatoYukina 0:04
C Chess_fan 0:08
D nikizakr 0:07
E FluffyTT 0:21
F FluffyTT 0:09
G 1tst 0:14

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

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

Expecting this round to be full of awesome questions with strong pretests!!!

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

Every problem you create is nice! Thanks for your efforts, wish you luck, Vovuh

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

I can smell an easy and a hard version problem.

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

    it seems that each problem of div3 contest will be divided into two part: hard version and easy version LOL

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

i like div 3

»
10 days ago, # |
  Vote: I like it +18 Vote: I do not like it

I will do my best to try to became an expert in this round, I wish high rating to everybody!

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

    Sorry if I said something wrong, I didn't mean to to this...

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

      You said nothing wrong, dont have to sorry for it

»
10 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Hope this contest is balance one like last DIV3.

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

Hope to AK. Fighting

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

The problems of each Div3 rounds are awesome. I believe if one regularly upsolve(solve the problems that one can't solve during contest time) the problems, then (s)he must learn something new and improve gradually.

»
10 days ago, # |
Rev. 3   Vote: I like it +26 Vote: I do not like it

1tst solved 3 problems in 2 minutes !! how that possible ?

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

How to solve problem E?

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

    The way I did it was using:

    1. A segment tree with lazy updates to find the maximum
    2. The painter's problem using disjoint-set-union to travel the array even after the 'deletion' of foster elements

    It's a lot to know and implement. I'm assuming there's an easier solution because of that

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

      This is the precise definition of overkill.

      You can use set to find maximum element, and store nxt[i] and prev[i] -> index next and prev to i, which is not still in a team. So you will have to move O(k) itmes in each iteration and there will be atmost O(n/k) iterations as, each iteration removes atleast k elements.

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

        Exactly as that, decided to delete my comment because i didn't think i explained it properly.

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

        Thanks it Helped!!

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

      My approach: Keep a set with pair {position, value} and another set with pair {value, position}. So second set gets the first element and the other set gets the (currently) adjacent ones. (I use this idea a lot, although there may be easier methods). My submission here https://codeforces.com/contest/1154/submission/52846244

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

      I also tried to do this, I finished now, FINALLY!!!! The main code is here: https://codeforces.com/contest/1154/submission/52877899

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

    u can use two ordered sets, where each element is a pair, and in first ordered set store each (val[i], i) and in second ordered set store (i,val[i]). this made it quite easy.

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

    All I did was just kept track of the right and left index of any given index at any moment. And after each iteration, I updated them as necessary.

    You can view my code here: 52867981

    Just a normal implementation.

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

    doubly-linked list + max-heap

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

    I think the easiest way is using doubly-linked list + sorting the values. Using a set(as max heap) also seems easy to implement.

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

Is it possible to solve problem F without the constraint k is not exceeding 2000?

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

A: That minus just before a+b is not a minus, it is just a dash. Thank you, but that killed the fun for me.

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

    me, me too I pour my 1 hour on that problem

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

      B: Lowest positive Integer is not 1, it is 0. Haha, very funny. C: ans overflows if not defined long long. D: Look like dp, but is not. Really funny.

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

        B: Are you really serious? There is at least 4 places in the statement where is said NON-NEGATIVE value $$$D$$$.

        C: If your calculations are somewhat inaccurate why are you trying to blame us for it?

        D: If you think that the problem topic is DP it is not our fault too.

        And about A: there is a place in the output section where all four numbers are defined without any "dashes" or "minuses".

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

          i still think the dash is confusing and missleading which is exspecially bad for a problem A. (can this still be changed for users who solve this later?)

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

            Okay, I will change this dash to colon. But I still think that users should read statements more carefully.

            Just see the old problems on Codeforces, their statements are so short and many almost obvious things are just not described. But now we are going to explain almost every thing which may be ambiguous. I think that after several hundreds of rounds participants will ask what does "integer" mean or somewhat similar. And it is very upsetting.

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

              But I really enjoyed this contest. Thank you. And for problem A at some point I managed to find out that I was wrong and I got correct answer. I think reading carefully a problem is a part of a problem. I really enjoyed this contest. Than you. Sorry for my bad english

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

                I’m not trying to blame you. I just want to make excuse for my poor job :( I’m sorry I hurt you

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

              I respect that you have invested a lot of work, and thank you for it. Even though I did not like this one competition, it's still great to have people doing the job.

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

    me too

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

How to solve problem G?

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

    yeah..i'd like to know ,too...

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

    Just fix the gcd and find two smallest numbers with such gcd. I think that's very easy problem for G.

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

      I did the same, however i got tle. I tried to precalculate all divisors of numbers in range (1,1e7+5) using 2 nested loops, like this:

      Your code here...
      for(int i=1;i<nax;i++)
      {
          for(int j=i;j<nax;j+=i)
          {
              divisors[j].push_back(i);
          }
      }
      

      Do you know why this gives tle, when it should amortize to nax(log nax), where nax=1e7?

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

        Instead you can try saving indexes of each number and it will be faster due to constant.

        See this submission (even instead of calculating gcd dividing by i is enough and makes the solution slightly faster): https://codeforces.com/contest/1154/submission/52851693

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

        It should amortize to nax*log(nax)

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

          I know, but you can check this in custom invocation:

          #include <bits/stdc++.h>
          
          using namespace std;
          const int k=3e6;
          vector<int> dzielniki[k];
          
          int main()
          {
          int nax=3e6;
          for(int i=1;i<nax;i++)
          {
              for(int j=i;j<nax;j+=i)
                  {
                      dzielniki[j].push_back(i);
                  }
          }
          
          return 0;
          }
          

          For nax=3e6 it works >3000 ms. What is wrong when it should be only ~60kk operations?

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

          you save over 10^9 values in divisors...

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

            How did you came up with such estimation?

            • »
              »
              »
              »
              »
              »
              »
              10 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
                  ll res = 0;
                  for (ll i = 1; i < lim; i++) {
                      res += lim / i;
                  }
                  cout << res << endl;
              
              • »
                »
                »
                »
                »
                »
                »
                »
                10 days ago, # ^ |
                  Vote: I like it -8 Vote: I do not like it

                For lim=1e7 it gives ~162 * 10^6.

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

                  whoops i meant 10^8... the problem is the random memory access and vector resizes.

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

                  Is there any smart way to optimize it?

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

                  not like this. I dont believe you can actually save all divisors off all numbers less than 10^7. What i did was to save for each value a prime divisor(with sieving) then if i need to find all divisors of a number i can factor it recursively and generate all divisors in $$$O(divisors)$$$

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days ago, # ^ |
                  Rev. 3   Vote: I like it -8 Vote: I do not like it

                  Thought about this solution as well. So you think that it should be faster? I think you are right actually. I did not suspect vectors to be this slow.

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

                  it is quite much faster... The problem is not the vector. Enumerating all divisors off all numbers less than $$$10^7$$$ still takes 10s. But you don't need all divisors off all numbers.

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

                  Ok, thanks. But why do you say that it is not vectors fault when we only do ~ 150 KK operations. It should take ~ 1 sec. And pushing back is the only operation we use?

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

                  memory allocation is the problem... if you use more memory allocating even more takes even longer... in fact savin all those values would take $640$mb of ram wich would even give you memory limit...

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

                  Ok thanks for explaination.

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

      I just found one accepted G in PyPy 2. Is it possible for this question to AC with Python 3 solution? I mean, it's terrifying to find every possible gcd within the time limit. Is it necessarily O(N^2)?

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

        finding every possible gcd of all pairs is bounded by $$$O(n\sqrt{n})$$$ (in fact its even fasert since the divisor function grows much less and we can sieve)

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

        I just wrote another solution which uses a priority queue (heapq in Python 3) which is pretty nice until test 77. Test 77 involves input of all primes and the expected output are those largest repeated primes. This is the worst input for my approach.

        I tried adding a prime sieve to tackle such special case when the input are all primes. But just the prime sieve itself took up 3000ms, and the bad news is, my heap solution alone took up nearly 900ms for some tests. That's frustrating when it's so close...

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

        Finally got it to work. Not the most elegant solution you would expect. In fact, it's pretty ugly I feel like my face is turning red just by looking at it. But at least that's an AC.

        EDIT: The above solution got hacked for TLE, and I tried switching to another approach. But with Python 3 this is not gonna work (TLE), with PyPy 3 the same solution got AC. The main idea of this approach is to iterate all factors from 2 to 10000000 and find the two smallest multiples in the list. Can't get away when the factors of the answer itself are very large, and plenty of time is wasted on smaller factors.

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

    I did the following thing:

    1. store the occurring index of each element in the range of a;
    2. loop through the whole range;
    3. which looping, just assume the current gcd we are checking is some multiples of current i, then the first two we find would be the local minimum, thus we should stop here.

    The number of operations should not exceed 2.4e8.

    You could check my implementation here: 52849391

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

    Suppose we find $$$\underset{x | a_i \text{ and } x | a_j}{min} (a_i*a_j /x) $$$, Note that minimum lcm of any two values is the answer for the stated. Therefore solution to first problem is solution to second. Now to solve first, for a given x, for minimum, a[i] and a[j] must be minimum. Thus for each x, just consider its two multiples that exists in array.

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

    I have a funny solution for G. ACC at the moment but probably hackable. The idea behind my solution is to try as many promising pairs as possible and stop just before we reach the time limit, hoping that we were lucky enough to find the best pair.

    My implementation is here: https://codeforces.com/contest/1154/submission/52868067

    The main computation is simply iterating all pairs in the order of smallest to largest. In order to speed up the computation we want to find a reasonable upper bound for lowest lcm before this main computation. This allows us to stop iterating i,j pairs when j>bound. I'm finding the upper bound by iterating all pairs of the lowest 30 non-duplicate items. Duplicate items can be used to construct a worst case scenario where we iterate the same pairs over and over again and reach the time limit before we get to try the optimal pair. We deal with duplicate inputs as a special case before the main computation. So the actual implementation is in this order:

    1. Deal with duplicates as a special case
    2. Find upper bound for lowest lcm by iterating all pairs of the lowest 30 non duplicate items
    3. Main computation: try all pairs from smallest to largest, with a speedup using the upper bound.
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Idk Java. Is your seed fixed? If yes? Then for sure your soln is hackable,

      As far as duplicates is concerned. Find the smallest no which occurs twice. It is probable answer.
      Then create a array which contains all nos only once. Then work on it.

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

        Default seed for Random in Java is current time in milliseconds.

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

          you don't need to hack based on the seed... the propability of this working is quite low...

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

            Congratz on the hack! Would you like to share the hack input?

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

              a lot of unique primes and a few composite values

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

I think this is the definition of a perfect Div. 3 contest. All the tasks were well explained, simple to understand and most importantly DOABLE for someone with a rating below 1600. Maybe i say this because i finally managed to solve 5 tasks (lol), but it was a great experience. Looking forward to the editorial, to see how F and G were supposed to be solved.

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

    Yeah, I think it will be good for everyone that rating below 1600 solve all the problems after contest.

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

    I agree this was a great Div. 3 contest, although the tasks could have been explained better. I had to ask questions about 2 tasks because of ambiguities in the statements.

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

That moment when everyone is thinking how to solve the problems and you are debugging some stupid mistake in your code that has nothing to do with the problem

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

    I, for one, spent 15 minutes to realize I've declared an array using 'bool' instead of 'int'. Yeah.

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

    happened with me, spent 40 minutes on C, Accepted just after 2 minutes when contest was over. Now I am feeling useless X_X

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

What is the problem in my E solution? I m getting TLE in TC #37 solution: Solution

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

    Got 37 TLE as well at first, but try using next/previous arrays instead of the boolean 'taken'. Where next[i] — the next student after i that isn't taken in any team. (so goes with previous)

    EDIT : With the boolean array, the complexity can come close to O(n^2)

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

      how to do that?

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

        First set next[i] = i + 1 and prev[i] = i — 1 Then say you start with the biggest value in the sorted array. You go k positions up and k down (assuming you sorted the array keeping track of the original positions). Now say the position of the biggest value is POS, you go to POS + k and POS — k and you set next[POS — k — 1] = POS + k + 1 and vice versa, so that you won't go through them again. Lastly, instead of doing POS++ while going thorough the elements, you say POS = next[POS] or POS = prev[POS] to save time.

        I'm terrible at explaining.

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

          U r too good in explaining...thanx buddy

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

I got two wrong submissions in Problem D because at last in Output section they said that print the max segment where Robot can reach. So, I just added the remaining value of the battery and the accumulator to get the final answer, whereas it was wrong, and when I removed them, I got Accepted. It's wrong they must have mentioned that N will be the maximum value, where Robot can reach.

I know it was written that Robot's target is to reach N. But clearly, there was no mention in Output part. And that led me almost 30-40 penalty plus I wasn't able to submit E, which was quite easy.

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

Vovuh I'm trying to hack problem G and got unexpected verdict while hacking. Hacking id is 550275.

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

    It was because of one of my testing solutions. I was not sure that it is correct and just forgot to tag it as "time limit exceeded or correct". All is ok now, the main solution is fast enough and written without bugs :)

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

can someone please give some hint for problem F and G?

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

    Problem F:

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

      Thanks. Actually I have implemented the same solution but due to some bugs it is not passing! Btw did you know how to solve G?

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

      Can the number he buy over the number he need to buy??? For example 6 1 5 1 2 3 4 5 6 6 5 If he buy 6 shovels,he can just pay 6 dollars.

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

    F : Just consider k shovels with least cost. And store for each 1 <= i <= k, maximum number of shovels you'll get for free, if you buy i shovels. Rest is just knapsack.

»
10 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Finally!!
Expert :)

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

problem E : Why when the array is sorted the program runs several times longer? I don't understand why.

»
10 days ago, # |
  Vote: I like it +23 Vote: I do not like it

I am very sorry about my bug in the problem G checker. It affected literally two people and just see how it looks:

I'm just TRYING to read two distinct integers $$$i$$$ and $$$j$$$ where $$$i < j$$$:

int i = in.readInt(1, n, "i") - 1;
int j = in.readInt(i + 1, n, "j") - 1;

I've tried... Really tried...

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

    Just curious how did this cause the bug in the checker ?

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

      If participant prints two equal numbers, this case will be considered correct and the checker will not raise any exceptions (in fact it should say that it is wrong to print two equal indices) and in case when LCM of $$$a_i$$$ and $$$a_i$$$ is less than the jury answer then checker will raise "FAILED" verdict and say that jury answer is incorrect.

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

        Oh. Really a tough thing to notice. Anyways problems were nice and it didn't affect much :)

»
10 days ago, # |
  Vote: I like it -25 Vote: I do not like it

In problem D:

problem statement said: If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can't become higher than it's maximum capacity).

But it is not said that if the charge of the accumulator exceeds it's maximum capacity, then you can't use battery during sunlight. I thought battery can be used but the charge of accumulator will not increase in this situation, when accumulator has already maximum charge.

Vovuh I think you should clarify this in the problem or give a sample input using such situation.

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

    sure you can use your battery during sunlight whenever your battery > 0; but that's not optimal strategy

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

      I got your point, I didn't think that way. I thought we can't use battery during sunlight in case after increasing the charge exceed the accumulator's capacity. Though I got AC thinking so and checking the condition, now I understood that the actual cause of not using battery is "not optimal".

      Thanks.

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

unfortunately very weak tests, only 11 tests for problems A B C. Please do more tests in the future.

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

In problem G, I got this in one of test cases
wrong answer Integer parameter [name=j] equals to 557392, violates the range [557393, 1000000]
What does it even mean! Solution link.

UPD: Figured out the error.

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

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

My first CodeForces round ever! I'm really excited, I have also dedicated myself starting today to solve at the very least 3 programming problems daily.

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

The problem A look like -a+b, a+c, b+c and a+b+c before the update

This silenced me for 20 minutes. :<

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

WOW! such strong pretests -_-

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

Thank you guys for this contest. I really enjoyed solving the problems and do think that it was a well balanced contest. :)

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

Weak pretests for B :(

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

    what according to you is a strong pretest?. There were only 5-6 conditions which were needed to be handled

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

      There were three cases in this problem:
      1. Make all the elements equal to ak+d,
      2. Make all the elements equal to ak-d, or
      3. Make all the elements equal to ak.
      for any 1<=k<=n. If we get a constant d(in case of multiple values the smallest one) then it will be the answer otherwise print "-1". My submission gone wrong because I've missed the 3rd case which appears to be one of the basic case.
      5
      4 2 6 2 6
      this test case covers the third case.I think which was missing in the pretests.
      My submission wthout handling 3rd case 52834854 and with handling 3rd case 52891662

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

        Oh I didn't know that. If I could have found such a submission I could have made my first hack. Btw I am really inspired seeing your love for India

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

Is this round rated? system test had finished, why my score isn't update?

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

is it rated?

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

my solution got compilation error during the system test case and when i coped the same solution and resubmitted it i got all correct vovuh please look at this as i lost my rating due to this bug of codeforces my submission link is[submission:52856023]

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

.

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

    try this, input : 1 2 3 it's supposed to print 5 because when you start on wednesday you can eat 2chicken, 2 rabbit and 1 fish, but yours print out 3

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

      After Wednesday: 1 2 2 After Thursday : 0 2 2 After Friday : 0 2 1 After Saturday : 0 1 1 On Sunday it doesn't have food so is not answer 4 in this case?

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

        sorry I made a mistake, you should start on Tuesday to make output 5

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

In problem E Using long long got TLE Using int got AC Why??

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

    This may happen in many problems who have tight time complexity so it is better to use long long int only where it is needed and always use the fast input method. otherwise, in many cases, it becomes very frustrating to find these kinds of mistakes.

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

Hii, I am new to java. Can anyone plz explain why this solution of F is getting TLE on test 66. 52900731

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

    Arrays.sort on primitive types is quadratic worst-case. Try using Arrays.sort on Integer or Collections.sort.

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

How to solve F?

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

Thank you for interesting contest, vovuh, waiting for editorial!

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

Can anyone provide some hint for how to solve G?

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

Problem G is exactly the same problem that has been asked on StackOverflow before. Link

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

    And so what? Did you see fast enough solution to our version of this problem in the link you posted? We have seen this link, but still gave the problem because we haven't found any fast solution in google.

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

I don't know, that's just accidental

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

How to solve F?

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

    My Approach :

    We need to buy K shovels at lowest possible prices. We will obviously use the K lowest priced shovels. Thus sort the array.
    Now we only need to save the offers (x,y) in which x <= K as we cannot buy more than K shovels.
    Make hash array where hash[i] stores maximum number of free shovels we can get by buying exactly i shovels using one of the offers.
    hash[j] = 0 implies no offer available on purchasing exactly j shovels.
    Now time to apply DP!
    let DP[i] be minimum cost to buy i shovels.
    To calculate DP[i] iterate j = 1 to i, and find min of DP[j-i] + cost to buy j-hash[j] shovels starting from index i. (cumm[i]-cumm[i-j+hash[j]])
    What we are doing is for every i simply apply every offer and check which gives minimum price and store it.
    DP[k] is required answer.
    Link to my solution.

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

      Can you tell me Why picking an offer first and then trying to minimize the cost by using this offer on number of shovels bought is a wrong approach, offers(x,y) are sorted in non-decreasing order of x. Link to code.

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

        Hey
        The ordering of offers is not the correct thing to do.You may have to re use an offer after using some other offer!.
        In fact my first few submissions were using similar approch and was getting WA as well.
        Consider two offers (5,3) and (2,1)
        If we use offer (5,3) before (2,1) for k=8 and A = [1,1,2,3,4,5,6] we get cost as 12 while if we use (2,1) before (5,3) we get cost as 13.
        But for case k=8 and [1,5,5,5,5,7,10] if we use (5,3) before (2,1) we get cost 22 while if we use (2,1) before (5,3) we get cost as 20.
        So we can order the offers as one order may give better value in a few cases but higher values in some cases.