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

Автор Stepavly, 4 года назад, По-русски

Привет, Codeforces!

<almost-copy-pasted-part>

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

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

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

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

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

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

Задачи на этот раунд были придуманы MikeMirzayanov, Supermagzzz, Stepavly и sodafago.

Спасибо Gassa, darkkcyan, bfs.07, Tzak, songsinger, Mukundan314, iankury, drunya, sodafago, ChOmPs, Programmer, Khairy, IITianUG, Rox за помощь в тестировании раунда!

Спасибо MikeMirzayanov за платформы и координацию нашей работы. Удачи!

</almost-copy-pasted-part>

Разбор: https://mirror.codeforces.com/blog/entry/89535

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

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

UPD : sorry

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

is it only me who see only this announcement in russian and rest are in english?

UPD : Now it is fine for everyone :)

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

from today all indian coders have a big problem wheather to give codeforces round or to watch IPL

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

122

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

Clashing with Codejam Round 1A :(

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

I think Everyone Love to see it :)

Captu1re

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

Yep, my mistake, Sorry!

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

I wish i would solve atleast 3 to 4 problems in this contest

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

Good luck to all

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

After a long time,I've got my focus back & feeling the same excitement I was used to feel.Hoping the contest will end smoothly.Good luck to me, Codeforces and all. :-) (Thinking,what will happen if Codeforces have an emoji that express excitement levels? :3)

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

It's sad that I can't participate in this Div. 3 because of my courses...
Maybe I'll participate in the Div. 2 tomorrow, but I'm not quite sure yet. Maybe I will be absent in CF contest for a long time...
btw, wish me good luck for my senior high school entrance examination QAQ

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

aboba

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

first time doing contest.... it's hard for me....(cry....:<)

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

    This was the lowest division and in my opinion, the problems were easier than other Div3 contests. I'm not saying this to discourage you but to give you advice. Maybe codeforces is a little too hard to start with. You can learn the basics from this website (https://www.pbinfo.ro/). It's a website from my country which takes you from zero to hero (or at least doing the first 2-3 problems in Div2 in less than 1 year, haha) You only have to translate the page to English when you enter the site. Good luck with your coding journey! I hope I gave some positive thoughts!

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

    dont listen to alexadru7, just solve 800s instead, and if those are still too hard, do leetcode (but they shouldn't be that hard)

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

Thanks for the great round!

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

Too much implementation :(

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

Please someone give idea for Problem E. Thanks in advance!!

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

    First take the at least number if l to r difference is 3 then take the number 1 2 3 if its greater than s then answer must be -1. other wise try to replace every number with large unused number as if sum of those number not exceed s. if sum==s you find the result.

    implementation

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

    you_ create new array have size = r-l+1. make array from 1 to r-l+1. add 1 to arr[pos]._ _You start with pos = size — 1. if arr[pos] == pos then pos--

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

    Here $$$sum(x)$$$ denote sum of $$$1, 2, 3, ..., x$$$. Let $$$len=(r-l+1)$$$. A solution exists if and only if $$$s>=sum(len)$$$ && $$$s<=sum(n)-sum(n-len)$$$. Now to simulate the process, take numbers from $$$1$$$ to $$$len$$$ in an array (arr). And take numbers from $$$len+1$$$ to $$$n$$$ in a set (st). Let's denote $$$left$$$ as the sum remaining i.e. $$$left = s - sum(len)$$$. Now, you can start from last element of array do this while $$$left>0$$$.

    for i from len to 1:
        if(left==0)
            break
        y=arr[i]+left
        if(st.contain(y)):
            arr[i]=y
            break
        else:
            remove greatest element from st say g
            insert arr[i] in st
            left=left - (g-arr[i])
            replace arr[i] with g
    

    Once you have got arr with sum s, you can add remaining elements at other positions. see my submission

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

I can't tell if I've gotten better, or if this round was just easier :/

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

Can someone help me in solving problem E?? I tried by using no from 1 to x-2(where x = r-l+1) whose sum will be equal to sum = (1+2+3+...+x-2), and found two no whose sum was equal to s — sum. I don't know the proof of this method. Someone kindly help.

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

    Here's an example for n = 10, l = 3, r = 7, and s = 21.

    We want to find the numbers that will be in the sum. First we try:

    1 2 3 4 5 / 2 3 4 5 6 / ... 6 7 8 9 10

    Then find the two sums that s is in between.

    Over here, it is 2 3 4 5 6 and 3 4 5 6 7.

    Now, since 3 4 5 6 7 is too large, we need to decrement some of the numbers one by one.

    Since 25 — 21 = 4, we decrement 4 of the numbers, and to ensure no collisions occur we decrement 3, 4, 5, 6.

    So the numbers included in the sum are 2 3 4 5 7.

    Now, just put these numbers so that they occupy positions 3 ... 7.

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

    LOL, ignore.

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

I'm curious what the intended $$$O(n ^ 3)$$$ solution to E was, there is actually a pretty nice solution to that can be made to run in $$$O(n)$$$.

For the subarray $$$[l, r]$$$, if a solution exists, then there always exists a solution of the form:

$$$1, 2, \ldots, i, j, k, k + 1, \ldots n$$$, where $$$i \lt j \lt k$$$.

(We can always shift terms equivalently left / right to reach this for some $$$i$$$ and $$$k$$$ from any valid solution)

Since size is fixed, $$$k$$$ also depends only on $$$i$$$. So we can just iterate over $$$i$$$, calculate the sums of $$$1 \ldots i$$$ and $$$k \ldots n$$$ and then check if the $$$i \lt s - sum \lt k$$$.

I implemented it in $$$O(n ^ 2)$$$ during contest by trivially iterating to calculate sums in $$$O(n)$$$ time for each iteration, but it can be done in $$$O(1)$$$ time per iteration using prefix sums or summation identities.

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

    I did not understand from the statement k also depends on i.Can you please elaborate as to what you have taken as i and c and k

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

      Sorry I meant $$$s$$$, not $$$c$$$, got confused between the characters representing the needed values in different questions.

      So we want to select $$$r - l + 1$$$ values, right?

      So if I know that I'm taking $$$i$$$ values at the start $$$(1, 2, \ldots, i)$$$, and I'm going to select a single number later as $$$j$$$, then I want to select $$$(r - l + 1) - (i + 1)$$$ values for the part $$$(k, k + 1, \ldots, n)$$$. So we can write $$$k$$$ completely in terms of $$$i$$$ as $$$n - ((r - l + 1) - (i + 1))$$$

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

    I didn't read sum of $$$n$$$ over all testcase is $$$500$$$ and took a lot of time to solve in $$$O(nlogn)$$$. About your intended solution $$$O(n^3)$$$ I think we can solved it like $$$0-1$$$ Knapsack. Since sum $$$s<=n(n+1)/2$$$

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

I think Blog should be update Cz it div3 : do not have a point of 1900 or higher in the rating.

it should be: do not have a point of 1600 or higher in the rating.

UPD: It's my mistake :)

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

    no

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

    Thats for trusted vs untrusted standings, not the rated part. Basically what it means is that if someone has peak rating $$$\geq 1900$$$, even if their current rating is $$$\lt 1600$$$, they won't appear in the official standings. Basically its meant to stop people from smurfing to specialist to appear at the top of the official standings of a Div3.

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

Was the intended solution for problem F is DP ?

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

    I also think so. but it's not dp. you_ create new array have size = r-l+1. make array from 1 to r-l+1. add 1 to arr[pos]. _You start with pos = size — 1. if arr[pos] == pos then pos--.

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

    you can prove that in the optimal solution,you will spend minimal days reaching a position then stop and only earn tugriks on that position until you pass c,so iterate over which position you stop at

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

    I don't think so. It can be solved by using Greedy.

    Assume Polycarp last at position i, then for position before i, upgrade to next position as soon as possible will be the best way.

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

    My approach was array day[i] carries the number of days to reach position i and the rem[i] the number of money i start with at position i

    then i get the minimum of days[i] + ceil(( c — rem[i]) /arr[i])

    i really don't know if it consider dp or not

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

can problem E solved by knapsack?

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

    I think so, but the problem is that you should consider amount of taken items, it is fixed

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

    I get AC with greedy

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

    Maybe, but if so its tougher than other solutions in my opinion. I thought about this at first, but the best state I could come up with was $$$dp[\text{current number(1 to n)}][\text{count of taken}][\text{sum of taken}] = 1 \text{ if it is possible}$$$, which is $$$O(n ^ 4)$$$. I can't see any trivial way to reduce the state.

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

      what do you mean by count of taken?

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

      If it's a boolean knapsack it can be optimized using bitsets I guess, so solution might become N^4 / 64

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

        Oh yeah, $$$dp[\text{current}][\text{count}][\text{sum}]$$$ will update $$$dp[\text{current}][\text{count + 1}][\text{sum + current}]$$$, so it can be performed in blocks of 64 elements using an $$$OR$$$ on the bitset. If you consider the extra constant factor of $$$\frac{1}{2}$$$ from sum, this will take $$$\frac{N^4}{128}$$$ or around $$$5 \times 10^8$$$ operations, which is sketchy but possible for 2 seconds I guess. However its obviously not the intended, and based on the editorial I think it was just set to $$$n = 500$$$ to allow less optimized solutions to pass.

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

A great Contest! Although I spent lots of time on problem D&G so that I couldn't finish this. :(

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

Who else ignored the fact that the coordinates for B were for rectangles instead of squares

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

Despair is when you fail to fit a problem in time-limit, only to realize later that the reason in long long int.

TLE: https://mirror.codeforces.com/contest/1512/submission/112546490 AC: https://mirror.codeforces.com/contest/1512/submission/112563646

Only if the time-limit was 3 seconds :(

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

Despair is when you fail to fit a solution in time-limit, only to realize post-contest that the bottleneck is '64-bit int'.

TLE: https://mirror.codeforces.com/contest/1512/submission/112546490

AC: https://mirror.codeforces.com/contest/1512/submission/112563646

Only if the time-limit were 3 seconds :(

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

    Yeah TL was super tight, my first submission with 64 bit integers ran in 1980ms, after replacing it with 32 bit ints it ran in around 1s.

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

The ranklist is cyclically shifting started from Geothermal and it will end to him LOL.

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

Why is everyone's A failing on the top of the standings?

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

EDIT: VALIDATOR DOESN'T CHECK THE 1 DIFFERENT ELEMENT PROPERTY

Whats the hack case on A?

Also how is this idea incorrect:

The different element is either the smallest or the largest element of the array, so we can just check one of them.

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

HackForces

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

Div3-A, there's probably an error in the input checker.

It is known that in this array, all the numbers except one are the same (for example, in the array [4,11,4,4] all numbers except one are equal to 4).

But I have successfully hacked my own submissions(#112521962) in the following case.
1
3
1 2 3

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

    Yup, hacked someone with this case as well. Seems like validator doesn't actually check that property. Should be fixed fairly soon.

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

wtf. Why everyone is getting hacked?

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

I think setters should again write a correct validator in problem A, invalid test cases are showing hacked in A.

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

Uh, are you guys going to fix the invalid test case for A. It's allowing many people to be hacked and lose easy rating.

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

It seems that a wrong validator was written for Problem A.

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

Screenshot-393

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

People are using invalid hacks on problem A by using

1
3
1 2 3 

as input, can anyone please check it

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

Please tell me why my B is wrong!
112540024

[Edit] Thanks lazy_and_slow Thanks a lot for taking the trouble. Appreciated!

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

This is most probably an unecessary comment but please do make sure to not allow incorrect (most probably TLEd out solutions for A to get accepted) upon re-judging

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

Could you help me with problem C please? I uploaded a solution but it failed. In one of the tests it should print 100001101100001 or something like this, but prints -1 instead.

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

    your solution fails on this test

    1
    4 4
    ??00????
    

    after the first iteration, your string will be0?00???0, which is incorrect, since these new zeros must be next to the already existing zeros. to fix this, you can first process the pairs about which it is already obvious which character should be set (pairs 1?, ?1, 0?, ?0), and then the remaining ones (which consist only of ?) 112623883

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

The input validator of Problem G is also wrong

I use this testcase and successful hack

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

This is ridiculous, not only problem A, but problem G is also broken... why does it allow inputs bigger than 10^7?

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

Can anyone also check G validator? I got hacked with RE and it seems kinda strange for me...

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

I got hacked in G for a solution which I believe can't be hacked , hey CF correct your test case validators

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

Hackerforces :(

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

Everyone Problem A XD

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

Could anyone tell me why my submission for D 112517759 was incorrect (hacked)? I'd appreciate it, thanks! UPD: Thanks to LastDance_NotLastOfMe for clarifying! Really appreciate it.

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

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

Lol got to about rank 298 before A and G hacks were fixed. GG.

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

why hacks just clean up and not make them wrong?

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

Can the validator for G please be checked? Thanks

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

Sorry to say but the level of Div3 is getting down day by day. We all saw what happened today. Moreover, problem G is just copied. Original G problem . If you just copied, give some credit to the owner at least. We really enjoyed Div3's that were organized by vovuh. I don't have any problem with the recent authors and I appreciate their hard work, but please maintain the level of Div3, as many of us enjoy giving Div3 more than much other contest.

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

I have been debugging my G since it got hacked.

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

Meanwhile Problem A after today's Div3

Edit — Those who don't know, most of the solutions were hacked by invalid Test Cases. It's fixed now. Thanks Mike ;)

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

So much hack unhack , that much high numbers of submissions on problems , Bug in the Problem A & Codeforces | #WeWantUnrated

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

Hello! Because of mistakes in some validators I reverted all hacks and rejudged solutions. Sorry for the issue. Fortunately, this did not affect the round itself in any way. Not a single participant was hurt!

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

    Will these real successful hacks which is ignored now be run again?

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

    After the rejudge of problem G, my solution got TLE on test 5. On submitting the same code in practice, it got AC, and test 5 ran in 1325 ms. Is there any reason for this inconsistency, because it may have affected other participants too.

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

    My effort of two hours is gone. T_T

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

      Sorry for it. It would be not easy to rejudge hacks properly. But you can uphack all solutions which weren't hacked yet )

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

Is this contest unrated? I haven't received any rating yet

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

my solution got hacked , now will it effect my ratings?

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

Though F is easier than G, for the first 1 1/2 hours during the contest there are more accepted submissions for G than F. Why is that?

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

    The relative length of problem Statement of F vs G probably. Plus I think G wasn't that hard compared to F. The time limit was rather tooooo tight for G.

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

    G is fairly standard if you know the property about sum of divisors (or can obtain it from the property about number of divisors), whereas F actually takes a few minutes to think about the specifics.

    Also 5-6 top participants solved G early in the round, meaning it had more solves than C or D. So several other participants (including me) just switched to trying G after solving B thinking it was significantly easier based on the solve count, which led to a positive feedback loop.

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

My solution for problem g is giving tle .however when i submitted it again it is getting accepted. How could it be possible?

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

Many of problem G accepted solutions got TLE in pretest after rejudge. G needs to rejudge again with proper balance. Thanks.

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

During the contest, my solution for D was Accepted. Now it is a TLE. I am tired of changing my Java solutions to use fast I/O. Are these I/O problems or algorithm problems?

Yes, in this case, seeing 1860 ms (with 2 sec limit), I probably should have changed it, especially because I had time to do it. For instance, my G passed only after I changed the way I printed the output. Nothing else. And then I saw D's time and thought "Screw that, I am not changing it".

Well, it sounds like it is a part of the competition. And yes, I go through this every other contest. For instance, it is a common knowledge that you want to use Long[] instead of Integer[] in Java when they need to be sorted. Why?

I think that having an efficient I/O should never be a goal for these contests. If it is, please remove "slow" languages, so we (the users of said languages) can either skip the contest or try to compete on equal grounds by coding in languages we are not familiar with.

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

    Each participant has the right to choose the language that he likes. Together with all its pros and cons. Yes, Java runs a little slower on average, but it has better static analysis in the IDE. It is quite typical for IT tasks that the tool is chosen for the task. And yes, I'm sure it's not a bad thing that sometimes you encounter purely programming difficulties. Understanding that not all ways to read or write data are the same is helpful. In particular, it is important to understand the basics of buffering. Specifically, in your case, knowing the standard library of the language in which you write is also useful. You are using Arrays.sort, but not reading the documentation. Read it finally.

    This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance

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

      Thanks for the response. All valid points, sorry for venting out.

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

New here, how long does it take for the ratings to be updated ?

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

question g needs to be rejudged. Many of the solutions which are getting tle getting accepted on resubmitting. Even on 1300 ms.

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

    Yes , the code I submitted yesterday got AC . Today it showed TLE on testcase 5. A Few moments later TLE on testcase 3. Submitted the same code just now in Practice — AC. Admins, please look into this.

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

My submission for Problem D passed all the pretests yesterday even though I had used int instead of long long.
Can finally say that the pretests should have been stronger ;)
int
long long

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

    It was obvious in the question that you had to use long long, if n==2e5 and you have permutation of that length, then the sum would more than 2e10 which can't be scored in int, which is basically what you had in the B array

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

      That's not the point. The pretest should obviously have some counter cases for int-solutions.

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

      I agree that it was an avoidable mistake on my part; but the thing is that if I had got an overflow error while the contest was still running, I would have been able to fix it in a moment and wouldn't have got the WA verdict that I got around 12 hours later.
      Had the pretests been a little stronger, I wouldn't have missed out on a point because of something as silly as the mistake that I made...

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

If we could not solve a problem and got 4 wrong submissions than penalty of 40 minutes extra will be added?

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

В пятой задача можно было еще трехмерное дп заюзать, а в четвертой доказать, что только 2 наибольших числа подходят в качестве суммы элементов массива a.

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

I am a newbie . When will the rating be updated ?. This is my first contest. Anyone pls reply

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

Thank you for the round! The tasks were very interesting.

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

I refreshed the official standings table (after the open hacking phase finished), and the rankings are still changing. What is the reason behind this?

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

Hello MikeMirzayanov I just received this message on my mail. Attention!

Your solution 112492155 for the problem 1512B significantly coincides with solutions swagsy/112482200, Sayskar500/112492155. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Sorry to say but I have no contact with the above mentioned user and I can clearly state that we have had the same logic (after visiting the guy's profile and seeing his/her code for question B) but there was no conversation or copy of code in betweeen us. I had received a similar message 5 months ago but that time I was not aware what the warning was about (also the user was different) otherwise I would have reported that time itself. Kindly mark my submissions as correct.

If I had any intensions to copy I would have copied solutions for all queestions. It's not neccessary that if two people have the same intuition/logic for a question they have copied it. Please kindly look into this that it doesn't happen. And I again mention I don't know that guy personally._

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

    Sorry MikeMirzayanov But I don't have any super complex template/snippet in my codes. I prefer writting simple and clean code; which is why there is always a chance that my code may match similar to anyone else's code.

    I didn't wanted to ping you 2 times but please kindly look into other factors while checking for plagiarism. Like if the 2 people had the same code for others questions or not.

    Suppose my code for A and C are not at all similar to that of the user mentioned above. So how did I solve them if I had to ask for solution for B?

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

hey guys, java code for problem D is giving tle in test case 17 although it's linear time complexity, can anybody explain why??

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

    Arrays.sort() internally uses quick sort as a sorting alogrithm thus in worst cases if pivots are not choosen optimally complexity will be O(n^2), so try to use Collections.sort() instead, which uses merge sort.

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

Top round!!!

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

Hello MikeMirzayanov , I just received this message

Your solution 112505064 for the problem 1512D significantly coincides with solutions ritesh1340/112500594, floki/112505064. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I was surprised to get this message, since I did not use ideone.com or any common source. I just used my local text editor (VS Code) and my own code and templates. I don't have any contact with the user ritesh1340. I'm certain this is a complete coincidence and we just happened to think of the same straightforward approach.

Please kindly fix this issue and thank you

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

    +1

    After receiving the message, I actually went to see, if my code was similar to floki's code Or not. I agree to the fact that the codes are really very very similar.

    But, what else would I code? That is such a straight forward approach, and a straight forward implementation. Plus, as far as using ideone Or something similar is concerned,I didn't use it.

    I would request MikeMirzayanov and Stepavly to please look into this

    Thanks

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

Is there anyone who got in Problem F's second test WA because 8891st number differs and then could manage to find the issue and get AC ?

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

    yes you can see my code actually u might be missing the case where you dont have to earn at a particular day and the balance you have is sufficient to move to next position

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

[Deleted]

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

For problem G: My submission using long long: https://mirror.codeforces.com/contest/1512/submission/112652041

My submission using int: https://mirror.codeforces.com/contest/1512/submission/112651472

Using int is taking noticeably less time than using long long.

Can anyone explain, Why long long is slower than int?

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

I don't know why I got TLE for nlog(n) submission in D.

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

Please consider to rejudge my solution of problem G

Last 713 div3

Same solution one is ac and one is tle

TLE Solution : https://mirror.codeforces.com/contest/1512/submission/112528244

Accepted Solution : https://mirror.codeforces.com/contest/1512/submission/112621917

When contest is running my problem got ac verdict all the 9 test case

And i have a screen shot also

And when contest and rejudge the

All solution g that time my solution got tle

In 7th test case, . But contest time

Show all the 9 test case ac

And same solution i submit now

It's show ac verdict

Please rejudge my solution MikeMirzayanov

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

This Div.3 is too easy...Hope a harder contest!