vovuh's blog

Codeforces Round #560 (Div. 3)
By vovuh, history, 6 years 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 awoo Piklyaev, Maksim Neon 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 smallguoguo 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 firefoooox 0:03
B CoolAttacks 0:03
C igniubi 0:08
D foool 0:13
E i_love_math 0:15
F1 cunt 0:27
F2 cunt 0:26

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

Comments Comments (193)
| Write comment?
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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 ;\

    → Reply
»
6 years 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 :)

→ Reply
  • »
    »
    6 years 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

    → Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Hope there are no server issues this time .. xD

→ Reply
»
6 years 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

→ Reply
»
6 years 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!

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

    @Java

    I agree! A was especially interesting. ;)

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

      Woah, are you the real ben shapiro.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Haha!

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

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

          → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -29 Vote: I do not like it

fine

→ Reply
»
6 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years 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).

    → Reply
    • »
      »
      »
      6 years 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.
      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    ofc, you can't submit anymore

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

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

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

    Yes.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    Yes

    → Reply
    • »
      »
      »
      6 years 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

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain E,please?

→ Reply
  • »
    »
    6 years 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}$$$

    → Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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 :)

      → Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In D what is input when ans is -1 ?

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

    for example: 1 2 2 8

    → Reply
    • »
      »
      »
      6 years 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

      → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
        • »
          »
          »
          »
          »
          6 years 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.

          → Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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]

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

      And be careful with overflows!

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

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

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

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

      → Reply
  • »
    »
    6 years 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

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

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

      → Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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.

→ Reply
»
6 years 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://mirror.codeforces.com/contest/1165/submission/54136675

→ Reply
  • »
    »
    6 years 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)

    → Reply
    • »
      »
      »
      6 years 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!!!

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

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

        → Reply
        • »
          »
          »
          »
          »
          6 years 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?

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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.

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

              aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa thank you

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years 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...

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

    you don't mod after you multiply with the frequency

    → Reply
»
6 years 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?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what's the approach to solve C please?

→ Reply
  • »
    »
    6 years 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

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

      Any proof?

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
  • »
    »
    6 years 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

    → Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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).

        → Reply
        • »
          »
          »
          »
          »
          6 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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()

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

    Read this: How to sort arrays in Java and avoid TLE

    → Reply
  • »
    »
    6 years 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

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

→ Reply
»
6 years 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
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

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

    → Reply
  • »
    »
    6 years 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?

    → Reply
  • »
    »
    6 years 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 * ...

    → Reply
    • »
      »
      »
      6 years 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. :)

      → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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?

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

2nd test case of D problem Ruined my contest.

→ Reply
»
6 years 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.

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

    Read the problem.

    → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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

    → Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Round with strong pretests. Thanks vovuh

→ Reply
  • »
    »
    6 years 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)

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

      Your way of proving things is really very harsh.

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
»
6 years 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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years 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.

→ Reply
»
6 years 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

→ Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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?

    → Reply
»
6 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
6 years 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.

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
6 years 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 ?

→ Reply
»
6 years 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 :)

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

weak pretest:(

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Is there any Pending System Testing now also?

→ Reply
»
6 years 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.

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

    Just wait, it should be updated soon

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Where is editorial ?? What about system testing ??

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

System Test has finished?

→ Reply
»
6 years 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://mirror.codeforces.com/contest/1165/submission/54168485

Updated 1: Fixed logical errors, still TLE

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

When system testing will be done for the contest??

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

when will contest ratings are going to be given ?

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

Is contest rated or not?

→ Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

when will our ratings will come?

→ Reply
  • »
    »
    6 years 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.

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

      Guess mine as well:)

      → Reply
    • »
      »
      »
      6 years 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

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the rating change come out?

→ Reply
»
6 years 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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this round unrated??

→ Reply
  • »
    »
    6 years 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.

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

    still some system test is going on

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

admins, plz press the start system test button

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

RATING CHANGE IS OUT ! ON THE RIGHT OF STANDINGS !

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

even system testing is not done.

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Press the button.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

FINALLY !!!

→ Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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.

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

      Really Thanks . Now I have found My mistakes ！

      → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is the test so slow?

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

    It often takes some (1 to 2) hours to run system test

    → Reply
»
6 years 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.

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

    Make your code readable and ask again

    → Reply
    • »
      »
      »
      6 years 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

      → Reply
      • »
        »
        »
        »
        6 years 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

        → Reply
        • »
          »
          »
          »
          »
          6 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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)$$$

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

              That's what I am asking. Why?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years 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$$$

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years 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.

                  → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My rate didn't change yet Why?

→ Reply
»
6 years 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?

→ Reply
»
6 years 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://mirror.codeforces.com/contest/1165/submission/54228312

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply