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

Автор Vovuh, история, 12 дней назад, перевод, По-русски,

На этот раз мне нечего сказать, так что встречайте еще один Div. 3 раунд :)

<almost-copy-pasted-part>

Привет! В 14.05.2019 17:35 (Московское время) начнётся Codeforces Round #560 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу PikMike Пикляеву, Максиму Ne0n25 Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.

</almost-copy-pasted-part>

UPD: Я также хочу поблагодарить nhho, chenjb и ksun48 за тестирование раунда.

UPD2: Я также хочу поблагодарить моего друга Адилбека adedalic Далабаева за важные предложения по поводу контеста и его тестирование!

UPD3: Разбор опубликован!

UPD4:

Поздравляем победителей:

Место Участник Задач решено Штраф
1 nuoyanli 7 368
2 Vaseline_Warrior 7 437
3 adimiclaus15 7 446
4 1716638489 7 604
5 leo990629 6 335

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 Java 68:-2
2 figdan 63:-13
3 makjn10 44:-1
4 csts.21 40
5 shubhammitt 27
Было сделано 872 успешных и 341 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
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

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

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

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.

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

    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.

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

    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 ;\

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

Waiting for a hackforces!!! :D

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

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

Just kidding :)

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

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

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

Hope there are no server issues this time .. xD

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

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

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

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

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

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!

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

fine

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

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.

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

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

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

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

    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      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.
  • »
    »
    10 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    come on!

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

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

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

Can anybody explain E,please?

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

    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}$$$

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

    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.

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

      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 :)

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

        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]

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

    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.

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

In D what is input when ans is -1 ?

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

    for example: 1 2 2 8

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

      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

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

      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.

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

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?

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

    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]

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

    -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

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

    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.

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

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

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

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

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

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

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

    You search for bugs in codes of other people

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

    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.

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

what's the approach to solve C please?

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

    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

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

      Any proof?

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

        @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.

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

        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.

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

    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

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

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?

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

    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.

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

    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.

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

      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.

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

        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).

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

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

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

            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()

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

    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

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

    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.

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

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

    tmg-article-tall

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

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

Here is a quick editorial

A

Spoiler

B

Spoiler

C

Spoiler

D

Spoiler

E

Spoiler

F

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

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

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

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

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

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

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

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

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

      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. :)

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

    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.

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

    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?

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

2nd test case of D problem Ruined my contest.

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

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.

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

    Read the problem.

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

    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.

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

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

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

    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.

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

Good Round with strong pretests. Thanks Vovuh

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

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

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

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

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

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

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

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.

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

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

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

"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.

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

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

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

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

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

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

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

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

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

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 :)

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

    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.

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

      Thank you Ismael_Olvera.

      I got the point :)

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

      can u explain more ?

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

        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! :)

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

weak pretest:(

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

Is there any Pending System Testing now also?

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

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

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

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

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

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

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

Where is editorial ?? What about system testing ??

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

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

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

System Test has finished?

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

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

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

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

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

When system testing will be done for the contest??

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

when will contest ratings are going to be given ?

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

Is contest rated or not?

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

when will our ratings will come?

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

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

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

And Now whaaaaat!

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

When will the rating change come out?

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

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

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

this round unrated??

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

admins, plz press the start system test button

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

RATING CHANGE IS OUT ! ON THE RIGHT OF STANDINGS !

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

even system testing is not done.

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

Press the button.

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

FINALLY !!!

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

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

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

    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.

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

Why is the test so slow?

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

Was this round unrated?

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

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.

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

    Make your code readable and ask again

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

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

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

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

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

          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.

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

            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)$$$

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

              That's what I am asking. Why?

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

                $$$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$$$

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

                  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 дней назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

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

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

My rate didn't change yet Why?

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

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?

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

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

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

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

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

    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 :)

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

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

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

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