Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Vovuh's blog

By Vovuh, 3 months 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  

»
3 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Another wonderful time for Chinese users.

»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

thanks codeforce for another round.

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

was good

»
3 months 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.

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

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

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

A bad time for indian students :(

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
3 months 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 ....

»
3 months 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.

»
3 months ago, # |
  Vote: I like it +60 Vote: I do not like it

For a moment I thought this was an educational round announcement

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Really?! 12:35 IRDT

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months 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"

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

well, i am coming!!!

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Great time for Chinese CF users.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wonderful time for Chinese users. So I am coming.

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

This was nice contest

»
3 months 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.

  • »
    »
    3 months 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

»
3 months 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 :)

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the editorial is just after contest end.

WoW!

»
3 months 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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why TLE using dp in problem D?

  • »
    »
    3 months 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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for posting editorial so quick.

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

¯_(ツ)_/¯

»
3 months 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

»
3 months 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

»
3 months 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

  • »
    »
    3 months 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

    :

    • »
      »
      »
      3 months 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 :

      • »
        »
        »
        »
        3 months 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)

        • »
          »
          »
          »
          »
          3 months 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 :)

  • »
    »
    3 months 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

  • »
    »
    3 months 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

»
3 months 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?

»
3 months 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

»
3 months 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.

  • »
    »
    3 months 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 .

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months 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.

»
3 months 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.

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

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

»
2 months 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 ?