Vovuh's blog

By Vovuh, 5 weeks ago, translation, In English,

Hello, Codeforces!

Codeforces Round #510 (Div. 2) will start at Sep/17/2018 11:05 (Moscow time). The round will be rated for Div. 2 contestants (participants with the rating below 2100). Div. 1 participants can take a part out of competition as usual.

The round will be rated for the Div. 2 participants (for everybody with rating less than 2100). The statements will be available in Russian and English languages.

This round is held on the tasks of the school stage All-Russian Olympiad of Informatics 2018/2019 year in city Saratov. The problems were prepared by PikMike, fcspartakm, Ne0n25, BledDest, Ajosteen and Vovuh. Great thanks to our coordinator _kun_ for the help with the round preparation! I also would like to thank our testers DavidDenisov, PrianishnikovaRina, Decibit and Vshining.

You will be given six problems and two hours to solve them. Scoring system will be announced traditionally closer to round start. :)

UPD: The scoring distribution is 500-1000-1500-2000-2250-2750.

UPD2: Editorial

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

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

Another wonderful time for Chinese users.

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

thanks codeforce for another round.

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

was good

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

Why so early?It's like choose what is more important some kind of study or cf.

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

Well, where is the thanks to MikeMirzayanov and polygon platform XD

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

A bad time for indian students :(

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

A bad time for Chinese student who need to study mathematics.

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

thank you for the back to back contest ...a contest in afternoon for Indian users after a long time ...will have to bunk class to give ....

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

Its very good to have variety in the hours that contests start so as everybody can find a time that fits to their standards. I hope that codeforces will continue this logic in the future as well.

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

For a moment I thought this was an educational round announcement

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

Really?! 12:35 IRDT

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

Forgot to Thanks mikemirzayanov for the wonderful codeforces and polygon platform.

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

Indians on cf- Good luck, have fun. Wish you all high rating.

Indians in real life — "thank you, come again" ; "i am going to drink cow piss with some curry"

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

well, i am coming!!!

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

Great time for Chinese CF users.

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

Wonderful time for Chinese users. So I am coming.

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

This was nice contest

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

Hack for A.
3 1
1000 1 1
Answer 1000 1001.

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

    You meant: "Answer 1000 1001"?

    P/s: Main comment edited, nevermind :D

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

you can simplify the problem C to this :

given a sequence of none negative numbers(n-th >= 0) get the maximum product.
so you will multiply the positive integers. then multiply the 0's and delete the last occurrence of the zeros
how to get this ?
if you have an odd number of negative numbers , convert the maximum negative number to zero , then take the absolute value for all the sequence.

could any one help me to understand the task D ? thanks in advance :)

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

    Consider the sum of segment [i,j] less than t is equals to prefix[i] - prefix[j-1] < t.

    For every prefix[i](1<=i<=n) calculate the number of j(0 <=j <i ) which satisfy prefix[j] > prefix[i] - t, and this number is the numbers of segments which endpoint is i and satisfy sum less than t.

    You can use the BIT to calculate the number of j (0<=j<i) which satisfy prefix[j]<=prefix[i]-t easily.Then what you need to calculate is i - the number of j . Sorry for my poor english.

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

the editorial is just after contest end.

WoW!

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

Such Tight limit constraints in Que-3 ,making it almost impossible to pass in pypy2/python2

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

why TLE using dp in problem D?

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

    For each i in [2..n] you iterate n - i times.

    The number of operations is

    Your solution is O(n2), that's why it gives TLE.

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

Thanks for posting editorial so quick.

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

¯_(ツ)_/¯

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

What is test 22 structure like on problem D?

P.S I found out the problem, try this test: 5 6 5 -5 10 -5 10

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

In problem C, there are no cases with only zeros and ones. This DP solution should fail: 42985876

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

~ B

~ N^3 (MAX_N = 1000)

~ ACCEPTED 1 SEC

~ Who can explain WHY???

42983122

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

    this is weird !

    i tried many tests to get the answer after 2s

    but this is the maximum time i got on the custom test!

    test case (long text)

    Test

    :

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

      my best : 1600ms, test : n = 1000 1 ABC, 1 ABC....

      look at it :

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

        yes, so is this the normal run time for 109 iterations ? or this code iterate less than 109 ?

        it's even doesn't make any break / continue inside any loop ! it's exact O(n3)

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

          Yes, stupid solve!

          Yes, more 1e9 iterations!

          So i wanted to hack him(((

          Result = -100 points :)

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

    Nowadays computers are fast enough to run 10^9 iterations in around 1s. Look at my code which runs around N^3/6 iterations in 234ms. http://codeforces.com/contest/1042/submission/42975128

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

    The following test case takes 2230ms on Codeforces (GNU G++14): 1000 AB and randomly appending C.

    Random Cs make a worse case than 1000 strings of ABC, most probably because of branch prediction.

    Here's the code with the case generated instead of being read: https://ideone.com/JRyp7j

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

The first time with me that the predictor does not predict the same rating change,why?

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

Does CF Rating predictor gives completely wrong rating predictions for today's contest ? Because it seems to me it worked perfectly well in yesterdays contest

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

I'm getting the message "Ooops! Something has broken down in Codeforces" when I try to open problem C, does anyone else get this message? What's going on?

Edit: The editorial for problem C is also not loading, probably the problem's package is somehow broken.

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

    Yes I am also facing this problem , But i can submit it through problem id .

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

    I'm getting that too!!! What's going on?

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

    No idea, to be honest. The package itself seems ok, I rebuilt it just to be sure, nothing got fixed. And the previous revision was created like 3-4 hours ago, something broke after that. Just wait a bit, sorry, I have no better advice for now.

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

It is better to put some difficult problems. This round is extremely easy for me.

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

    Easy? Come to Codeforces Round #510 (Div. 1)!

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

in task E in Div 2, what is the answer on test: 1 3 1 1 2 1 3 ?