Vovuh's blog

By Vovuh, history, 5 months ago, In English,

I have nothing to say this time, so meet yet another Div. 3 round :)

<almost-copy-pasted-part>

Hello! Codeforces Round #560 (Div. 3) will start at May/14/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: I also would like to thank nhho, chenjb and ksun48 for testing the round.

UPD2: I also would like to thank my friend Adilbek adedalic Dalabaev for valuable suggestions about the contest and testing it!

UPD3: Editorial is published!

UPD4:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 nuoyanli 7 368
2 Vaseline_Warrior 7 437
3 adimiclaus15 7 446
4 1716638489 7 604
5 leo990629 6 335

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Java 68:-2
2 figdan 63:-13
3 makjn10 44:-1
4 csts.21 40
5 yashi2552 27
872 successful hacks and 341 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A Tokisaki-Kurumi 0:03
B CoolAttacks 0:03
C igniubi 0:08
D foool 0:13
E maverick_10 0:15
F1 cunt 0:27
F2 cunt 0:26

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

»
5 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Isn't the 12-hour hacking phase an overkill? I mean because most of the hacks are done within the first 6 hours or so.

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

    Of course not, the hacking phase starts at 0:35 in Hong Kong, but I'm a lazy guy who wakes up at 12:00 everyday XD.

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

    do you now one time in edu contest i submit a code that shoud get TLE but after hours nobody hacked me
    so i said to one of my freinds that my code is wrong after that he hacked me :\ the cool thing is that i submit that code with another handle and it got AC ;\

»
5 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Waiting for a hackforces!!! :D

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

I have nothing to say this time, ... I also would like to say that participants who will submit ...

Just kidding :)

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

    Honestly, I understood the meaning of your joke only a couple of minutes after downvoting your comment XD XD XD

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

Hope there are no server issues this time .. xD

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

The third category is good for people whose level is poor because it easier more than the second category

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

More < copy-pasted-part >< /copy-pasted-part > ?

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

Vovuh's Division 3 Rounds are usually balanced and contain interesting problems, I hope this contest lives up to that standard as well! Good Luck To All Participants!

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

    @Java

    I agree! A was especially interesting. ;)

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

      Woah, are you the real ben shapiro.

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

        I am not, what the moo? Are you high on geniosity?

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

          Aren't you the guy that destroys people with facts and logic?

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

fine

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

If there is a server issue just try the baby sites, they work well. It saved a lot of time for me in the last contest.

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

was my best contest ever..solved 5/7 . please dont hack me .

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

    How did u solve D?(I've got WA on 32nd testcase and I am mad).

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it
      1. sort the almost divisor list
      2. check if it satisfies. lets say our number X. divisor[i]*divisor[n-1-i]==X
      3. count the number of almost divisors of X. it must be equal to n.
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    come on!

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

So, are we allowed to discuss problems during 12 hour phase?

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

    ofc, you can't submit anymore

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

    Since the solutions are visible discussions should not be a problem.

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

    Yes.

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

    Yes

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

      почему ты игноришь серых?

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

      Hi MikeMirzayanov I tried to hack my friend submission and get "Unexpected verdict" as a verdict for my hack how ever my friend submission should take RunTimeError as verdict of my hack test "I try that on Custom Invocation" my hack id is 558494 on problem D Is It a Bug in hacking system or what? Thanks

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

Can anybody explain E,please?

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

    Greedy. First you have to calculate appearance of each $$$a_{i}$$$ and multiply it with $$$a_{i}$$$. Then sort both of arrays and reverse $$$a$$$ (or $$$b$$$). Answer is $$$\sum\limits_{1 \le i \le n} a_{i}*b_{i}$$$

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

    Think in fixed values, the array $$$a$$$ and how many times the number $$$a[i]$$$ (0 index base) appears in the sum expression, so you can create an new array $$$staticval$$$. Note that $$$staticval[i]=a[i]*(n-i)*(i+1)$$$ for each $$$0 \leq i \leq n-1 $$$, then you arrangue the $$$b[i]$$$ values as you need (sorting $$$b$$$ and $$$staticval$$$), note that $$$staticval$$$ array have values less than $$$10^{18}$$$, so you always can obtain the answer.

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

      Hey. What is the problem in my solution? Here is the code: Code.

      I sorted a in ascending and b i descending order and Multiplied corresponding elements . Sorted back the product in order of corresponding elements of array a. Finally I printed the summation(f(l,r)) for 1<=l<=r<=n in O(n). Please explain :)

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

        You should You should make the {a [i] * (n — i) * (i + 1)} * b [i] minimum, rather than {a[i]*b[i]}*(i+1)*(n-i)

        So you should make tmp[i]=a[i]*(n-i)*(i +1).sort the b array

        So the answer should be ∑tmp[i]*b[i]

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

    Assume that you have the optimal array as C. So we have to find the minimum of \sum_{i = 1}^n(i)*(n-i+1)*a_i*c_i (This is because the i'th element will occur when l can be anything from 1 to i and r can be anything from i to n so i'th element will occur in i*(n-1+i) number of times). So we can rearrange b_i to form C. So to get the total minimum sort the modified A array where a_i = a_i * i * (n-i+1). and array B. And then for the minimum multiply a_i & b_{i-1}. Here is the code for this.

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

In D what is input when ans is -1 ?

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

    for example: 1 2 2 8

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

      We can't have 1 2 2 8 as test case because 1.all factors given are distinct 2.1 or the actual x is not given in the factors list

      You may Consider Sample case where factors are: 2 3 4

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

        first number = t. second number = n

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

          Sorry, I misunderstood.

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

            but they have said it will contain all factor , so what will be the answer

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

      I don't think that's a valid input array. I think it's more along the lines of 4 8.

      The answer to this is -1 because whatever number is divisible by 4 and 8 must also be divisible by 2, yet 2 is not in the input array.

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

        i am confused. if all factor has given except 1 and x then 2 should be in input. please clear it to me.

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

          Yes, that's why the answer is -1, because the input data is contradictory.

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

How to construct array in Problem E such a*b is minimized?

I tried by first taking frequency of each element in final answer which for each index i came out as i*(n-i+1). This is increasing and then decreasing sequence. So for final array, we can take smallest b value at middle position and distribute b by moving from the center of array a. But this approach seems incorrect since it gets wrong on given first test case itself.

How to construct the array so that final sum is minimized?

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

    multiply a[i] with its query frequency, sort the two arrays in reverse order of each others then calculate sum of a[i]*b[i]

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

      And be careful with overflows!

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

      Thanks ! Was multiplying a[i] with its frequency at last.

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

      why do we multiply a[i] with its query frequency ?

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

    -i constructed mul[i] array as the freguency of each element times a[i], mul[i]=a[i]*(n-i)*(i+1) {my i starts from 0}; -then sorted mul[], and b[] -reverse b[] -k=(k+b[i]*mul[i])%M

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

      Thanks ! Was multiplying a[i] with its frequency at last.

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

    Assume that you have the optimal array as C. So we have to find the minimum of \sum_{i = 1}^n(i)*(n-i+1)*a_i*c_i. So we can rearrange b_i to form C. So to get the total minimum sort the modified A array where a_i = a_i * i * (n-i+1). and array B. And then for the minimum multiply a_i & b_{i-1}. Here is the code for this.

»
5 months ago, # |
  Vote: I like it -26 Vote: I do not like it

I dont feel like having anything learned from these problems. Its just understanding difficult language and fiddling with indexes. Not the fun stuff.

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

What is wrong in my code guys? Can you help me? Its about problem E: https://codeforces.com/contest/1165/submission/54136675

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

    a[i]*b[i] can overflow,can do (a[i]%mod)*(b[i]%mod)

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

      Why? Its impossible in my view! a[i] is already % mod, and b[i] max value is 10 in the power of 6, so max value is 10 in the power of 16!!!

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

        You are right. Your mistake is modding array $$$a$$$.

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

          Does it matter if a take %mod of a and not taking of b?

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

            a[i] = (((n-i+1LL)*i)*a[i])%mod;

            When u mod $$$a_{i}$$$, sorting goes wrong.

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

              aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa thank you

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

              Thanks...Such a minute observation...Finally able to solve it after reading this comment...

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

    you don't mod after you multiply with the frequency

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

It's my first codeforces contest. Can anyone please explain to me what is this hacking period?

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

    You search for bugs in codes of other people

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

    During hacking phase, you may read other's code and find bugs in them (maybe their code fails in some test case, likely corner cases or something similar).

    If you successfully find a test case in which their code may fail, you get some points and the latter loses his/her because of wrong verdict (Hacked in this case).

    On the contrary, if their code runs successfully providing correct output on your provided test case, you will face an unsuccessful hacking attempt and lose your points.

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

what's the approach to solve C please?

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

    Start in the first position anf, greedly, start checkin if s[i]==s[i+1], if its equal, erase s[i] and chande the odd positions to even positions, this is the answer if the string is even, otherwise, erase the last position

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

      Any proof?

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

        @Alphatrance

        It is required if you have elements starting from odd position, say xxxxy, that next element must be different. So its gauranteed to delete one of the above 4 possible x. Even if you delete first 3 x, you have last x, come into original position in the new string, as you would have deleted the last 3 x.

        Also, If you move from left to right, deleting, you gaurantee that that prefix will always be a good string, irrespective of what happens in the next part.

        Thus the greedy approach follows.

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

        Suppose that i is the least position at string s that s[i]==s[i+1] and i is odd. If you dont erase it, or the next element, you will never change the parity of the positions <= to i and you will never erase them, so you have to erase all the positins from the beggining with the conditions of the problem.

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

    for every odd index, if(str[i]==str[i+1]) just remove str[i]

    after that, if str.size() is odd then remove last index

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

I had the following strange issue when sorting in Java:

In both problem B and E, I got TLE when using Arrays.sort but AC when using Collections.sort. Has anyone else encountered this problem?

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

    I have encountered it too. I didn't try Collections.sort(). I'm getting mad. Just can't understand why Arrays.sort() gives time limit exceeded verdict.

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

    Arrays.sort() uses the quicksort algorithm, whose worst-case running time is O(n*n). The other day one of my solutions for a Div.3 problem was hacked because someone created a counter test on Java's sort method, from this time on I coded a custom mergesort function with guaranteed O(n log n) performance.

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

      Ah, cheers, you're absolutely right (see this article). However, I don't think you have to code your own sorting algorithm since, apparently, the worst-case time is O(n log n) when sorting objects.

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

        Well, it's just 30 lines of code that I copy-paste, and more often I sort primitive types (in problem E, where I used mergesort, I sorted an array of longs).

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

          That's a good point. Alternatively, one could use Long instead of long.

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

            Well, the overhead is rather high when you have big input data, it's faster to simply mergesort and forget about it :)

            In contests like Google Code Jam, it's much less of a problem, since the TLs are on the order of 15s, enough to make an unoptimized solution fail, but high enough to allow slight low-level inefficiency like the one you mentioned (Long vs long). And no one tries to come up with a corner case for Arrays.sort()

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

    I am pissed off ! I don't know why a nlogn code shows tle (using sort) in java then I submitted in python it's get accepted. even in next problem I m getting tle...uh

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

    in the first time I encountered the same problem (TLE). Then I used TreeSet instead of Arrays/ArrayList, it will sort by itself and collect distinct numbers.

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

    In my job I am practicing java and I am facing...

    tmg-article-tall

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

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

Here is a quick editorial

A

Spoiler

B

Spoiler

C

Spoiler

D

Spoiler

E

Spoiler

F

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

    your E is wrong you shouldn't mod after multiplying with frequency

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

    You cant % array A before sorting, it gave me Wrong Answer ...

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

    In problem F, on i th day can i order more than 1 types of micro-instruction?

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

    For problem D can someone explain the formula for the number of divisors? p1^e1 * p2^e2 * ...

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

      Suppose, N be a number. Then N can be written as follows:

      N = p1^e1 * p2^e2 * p3^e3 * p4^e4 * ......... * pk^ek

      This is called prime factorization of N. Now, if 'd' is a divisor of N, 'd' shouldn't contain any other prime except (1 <= pi <= k). And the power of pi should be within (0 — ei).

      so d = p1^b1 * p2^b2 * p3*b3 * p4*b4 * .........* pk^bk, where, 0<=bi<=ei

      For a single prime it can be present in a divisor in (ei+1) ways [ pi has power from 0 to ei ]

      so total number of divisor (NOD) = (e1+1) * (e2+1) * (e3+1) * (e4+1) * ...... * (ek+1)

      I hope its clear to you. :)

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

    I have a small doubt in this problem F1,F2. Can we buy more than one types of microtransactions in a single day? e.g. 1 of type 1, and 1 of type 2 etc. Or its just that we can buy any number of any SINGLE microtransaction each day?

    From your code it seems that we can actually buy multiple types. But this was not that clear from the problem statement.

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

    In F the question doesn't ask us to keep the money spent minimum, so why don't we buy all type on the first day?

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

2nd test case of D problem Ruined my contest.

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

shouldn't E be solved this way ?:

first sort a, and b array. Then by rearrangement inequality, minimum order must be a1b1 + a2b2 + .... .

Then for effective (O(n)) calculation, I used this (where pr[n] = a1 + a2 + ... a3, ... i.e. prefix sum)

    fr(i, n){
        ans += ((((1ll*pr[i+1])*(1ll*b[i]))%mod)*(n-i))%mod;
    }

which I think is correct formulation, but its giving me 643 instead of 646 for 1st test case. Can someone help please?

Thanks.

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

    Read the problem.

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

    It's because you are not allowed to permute array a, only b. There are also other errors with your solution. You are not adding to the final answer correctly. Check this.

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

    do exaclty the same but not sorting A before you do the algorithm above

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

    rupav Sort A after multiplying with the coefficient (i*(n-i+1)) i.e. Sort the Array ModifiedA where ModifiedA[i] = A[i]*i*(n-i+1).

    See this solution.

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

Good Round with strong pretests. Thanks Vovuh

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

    No the pretests were very weak for A. And to prove my point I hacked you. (Sorry)

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

      Your way of proving things is really very harsh.

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

        Perhaps, but if it’s any consolation, your code would have been tested through other hacks anyway at the end of the contest.

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

I use binary search to solve B, I use std::lower_bound got correct 54118173 ,but I try to use std::set::lower_bound got incorrect 54110418, could somebody tell me why...ORZORZ

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

    Yes, lowerbound(set.begin, set.end, value) will take O(n). Instead you should use set.lower_bound(value)

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

    Check this test case: Input: 1 3 3 Output: 3 Your output: 2 Set erases not unique elements

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

    In your second submission you used set. set does not contain any duplicates. That's why. Consider This case:

    5
    5 5 5 5 5
    

    then set will contain only one 5. So your output will be 1 instead of 5. Change your set to multiset you will get AC.

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

    ORZ ORZ

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

What kind of test cases are being used to hack A?

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

This contests was good except for weak pretests. For example I was hacked on A, and I know why I was hacked. I am surprised that pretests didn't catch this simple bug and my rating is going to suffer. I am dissapointed.

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

Great round with great problems! No issues with the servers either. Thank you

»
5 months ago, # |
  Vote: I like it -23 Vote: I do not like it

"I tried to make strong tests." While I believe this is true, I don't believe much thought or time went into them as seen by how many people were hacked on A. I know that Vovuh does many rounds but maybe he should take some time before finalizing it.

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

    I feel like Vovuh should give you a rebate for those lost points man.

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

    Hacking is a part of contest. If pretests are made very strong then what is the point of hacking?

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

time to change the name of codeforces to hackforces ...

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

Did anyone notice the number of submissions of F1 is exactly equal to the submissions of F2.

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

Strong tests !! Is the meaning of strong has been changed lately ?

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

Is E polinomially solvable if we are allowed to permute both a and b ?

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

Can anybody explain the first sample input/output of problem E ?

Input:

5
1 8 7 2 4
9 7 2 9 3

Output:

646

The problem statement isn't clear to me :)

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

    If you reorder the elements of b in this way:

    9 2 3 9 7
    

    You'll have the next sums:

    $$$ f(1,1) = 9, f(1,2) = 25, f(1,3) = 46, f(1,4) = 64, f(1,5) = 92 $$$

    $$$ f(2,2) = 16, f(2,3) = 37, f(2,4) = 55, f(2,5) = 83 $$$

    $$$ f(3,3) = 21, f(3,4) = 39, f(3,5) = 67 $$$

    $$$ f(4,4) = 18, f(4,5) = 46 $$$

    $$$ f(5,5) = 28 $$$

    Then the total sum will be:

    646
    

    P.D. I hope this has helped you better understand the test case.

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

      Thank you Ismael_Olvera.

      I got the point :)

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

      can u explain more ?

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

        Of course. The task in this problem is reorder the elements of the array $$$b$$$ (the array $$$a$$$ can't be moved). We need to reorder $$$b$$$ in such way that the value of the following expression is the minimum possible.

        $$$\sum\limits_{1 \le l \le r \le n} f(l, r)$$$

        For clarity, let's call $$$c$$$ to the array such that $$$c_i = a_i * b_i$$$

        How does $$$\sum\limits_{1 \le l \le r \le n} f(l, r)$$$ mean?

        The expression is equal to say: "take all the possible subarrays in c and apply them this function, finally sum all the results".

        Example:

        $$$ a = [1,8,5] $$$

        $$$ b = [9,4,7] $$$

        If I choose this order, $$$ b = [4,7,9] $$$, the array of multiplications, $$$c$$$, will be $$$ c = [4,56,45] $$$. Finally the sum of apply the functions to all the possible subarrays is:

        $$$ 371 = (4) + (56) + (45) + (4+56) + (56+45) + (4+56+45) $$$

        If I choose the order, $$$ b = [7,4,9] $$$, $$$c$$$ will be $$$ c = [7,32,45] $$$. And the sum of apply the functions to all the possible subarrays is:

        $$$ 284 = (7) + (32) + (45) + (7+32) + (32+45) + (7+32+45) $$$

        As you can see, the order $$$b = [7,4,9]$$$ is better than $$$b = [4,7,9]$$$.

        Note: If you have $$$n$$$ elements in the array, there are $$$n!$$$ ways to reorder $$$b$$$.

        Test case:

        $$$ a = [1,8,7,2,4] $$$

        $$$ b = [9,7,2,9,3] $$$

        As I said before, the best way to reorder $$$b$$$ is: $$$ b = [9,2,3,9,7] $$$.

        Just for extra help, the array that I called $$$c$$$ should be: $$$ c = [9,16,21,18,28] $$$.

        I hope this explanation can help you! :)

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

weak pretest:(

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

Is there any Pending System Testing now also?

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

Is this contest unrated? Because my rating is not updated yet, and my rating is less than 1600.

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

    Just wait, it should be updated soon

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

      Oh.. Okay. Actually the hacking phase was finished. So thats why i asked.

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

        The thing is that the system's checking all solutions w/ hack-tests.

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

Im about task D. Why the answer for this test is 9, not 6? k = 1, n = 1, d1 = 3.

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

    Because for 6 dividers will be 3 and 2

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

    For 6, the almost divisors will be 2, 3. Whereas 9 will only has 3 as almost divisors.

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

the first problem data is so easy I was hacked:(

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

Where is editorial ?? What about system testing ??

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

Is this contest unrated?Why I don't get rating changes?

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

    I don't know nobody said it's unrated

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

    System still calculating something, my standing first dropped from 500 to 1700, now it's changing between 1500-1700

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

      Emm,I got it.Thanks.

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

      Your A got hacked by someone that's why your standing dropped from 500 to 1700.

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

        See! it's because of my standing. 500 to 1700 was too much for a hacked A and it caused indecisive loop between 1500 and 1700. Now system test restarted to decide it :P

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

System Test has finished?

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

Can someone post a solution in Python for "D — Almost All Divisors" without "Time limit exceeded on test 4"?

Or show me error in my code https://codeforces.com/contest/1165/submission/54168485

Updated 1: Fixed logical errors, still TLE

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

I submit D at the last second,and failed because of my poor Broadband net T.T

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

When system testing will be done for the contest??

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

when will contest ratings are going to be given ?

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

Is contest rated or not?

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

when will our ratings will come?

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

    using cf-predictor you can know your rating change will be +139 if any solution don't get wa on system test.

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

      Guess mine as well:)

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

      Yes i know that if my solutions will not get wa i will take about +139 but i want to take my +139

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

And Now whaaaaat!

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

When will the rating change come out?

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

MikeMirzayanov Ratings are not updated yet ...Pls look into the matter

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

this round unrated??

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

    No, I think it's not as written in the rules...but it's very late this time..hope it will be updated soon.

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

    still some system test is going on

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

admins, plz press the start system test button

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

RATING CHANGE IS OUT ! ON THE RIGHT OF STANDINGS !

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

even system testing is not done.

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

Press the button.

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

FINALLY !!!

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

I have a question in problem D, I have the same ideas

  1. sort the divisors
  2. make them all ans = ans * divisor[n] / __gcd(ans,divisor[n])
  3. if ans = MaxDivisor , ans *= MinDivisor , then list all the divisors of new ans.

but I've got WA on test 5, and after some tries finally WA on test 6,I really feel frustrated . Could someone tell me why my code is wrong?54168335

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

    Just try for find countertests.
    1
    3
    3 4 9

    Your output: 36
    Right answer: -1

    P.S. Try to check found number for correctness before printing.

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

      Really Thanks . Now I have found My mistakes !

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

Why is the test so slow?

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

Was this round unrated?

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

Please tell why my approach for Problem E is incorrect?

My Solution: https://ideone.com/tBe1up

I am also doing like mapping max value of a with min value of b and so on. And then calculating the answer using dp like dp[i] denotes the answer for ai and bi arrays till index i.

Please tell, I can't figure out the same.

Editorial is doing the same thing for vali as given.

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

    Make your code readable and ask again

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

      Don't know why it was not readable. I made it public. Try this: https://ideone.com/tBe1up

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

        he means your code has too much define and others may not understand

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

          It is not much of define.

          ll means long long

          and fl(i,a,b) means for loop with range [a, b)

          and slld(a) means scanf("%lld", &a)

          Just this.

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

            I think mapping arrays $$$a$$$ and $$$b$$$ it's not enough, you need to map the array $$$a'$$$, that $$$a'[i]=a[i]*cnt*(n-cnt+1)$$$

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

              That's what I am asking. Why?

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

                $$$a=[4, 3, 2, 1, 2, 3, 4]$$$; $$$b=[1, 1, 1, 1, 1, 1, 1]$$$ sorting $$$a$$$ you get: $$$a=[1, 2, 2, 3, 3, 4, 4]$$$ so you $$$a[i]*b[i]$$$ is the same as $$$a$$$ finally, you have $$$ans=[1*7, 2*12, 2*15, 3*16, 3*15, 4*12, 4*7]$$$ but the answer is: $$$resp=[4*7, 3*12, 2*15, 1*16, 2*15, 3*12, 4*7]$$$ as you can see, it's not enough mapping $$$a$$$ and $$$b$$$

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

                  phibrain How did you came up with this thinking of using vali instead of ai, by using some test cases only or any other thing?

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

                  It's just a counterexample of a possible solution, so it's not hard to got that.

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

My rate didn't change yet Why?

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

Sorry for criticizing, but frankly I don't think Div 3 problems are easier than Div 2 in any sense.

Div 3 problems are implementation tasks and costs serious debug time, and this time Div 3 A is harder than Div 2 A (#559) imo. Other problems are also annoying implementations which I fail to debug quick enough to get a high rating.

Div 2 is generally a more relaxing coding experience for me, to calm down and think of ways to optimize to AC, but Div 3 is just me frantically debugging. 4 questions in Div 3 to increase rating is rusher than 3 in Div 2, don't we think?

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

Problem E- Can anyone please explain why that while using

long long int yyy=(n-i)*(i+1); a[i]=a[i]*yyy;

produces an error in https://codeforces.com/contest/1165/submission/54228312

whereas simply writing - a[i]=a[i]*(n-i)*(i+1) gets an AC

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

Hi, I am a newbie to codeforces. My approach for problem E is similar to that of above, however, I got an WA on testcase 5 IMO, this is due to overflow, but cannot figure out where since I have implemented required %mod in the arithmetic operations.

Deeply thanks for any constructional advices :)

My code

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

    Update: When I change from unsigned long long to long long, it magically AC,

    My code of AC

    Has anyone came across the same problems of using all for mod result resulted in a WA but changed to ll made an AC, any explanation or idea?

    Thanks a lot for the help :)

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

Regarding Problem C My code gives TLE . I've seen the editorial but I can't seem to find the problem in my code which leads to TLE. Here is the link to the code : https://ideone.com/fY10V4

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

I was the first one to solve problem E, yaaay! yaaay!