Sereja's blog

By Sereja, 11 years ago, translation, In English

Hello everyone!

Codeforces Round #182 will take place on Sunday, May 5th at 19:30 MSK. This is my sixth Codeforces round and I hope not the last.

I'd like to thank Gerald and sdya for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Because of technical issue the start of the contest was unsuccessful. Sorry about it. The contest will be UNRATED.

Tutorial.

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

| Write comment?
»
11 years ago, # |
  Vote: I like it -109 Vote: I do not like it

求轻虐!!!!!!

»
11 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Any info. about the score calculating rules? As usual?

»
11 years ago, # |
  Vote: I like it -17 Vote: I do not like it

I believe this will be a very level of the game!

»
11 years ago, # |
  Vote: I like it -15 Vote: I do not like it

all your round announcement posts look like the same :D

»
11 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Can you tell me what about the score ? dynamic or 500-1500-1500-2000-2500 ?

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

Good look to everyone! :)

»
11 years ago, # |
  Vote: I like it +33 Vote: I do not like it

hope my friends and i can reach blue= =

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

It is easter in the ortodoxal world. I hope a wonder happen and everything with the contest will be OK.

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

looks like the contest is delayed 10 minutes

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

    May be system is experiencing some load. Request are getting timed out.

»
11 years ago, # |
  Vote: I like it +27 Vote: I do not like it

hope today's sever will be stable

»
11 years ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

Yestody, GCJ, Have your score arrived 22.

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

Hope Codeforces can fixt it .. the server cant breathe right nw :O

»
11 years ago, # |
  Vote: I like it +36 Vote: I do not like it

WTF IS THAT?!

The contest opened while the server was down and some people managed to get the problem statements!

THIS IS COMPLETELY UNFAIR!!

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

    How you know that ?

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

      One of my friends already sent me the statement for problem A

      Problem A. Eugeny and Array

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -13 Vote: I do not like it

      , Problem A. Eugeny and Array Input le: stdin Output le: stdout Time limit: 2 seconds Memory limit: 256 megabytes Eugeny has array a = a1; a2; : : : ; an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:

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

    What the....

    If this is true, the contest need to be cancelled definitely. Please announce about the situation and stop wasting competitor's time.

»
11 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Will the contest be rated? At some moment, contest once started.

»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Are you sure, you want to continue this contest ?

»
11 years ago, # |
  Vote: I like it +116 Vote: I do not like it

Sereja strongly recommends you to read ALL the problems. I strongly recommend you to open ALL the problems :))

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

its getting late 35 min wasted time yet.

»
11 years ago, # |
  Vote: I like it -9 Vote: I do not like it

it's really unbearable !!!!!!!1

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

Contest gonna start today???

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

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

»
11 years ago, # |
  Vote: I like it +33 Vote: I do not like it

"Oops! This link appears to be broken"

"502 Bad Gateway"

"504 Gateway Time-out"

"Sorry, the server is too busy at the moment. Please try again later."

For 15 minutes these were the only problems I could see!

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

Hope system can be fixed as soon as possible. It's hard to not get the request of "502 bad gateway"...

»
11 years ago, # |
  Vote: I like it +28 Vote: I do not like it

If this round will be unrated, please tell us before the contest end.

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

**Server Problem !!!!** **Bad Gateway** Hope it'll be OK soon... :/

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

Already 00:05 ! (East Asia)

»
11 years ago, # |
  Vote: I like it +39 Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

The server problems are getting really annoying!!! at least could someone explain why the server is down lately??

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

LOL, they all had the problem statements and the code ready before the contest begins

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

    good that the contest is unrated.

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

thank you for letting us know that the contest will be unrated.

»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

waiting 35 minutes... and... unrated...

»
11 years ago, # |
  Vote: I like it +119 Vote: I do not like it

Sorry about the contest start. It was my fault: the main reason is — it was a non-production copy of Codeforces deployed before the contest (some experimental code + experimantal JVM settings + enabled profiler). Somehow the production copy was unable to start because of many requests :( It was started after some time, but it was passed about 0.5 hour and it was a moment of contests was started (so some users were read the problems).

The contest is unrated. I'm sorry about it. I hope you will like nice problems by Sereja.

===

Приношу свои извинения в связи со срывом старта контеста. Это по моей вине, основная причина — был запущен не-production вариант Codeforces (с некоторым экспериментальным кодом + с экспериментальными опциями в JVM + под профайлером). Почему-то production-сборка не смогла сразу запуститься под написком потока запросов :( Когда она была запущена (примерно через полчаса), был момент когда контест был доступен и некоторые из вас уже прочли задачи.

Контест будет нерейтинговым. Еще раз приношу извинения. Я надеюсь, вам понравятся красивые задачи от Sereja и вы получите удовольствие от их решения.

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +73 Vote: I do not like it

    ... The author is innocent ... We shouldn't blame on him. ... Sereja, Thanks for your work and problems.

    PS: I wonder on this particular issue, does Codeforces will pay for the problemset? Does the author will write the Editorial as well as it been rated?

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

Problem C, Do the n elements for which we can change the sign needs to be consecutive ?

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

    No. It's not necessary for n elements to be consecutive!

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

Something is definitely wrong with new Python 3 interpreter. Sorry for spoiling before the end of the contest, but anyway it's unrated.

So I feel I'm clever enough to make a solution for problem A, but it has TL on test 11. I do some stupid things sometimes so I checked here: http://codeforces.com/contest/302/status and everyone fails on test #11 (no one solved it using python 3). The problem could be in reading input data, but it's not as big (10**5).

Also after direct translating my code to python 2 it was accepted, so I think something has to be repaired here.

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

    It is true (at least for me) that CPython 3 is sometimes slower than CPython 2.

    I wonder if Codeforces could implement support for PyPy?

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

      Python 3 can be slower, but if it fails on this example what will be on examples with bigger inputs? I waited py3 really for a long a time, but in my opinion it's better to disable it in this state.

      It would be good if admins add PyPy but the problem is that it's implemented, again, only for python 2

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

    I tried Div2 A and B with Go language but both solutions got TLE in pretests. (my solutions: 3675888, 3676731) I feel more optimization is needed for those new languages.

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

      It's strange that solution both in python 3 and Go fail exactly on test #11. I hardly believe they are equally slow.

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

      I tried to run it localy. The result is "time consumed: 2.81 sec". Note, my laptop is much faster than judging machines. It seems IO in Go is a bottleneck.

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

        I also ran it locally and it took 8.1 seconds... looks like the judge was correct and I should use faster IO functions if any. Thank you for pointing it out.

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

    Right, Python 3 is slower than Python 2 in many cases. For example, on my laptop (i7, much faster than judging machines) you solutions work (on the test 11):

    • Python 2: 0.65s,
    • Python 3: 2s,

    Also PyPy works not faster than Python 2:

    • PyPy: 1s.

    "... so I think something has to be repaired here ..."

    I believe Python team should "repair" Python 3 to work faster. On the other hand you should know and understand pros and cons of the language.

    Another conclusion that PyPy is not a silver bullet, this problem shows again that it doesn't work faster than CPython 2.

»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

no need to complain about unrated contest, just practice in this contest, after all, this contest isn't offering any prize

the important thing is you doing well in that kind of contest, and this codeforces round is one thing to do to achieve that, higher rating doesnt mean always win

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Div 1 C / Div 2 E Yaroslav and Algorithm is very interesting! Anyway thanks for the great questions by the author!

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

What a pity! It was a very interesting problem set. Thanks Sereja

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

The problems are so good. Thanks Sereja, sdya and Gerald. What was the 3rd pretest of Problem C!!!???

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

    I think you understood the task of problem incorrect, read again, sorry for poor English.

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

    comment deleted

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

    input:

    3

    1 2 2 2 2

    output:

    7

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

    Did you figure out how the problem works? I'm interpreting the problem as in a single operation you MUST change the sign of n numbers. In pretest 3, however, the solution would require changing the sign of four numbers while n=3, which I thought would be impossible...

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

      It is possible using two operations:

      -959 -542 -669 -513 160
      -959 -542 669 513 -160
      959 542 669 513 160
      
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh wow, thanks. Wasn't thinking like that for some reason.

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

O(m*n) solutions accepted in problem B Div2.
Edit
My apologies, i misread the solutions. Is O(n+m) complexity, because they keep the last position found.

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

    read the constraints again

    (It is guaranteed that vi < vi + 1)

    solutions are O(n+m)

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

      The worst test case is:
      n = 10^5
      m = 10^5
      ci = ti = 1 for 1 <= i <= n
      vi = i for 1 <= i <= m

      Ops! you are right, i misread solutions... they keep the last position found.

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

    you might be dont know two pointers :)

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

      Ops! you are right, i misread solutions... they keep the last position found.

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

Thanks for brilliant contest. It could be a great rated contest if CF didn't crash, but as an unrated contest it was outstanding. GL & HF!

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

too slow system test :/

I'm waiting to add problems to practice.

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Very nice problems!Especially problem C in div1!Thanks to sereja!

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

Weak test cases for problem B in DIV2

O(m*n) solutions pass the system test! m,n <= 10^5 !!


Okay I was wrong (It is guaranteed that vi < vi + 1) solutions are O(n+m)

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

    show me the code. i think it's O(m+n) solution, not O(m*n), because variable j can not decrease:)

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

trying to figure out div1 problem D. i believe the number of divisors of a number n is no greater than 2*sqrt(n), is there a tighter bound?

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

    Look at it as the number of multiples in the range [1,n]. Then you get:

    n/1 + n/2 + n/3 + ... + n/n

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

    Sum of numbers of divisors for numbers not exceeding N is .

    Also, number of divisors of N is o(Nε) for every ε > 0.

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

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

    Absolutely! except for the last thing :D

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

Hi there, a quick question.

In Div2 D/Div1 B, what should the output of the following test case be?

3 1000
2000
0 0
0 1
0 2

Should it be 1000? Because my program outputs 0 and passed system test. Thanks! :)

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

    a_i<=1000

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

      oh, I missed that one. Thanks, Sereja! I really enjoyed your problems :)

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Would you mind returning pagination on the 'Contests' page to its normal state (slightly more than 4 contests per page)?

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

So sorry to hear that...:(

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

The third topic what is thinking?

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

In the problem "Yaroslav and Time", I define INF as 20000005, and get "pretest passed". However, "wrong answer on case 51" in rejudging. So Sad that INF shall be 2*20000005 or bigger. PS: If dijkstra algorithm is used in this problem, it's okay. But if dp is used, this test case should be concered: 5 1000 1000 1000 1000 0 0 0 1 1 1 2 1 2 0 What I mean is that we shouldn't just apply dp in just (sx,sy) to (ex, ey), but the whole (-100,-100) to (100,100).

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

Can someone tell me solution of problem C div 2

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

    The problem tag is dp and math. However, I solve it in a more complicated way — bfs and greedy. First, I use bfs to get all the possible number of multiplying -1. For example, for n = 2, all the possible number are {0,2}. That's to say, I can multiply zero or two numbers in the array by -1. Then, sort the sequence and apply greedy algorithm. If I can make all the numbers positive, then do it. Else I make as more as I can. Be careful of occurrences of 0.

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

    Here's another solution:

    If there are any zeros inside the array, then you can ALWAYS make them all positive.

    If you have n is an odd number, then you can ALWAYS make them all positive.

    If you have n is an even number and there is an even number of negatives, then you can ALWAYS make them all positive. Else, you can ALWAYS make all but one of them positive.

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

      Here is a rigorous proof of the "always"es frznlich said.

      First, note that if n is odd, we can change any single number. To see this, take the number x that we want to change, and n more numbers a1, a2, ..., an. We do an operation to each of these: (x, a2, a3, ..., an), (x, a1, a3, a4, ..., an), ..., (x, a1, a2, ..., an - 1) -- basically every combination possible that takes x and n - 1 of the ai's. We can see that x belongs to n (an odd number) operations and hence changes sign, while every ai belongs to n - 1 (an even number) operations so doesn't change sign.

      If n is even, we cannot change a single number: The number of numbers we change is even (some number times n which is even), and two changes equal null, so the parity of number of numbers we change is an invariant. So it will stay even. However, we can change two numbers. If we want to change x, y, take numbers a1, a2, ..., an - 1 and perform the operations (x, a1, a2, ..., an - 1), (y, a1, a2, ..., an - 1).

      This means we can change all negative numbers to positive except probably one, and this "probably one" only occurs when n is even and there are an odd number of negative numbers.

      So what we should do is to determine whether the above condition occurs. Besides, we will also find out the sum of the absolute values of the numbers and to figure out the number with the least absolute value, which we will "sacrifice" as the single negative number if there is any.

      So our approach is this:

      Loop over all numbers. Compute the number of negative numbers in the input and call it neg, the sum of the absolute values of all numbers sum, and the minimum absolute value of all numbers min. If n is even and neg is odd, output sum - 2min, otherwise output sum.

      EDIT: Removed double post (phone acts up at times), useless statement to find the largest number, and useless assumption that zero is negative.

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

    A solution more suitable to a contest, however, is: notice the bound N <= 100 and do BFS on how many negative numbers there could be, since if you change x negative numbers and N-x positive ones in one step, then there will be N-2x more negative numbers (special case: if there's a zero, it's clear that they can all be made non-negative). You don't need to think about all possible cases, just use a simple algorithm to do that for you.

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

Can someone tell me solution of problem C div 1? thanks!

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

    One approach is this (works for any number):

    1. Place ? after the first occurrence of the smallest digit in the number.
    2. Move ? to the end of the number.
    3. If the last digit of the number is 0..8, increase it, remove ? and stop. Otherwise replace ? with ??.
    4. So long as the digit before ?? is 9, replace it with 0 and move ?? one step left.
    5. If there is another digit before ??, increase it, remove ?? and stop.
    6. If there is no digit before ??, replace it with 1 and stop.

    For example, the number 6299:

    6299, 62?99, 629?9, 6299?, 6299??, 629??0, 62??00, 6300

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

    Just output the following:

    ??0>>0??
    ??1>>1??
    ??2>>2??
    ??3>>3??
    ??4>>4??
    ??5>>5??
    ??6>>6??
    ??7>>7??
    ??8>>8??
    ??9>>9??
    ??>>?
    0?<>1
    1?<>2
    2?<>3
    3?<>4
    4?<>5
    5?<>6
    6?<>7
    7?<>8
    8?<>9
    9?>>?0
    ?<>1
    0>>??0
    1>>??1
    2>>??2
    3>>??3
    4>>??4
    5>>??5
    6>>??6
    7>>??7
    8>>??8
    9>>??9
    

    The above is composed of five parts: End marker movers of 10 commands, end marker converter of 1 command, converter processes of 10 commands, converter finalization of 1 command, and end marker initializations of 10 commands.

    At first, the string doesn't contain any question mark, so some of the end marker initialization commands (d>>??d) is encountered. There will be some double question mark, called end marker, inserted in the string.

    Now, some of the end marker mover commands (??d>>d??) will be encountered. This basically moves the end marker one step to the right. As long as this end marker isn't at the end yet, the end marker will be constantly moved, so the end marker will eventually reach the end of the string. At the worst case, the end marker begins in the front of a 25-digit string, taking 25 iterations.

    Next, the end marker converter (??>>?) is found, and the end marker becomes a converter sign (?). This converter sign's job is to add the digit exactly before it.

    Next, some of the converter process commands (d?<>d) will be encountered, which changes the digit in front of the converter sign. If it's not 9, the addition will not cause any carry, so we're done. Otherwise, the special 9?>>?0 command is encountered, which marks that we need to carry and so we need to add 1 to the previous (more significant) digit. At the worst case, the converter processes need to go all the way to the front with the number 1025 - 1 = 9999999999999999999999999, which takes 25 iterations.

    Finally, in the case the converter sign reaches the front of the string, we assume that there is an extra 0 in front of the string, and add 1 to it, hence the special (?<>1) converter finalization command.

    This takes 32 commands and at most 53 iterations at the worst case, no matter what the actual numbers are.


    To arrive at this solution, first you need to realize that 100 numbers is too much to handle by investigating the numbers; there must be some testcase that causes any submission based on handling numbers to fail. Too many numbers for too few commands. So there should be some easy solution independent of the numbers.

    Next you need to figure out that you need to find some way to mark the end of the string (so you can start adding), you need to handle all digits, you need to handle 9s added, and you need to handle 999...9s.

    The above is mostly trial-and-error after the above realizations.

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

Because the contest was unrated, There wouldn't be any editorial for it?

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

In problem B div 1, I failed at system test 52. There is some thing special in this testcase I couldn't find out . Can anyone help me? I think every station passed have to be inside the rectangle of point 1 and point n because when going out of the rectangle and returning, it will cost at least 2*d which is larger than any a[i]. However, it is inaccurate in test case 52 when the best route pass through outside points and then come to point n. For some more details
Test 52: 12 1211 1 5 7 1000 1000 1000 1000 1000 1000 1000 1 1 5 5 3 4 4 3 0 1 0 2 0 5 0 7 1 0 3 0 8 0 10 10 The best way: (1,1) -> (0,1) -> (0,2) -> (0,5) -> (0,7) -> (10,10)