vovuh's blog

By vovuh, 6 years 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 awoo, fcspartakm, Neon, BledDest, Roms and vovuh. Great thanks to our coordinator cdkrot 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

| Write comment?
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Another wonderful time for Chinese users.

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

thanks codeforce for another round.

»
6 years 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.

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

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

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

A bad time for indian students :(

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 years 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 ....

»
6 years 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.

»
6 years ago, # |
  Vote: I like it +60 Vote: I do not like it

For a moment I thought this was an educational round announcement

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really?! 12:35 IRDT

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Great time for Chinese CF users.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wonderful time for Chinese users. So I am coming.

»
6 years 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.

  • »
    »
    6 years 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

»
6 years 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 :)

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the editorial is just after contest end.

WoW!

»
6 years 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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why TLE using dp in problem D?

  • »
    »
    6 years 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.

»
6 years 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

»
6 years 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

»
6 years 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

  • »
    »
    6 years 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

    :

    • »
      »
      »
      6 years 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 :

      • »
        »
        »
        »
        6 years 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)

        • »
          »
          »
          »
          »
          6 years 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 :)

  • »
    »
    6 years 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://mirror.codeforces.com/contest/1042/submission/42975128

  • »
    »
    6 years 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

»
6 years 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

»
6 years 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.

  • »
    »
    6 years 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 .

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

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

  • »
    »
    6 years 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.

»
6 years 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.

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

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

»
6 years 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 ?