Stepavly's blog

By Stepavly, 5 weeks 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://codeforces.com/blog/entry/89535

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it -32 Vote: I do not like it

UPD : sorry

»
5 weeks 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 :)

»
5 weeks 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

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Is it rated?

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

122

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

OK thank You

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Finally a Div 3 contest on weekend! Thanks for making it a reality :-)

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

Plz change time since there is an IPL match.

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

I think Everyone Love to see it :)

Captu1re

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

Yep, my mistake, Sorry!

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

    CodeJam is runnig.will be finish in 10 min. then how The timing of Google Codejam clashes with this content?????

»
5 weeks 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

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

Good luck to all

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

may the force be with you

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

Old but still best......

»
5 weeks 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)

»
5 weeks 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

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

aboba

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

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

  • »
    »
    5 weeks 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!

  • »
    »
    5 weeks 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)

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

Thanks for the great round!

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

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

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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--

  • »
    »
    5 weeks 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

»
5 weeks 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 :/

»
5 weeks ago, # |
  Vote: I like it -24 Vote: I do not like it
»
5 weeks 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.

  • »
    »
    5 weeks 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.

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

      That's what i wrote. But I got the second example wrong. I want to know why.

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

    LOL, ignore.

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

why my code is giving TLE for problem G?

»
5 weeks 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.

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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))$$$

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
  • »
    »
    5 weeks 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$$$

»
5 weeks 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 :)

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

    no

  • »
    »
    5 weeks 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.

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

Was the intended solution for problem F is DP ?

  • »
    »
    5 weeks 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--.

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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.

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

        my sol is the same as editorial

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

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

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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

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

    yup. You can calculate the number of days required to reach every position and tugriks left after reaching every position. Then calculate the number of days required for each position and take the minimum. You can also do it in the single loop. I made a very silly mistake in this :(

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

Thank you for the effort you put into the contest.

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

contest ended at 10:05 ist, code submitted and ac in one go at 10:07 ist. Life.

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

Contest was easy but a lot of code was there to write .

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

can problem E solved by knapsack?

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

    cant store an array of 500 as a dpstate ? or you meant problem F ?

  • »
    »
    5 weeks 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

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

    I get AC with greedy

  • »
    »
    5 weeks 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.

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

      what do you mean by count of taken?

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

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

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks 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.

»
5 weeks 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. :(

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

Did anyone used bruteforce approach with right angle property in problem 2?

»
5 weeks 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

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

    Every square is a rectangle!

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

      Every rectangle is not a square!

      • »
        »
        »
        »
        5 weeks 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?

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

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

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

            Maybe I didnot get what you were trying to say! just ignore my messages in that case :D

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

          not all the cases allow him to make square

»
5 weeks 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://codeforces.com/contest/1512/submission/112546490

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

Only if the time-limit were 3 seconds :(

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

MikeMirzayanov Can you please provide the whole second testcase for problem B , can't seem to find my mistake

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

    Line 91 should be poin1 = make_pair(first_x,0); instead of poin1 = make_pair(0,first_x);

    Currently can't submit this, but you can check after the hacking phase gets over.

    Let me know if the error persists!

»
5 weeks 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.

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

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

»
5 weeks 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.

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

HackForces

»
5 weeks 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

  • »
    »
    5 weeks 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
    
»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

wtf. Why everyone is getting hacked?

»
5 weeks 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.

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

MikeMirzayanov Please fix all hacks for A, Thanks!

»
5 weeks 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.

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

    I mean you just hack 113 solutions with it!

  • »
    »
    5 weeks 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.

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

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

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

Screenshot-393

Indeed
»
5 weeks 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

»
5 weeks 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!

  • »
    »
    5 weeks 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

»
5 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

wrong answer Not a rectangle (1) (test case 35)
Could someone please provide that

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

Everyone's Problem A XDDDD

»
5 weeks 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

»
5 weeks 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.

  • »
    »
    4 weeks 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

»
5 weeks 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
»
5 weeks 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?

»
5 weeks 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...

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

Can anyone help me why my code is failing at Test 2 (Case-60) for problem D. Link-Solution

Upd: Found the mistake and got AC.

»
5 weeks 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

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

Hackerforces :(

  • »
    »
    5 weeks 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 :):)

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

Everyone Problem A XD

»
5 weeks 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 you_dont_know_me for clarifying! Really appreciate it.

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

»
5 weeks 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.

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

Can the validator for G please be checked? Thanks

»
5 weeks 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.

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

I have been debugging my G since it got hacked.

»
5 weeks 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 ;)

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

Could anyone tell me why my submission for D 112574846 is showing incorrect output for test case 1 only??

»
5 weeks 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

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

    Why? Because you couldn't perform well enough?

»
5 weeks 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!

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

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

  • »
    »
    5 weeks 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.

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

      :")

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

      Same happens to me.

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks 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.

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

    My effort of two hours is gone. T_T

    • »
      »
      »
      4 weeks 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 )

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 3   Vote: I like it -13 Vote: I do not like it

        Sorry for bothering you Mike sir.

        But my query regarding a plagiarism check (which I had posted about an hour ago) is still unanswered even though the ratings are out.

        It would be great if the team is considering checking the claim and my message once again.

        Thanks

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

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

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

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

»
5 weeks 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?

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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.

»
5 weeks 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?

»
5 weeks 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.

»
5 weeks 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.

  • »
    »
    4 weeks 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

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

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

»
4 weeks 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 ?

»
4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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.

    • »
      »
      »
      4 weeks 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...

»
4 weeks 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?

»
4 weeks 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

»
4 weeks 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?

»
4 weeks 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://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 weeks 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?

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

      Doesn't seems like my query will be looked into :(

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

        MikeMirzayanov and Stepavly It has been 4 days since I posted the comment and still no response or update whether the team has considered reviewing the claim or not.

        I again insist that I have no direct connection with the above mentioned user.

        My solutions are very simple and easy to understand which might be a reason that my solution might have coincided with someone else's code.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I participate for the first time in contest. So can anyone help me in whether my "Unrated" status changes with a rating .

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

    After giving the contest your ratings will be updated 1 day after the contest gets over.

    NOTE : May take more or less time depending on factors like : no. of participants, hacks, buggy hacks(like that happened in this one) ...etc.

»
4 weeks 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??

  • »
    »
    4 weeks 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.

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

    Same thing happened with me too. I think Arrays.sort uses dual-pivot quicksort algorithm for primitive arrays which is not stable. Sometimes its time complexity degrades to O(n^2) for particular data sets.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Top round!!!

»
4 weeks 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://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 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Codeforces round 713 div 3, I got a message saying that my submission for problem B coincides with another person. The reason behind this is that I solved all my problems on CodeChef IDE but for problem B it was throwing some problems. don't know the reason why. So I tried running my code on Ideone in the default setting and someone copied my code and I was not aware of that. You can check my code for Problem A it is unique. The approach is unique the variables are unique. So it was only for Problem B that this mistake happened.

sorry for my mistake. I'll make sure it never happens again.

»
4 weeks 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 ?

  • »
    »
    4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For codeforces round 713 div 3, I got a message saying that my submission for problem c coincide with some other people.The reason behind this is that I solved all my problems on my local ide sublime text but for problem c my local ide gives wrong output don't know the reason why. So I tried running my code on ideone in default setting and someone copied my code and I was not aware about that. sorry for my mistake. It'll never happen again. Please look into it MikeMirzayanov

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

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

My submission using int: https://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 weeks 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.

»
4 weeks 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://codeforces.com/contest/1512/submission/112528244

Accepted Solution : https://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 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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