Stepavly's blog

Codeforces Round #713 (Div. 3)
By Stepavly, 4 years ago, translation, In English

Hello, Codeforces!

<almost-copy-pasted-part>

Hello! Codeforces Round #713 (Div. 3) will start at Apr/10/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended 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 7 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 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.

The problems for this round were invented by MikeMirzayanov, Supermagzzz, Stepavly and sodafago.

Thanks Gassa, darkkcyan, bfs.07, Tzak, songsinger, Mukundan314, iankury, drunya, sodafago, ChOmPs, Programmer, Khairy, IITianUG, Rox for helping with testing the round!

Thanks to MikeMirzayanov for platforms and coordination of our work. Good luck!

</almost-copy-pasted-part>

Editorial: https://mirror.codeforces.com/blog/entry/89535

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

Comments Comments (172)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it -32 Vote: I do not like it

UPD : sorry

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

    And why exactly you gave this guy so many negative reviews?

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

      This is the third time I've seen the same meme in announcement blogs

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

        Yeah I have seen it before too

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

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

UPD : Now it is fine for everyone :)

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

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

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

122

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

I think Everyone Love to see it :)

Captu1re

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

Yep, my mistake, Sorry!

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

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

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

Good luck to all

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -28 Vote: I do not like it
→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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)

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

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

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

aboba

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

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

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

    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!

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

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

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

Thanks for the great round!

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

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

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

    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

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

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

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

    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

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

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

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

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.

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

    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.

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

    LOL, ignore.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

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.

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

    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

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

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

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

    E was apparently available on stackoverflow https://stackoverflow.com/questions/46296588/distinct-n-numbers-so-that-sum-equals-to-n

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

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

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

    no

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

    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.

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

Was the intended solution for problem F is DP ?

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

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

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

    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

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

      hey, can you please share your solution? I thought almost the same but guess I missed some corner case.

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

        my sol is the same as editorial

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

          Funny thing, i thought that but couldnt get it to work

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

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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

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

can problem E solved by knapsack?

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

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

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

    I get AC with greedy

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

    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.

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

      what do you mean by count of taken?

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

        He meant amount of numbers used, cuz it should be always fixed

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

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        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.

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

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

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

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

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

    Every square is a rectangle!

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

      Every rectangle is not a square!

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

        So if your solutions is for squares instead of rectangles , it should still work ryt?

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

          No. It only works for all squares, not all rectangles are squares

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

          not all the cases allow him to make square

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

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

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

    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.

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

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

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

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

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

    Invalid inputs are passing as hacks. I think the validator doesn't have a check for 1 different element.

    I submitted

    1
3
1 1 1

    and got successful hack.

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

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.

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

HackForces

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

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

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

    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
    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

wtf. Why everyone is getting hacked?

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

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

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

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.

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

    we are not going to lose rating lmao. I don't know if you are delusioned or you are joking it's most probably the latter.

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

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

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

Screenshot-393

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

People are using invalid hacks on problem A by using

1
3
1 2 3

as input, can anyone please check it

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

Please tell me why my B is wrong!
112540024

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

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

    you have made a mistake in your first_y and second_y points in the code. I corrected it (commented on the line with mistake). 112571015

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

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

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

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.

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

    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

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

The input validator of Problem G is also wrong

I use this testcase and successful hack

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

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

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

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

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

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

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

Hackerforces :(

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

    Today people like me (Newbie) tried to hack GEOTHERMAL(I.G.M) solutons :):)

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

Everyone Problem A XD

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

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.

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

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

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

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

Can the validator for G please be checked? Thanks

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

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.

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

I have been debugging my G since it got hacked.

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

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

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

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

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

    Why? Because you couldn't perform well enough?

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

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!

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

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

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

    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.

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

      Same happens to me.

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

      Same for me my solution passed in 1650 ms in the contest but after rejudge it TLE on the 1st test. On submitting the same code it got accepted now.

      TLE : 112502445, Accepted : 112582502

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

        The same happened with my code. It's giving tle on 3rd test case. when I submitted it again it got ac.

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

    My effort of two hours is gone. T_T

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

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

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

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

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

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

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

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?

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

    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.

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

    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.

    → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +7 Vote: I do not like it

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

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

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

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

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.

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

    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

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

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

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

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

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

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

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

    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.

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

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

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

    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

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

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

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

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

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

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

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

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

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

    it should be updated very soon. you can see your rating changes by cf predictor extension

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

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

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    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?

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

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

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

    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.

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

Top round!!!

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

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

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

    +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

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

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 ?

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

    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

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

[Deleted]

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

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?

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

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

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

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

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

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

→ Reply