By zeliboba, 9 years ago, translation, In English

Hi, Codeforces!

AIM Tech Codeforces Round will take place on February, 4 at 20:05 MSK.

The round is prepared by AIM Tech employees: Kostroma, riadwaw, yarrr, ArtDitel, ValenKof, bobrdobr, agul, gchebanov and zeliboba. Round will take place during Petrozavodsk Winter Camp, which is sponsored by our company.

We made our problems a little easier than at our last Round, but we promise they won’t be less interesting. Scoring system will be static. The final distribution of points will be announced right before the round, however you should note that this time difference in complexity between problems div1 C, D and E may be less than usual so our strong recommendation that you read them all first.

Thanks to Mike Mirzayanov(MikeMirzayanov) for brilliant platforms Polygon and Codeforces, problem coordinator Gleb Evstropov (GlebsHP) and Maria Belova (Delinur) for English translation.

Our company specialises in proprietary trading, the key concepts in our work are big data, low latency and high frequency. Our team mainly consists of graduates from the MSU Faculty of Mechanics and Mathematics and Moscow Institute of Physics and Technology (MIPT).

We wish you good luck and high frequency rating!

P.S. For all participants of PTZ gathering we are glad to announce evening buffet that will take place at Paulaner Brauhaus and will start Februrary, 5 at 7:30 pm

Scoring

div2: 500 — 1000 — 1500 — 2000 — 3000

div1: 500 — 1000 — 1750 — 2000 — 2250

Editorial

P.P.S. Author solution of div2A had precision error 5e-7, so we decided to rejudge this problem.

Announcement of AIM Tech Round (Div. 1)
Announcement of AIM Tech Round (Div. 2)
  • Vote: I like it
  • +298
  • Vote: I do not like it

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

I hope that the all problems will be more interesting;)

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

GL & HF

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

Why does it say "February 22" when it actually is on February 4th ?

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

It would be great to make one division contest like previous round :) I think that is more interesting for everybody.

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

It says the scoring system will be static, does this mean that the points for submissions of a problem won't decrease as time goes by?

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

    As far as I know, No it means that the scores of problems won't be changed during the contest ,this means if problem C is for 1500 points before the contest it can't be changed to 1250 or 1750 points during the contest even if number of submissions for that problem increase or are relatively less.

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

No T-Shirts ?? Your past contest had 200 T-Shirts which was really awesome.

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

    Next time we are going send T-shirts again =) This round is created mostly for participants of Petrozavodsk Training Camp.

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

In fact I havn't received the T-shirts prized for AIM-FUND ROUND yet! :D

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it
  1. difference in complexity between problems C, D and E may be less than usual in Div2
  2. difference in complexity between problems C, D and E may be less than usual in Div1
  3. C div2 = A div1, D div2 = B div1, E div2 = C div1
  4. difference in complexity between problems A, B, C, D and E may be less than usual in Div1
»
9 years ago, # |
  Vote: I like it -21 Vote: I do not like it

what is high frequency rating?

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

    Maybe your browser can't display it, but the word "frequency" is crossed out.

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

As far as I remember, your previous contest was very good.I hope this one will be better.

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

    I think you mean very tough.

    In div 2 the standing was very unusual, from the 27th to the 1500th all of them solve A and B only !!!

    very easy A,B and very hard C,D,E. I think the difference in difficulty should be normally increasing not exponentially.

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

      Agreed, but all problems were good at all.

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

      this contest was better very easy A,B,C and very hard D,E

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

Be rated or not ?

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

Will it be a rated contest like division 2 contests ?

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

    It's usual rating contest, except that it's prepared by us

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

Will the score obtained will depend on the time of submission just like any other round?

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

when I try to submit a code it says i'm not registered !!!

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

    you must be registered before start of the contest. usually register is open 24 hours before the contest begin.

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

      he/she registered in two contest before how could he/she doesn't know about this

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

        good question for his/her ! I must investigate more , next time.

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

And here is when I hack Um_nik ! :)

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

How to solve problem D div 2 ?

Nice problemset !

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

How to solve Div2C?

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

    First observation: each 'b' symbol will be connected with every other symbol in the string.

    So, find all symbols connected to all others and add them to first set ('b').

    First symbol that is not 'b' will be 'a'. Add this symbol and all symbols connected to him to a second set ('a').

    All other symbols not in first two sets will be in third set ('c').

    Now validate sets 'a' and 'c' so each symbol in the set connected to each other (set 'b' is valid by its definition). If not — answer 'No', if yes — print the answer.

    Complexity is O(N^2).

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

      Now validate sets 'a' and 'c' so each symbol in the set connected to each other (set 'b' is valid by its definition). If not — answer 'No', if yes — print the answer.

      Oh, and now I realized my solution is wrong, because it's not enough to check this. You also must validate that any 'a' and 'c' are not connected.

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

        Lol yes, I actually just realized this too.

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

      My alternative solution:

      1. Obtain reverse graph. (not connected graph)
      2. Try to color it in with 2 colors when no edge is connecting 2 nodes with the same color
      3. If failed -> No solution. If colored, pick any color as 'a', other colors as 'c'. All non-colored nodes as b.

      EDIT: probably bad idea, got Wrong Answer on test 26 because I forgot to check that any two different colors are not connected

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

        Additionally, in step 2. you need to ignore nodes without edges, so they can be colored as 'b' in step 3.

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

          Well, these would be ignored anyways as all 'b' nodes would not exist in the reversed graph (because 'b' nodes are connected to every other node).

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

            It depends on your method for generating the reverse graph. If you don't remove the nodes that are not connected to any other node, then there is a risk of coloring them as 'a' or 'c' in step 2.

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

        I got AC with this kind of solution, I checked the string 1000 times to try to find new symbols, then filled the rest with 'b' and checked the answer: 15798901

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

      I had brute force solution, lol :))) Of course, it is named as "backtracking", but, anyway, it was too stupid. TL on test 15

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

I knew How to solve E....

If I had just 5 minutes more...

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

    Same here. Fucked up on indecies (+/- 1)

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

Can anyone give me an idea for B div.1 ? :'(

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

    Factor a[0]-1,a[0],a[0]+1, a[N-1]-1,a[N-1],a[N-1]+1. Then for each prime from that factors, do:

    • in first pass count best solutions for left prefixes
    • in the second (reversed) pass get best solutions for suffixes and join with the best solutions for prefixes.

    Solution for prefix is basically a run of modifications such that gcd(run) = p and then run of deletions. Deletions from prefix solution join with deletions from suffix solution.

    PS: there may be a mistake in idea, I didn't get AC.

    PS: it's actually easier to make one pass of DP for each prime

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

    My idea was that either the left element or the right one will be present in the final array, so try for every prime factor of those numbers (plus 1 and minus 1 too) the minimum cost to build an array with all numbers multiple of that prime.

    I did it with prefix/suffix DP and some operations of addition in between. I don't know if my solution is correct though.

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

      +1 or -1 of left or right elements may also be present.

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

        Yes, that's what I did. I just forgot to mention it here. Thanks for pointing it out.

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

    Note that you only need to consider prime divisors of a1, (a1 - 1), (a1 + 1), an, (an - 1), (an + 1) as possible GCDs. Trying all the possibilities should be easy enough.

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

      I didn't consider cases for an only for a1 :(

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

Anybody got stuck too at Div1B — 9th pretest?

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

    Stupid mistake, when factoring by trial division forgot to check if the rest of the number is > 1 and then it should be added to prime list too.

    9th test is the first when a large prime appears.

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

Solutions for Div1 D? Being solved way more than Div1 C for some reason, is there some easy solution?

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

    I am not sure why it should work, but here is my approach, which passed pretests. First of all guess each friend once (order doesn't matter now). After that I always greedily guess the friend which gives me the biggest profit as a matter of probability that you win in that turn. I simply do that with a heap and while I have enough time.

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

      Let pi denote the probability that we've already caught the i-th person. The probability of winning right now is p1·p2·...·pn. For each i we can consider ri — the probability that we've already caught this person or we will catch him/her in this turn (assuming that we're going to try to catch him/her now). The probability of winning a will change to where c denotes a person chosen in this turn.

      Why can we greedily choose the biggest ? I won't show the formal proof but the following two arguments are enough:

      • the probability of winning in some turn is equal to the product of chosen values
      • For fixed i the value of is decreasing as we choose this person again and again.
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Today Codeforces was extremely slow :( I was hacked and didn't refresh manually. It took 25 minutes for Codeforces to warn me :( I went to other heavy websites but my connection was totally okay :(

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

    I had the same problem: my A solution got hacked 9 min before contest's end, but I got the notification only when it was over :( So I spent 9 last minutes on D rather than finding bugs in A. Seems like manual page refresh is a must :(

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

Div2 B hack:

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

    Why So Many Ones?

    3 1 1 1

    is enough

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

what is test 6 of div1 C?

I think this the worst decision I make in my life choosing to solve C first!!

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

Wow. You really can't make easy contests.

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

Another contest by unusual scores and difficulty of problems... at Div. 2 Problems A,B was very very easy and so Problem C a little ... for this a lot of people solved problem A,B,C and the force(competition :D ) of contest was for a few of Time!! All are the same !! :|

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

    Well I think ABC tasks was very good for div2: difficulty is raised from A to B and from B to C significantly (there were like 3000+, 2000+ and 1000+ solved participants).

    But D and E was too hard (only 15 and 1 solved). Imo, D should be actual E and there needs to be a simplier task between C and D to be perfect problemset for Div2 :)

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

      Now I see Problem C has just about 500 AC after system tests... This mean that Problem C was not normal so... Now All the same at solve Problem A && B :D !!

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

      actually A-> 3200 B->2500 C-> 500 . Not a good distribution.

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

My hack case for C :

4 3

1 4

2 3

3 4

I even hacked my own solution with it (i.e. discovered it after locking -_- )__

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

Another contest with weak pretests.

GL hackers!

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

wow! so many failed C(div2). and the whole time i was trying to hack with B -_-

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

My hack case for A(div 1) C(div 2) :

5 9

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

bbbac or bbbca

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

    Both are supposed to be accepted right?

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

      In all testcases 'a' can be swapped with 'c' in the answer.

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

I thought the string in problem A can have any character from a to z. So I solved the harder version and failed system test. After contest I changed upper bound of character from z to c and got AC :(

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

    I think I also had it bad. Forgot to print "Yes" in the special case ( n = 2 and m = 0 ) and got WA78. But I fixed it after the contest and it got accepted. I kind of hate myself right now.

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

      This kind of mistake may sometimes be avoided by having only a single line in which you output Yes and No. If you don't have any "return" statements above the line has to be executed always.

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

        Yes, you're right. It's entirely my fault that I implemented the code like this with multiple Yes or No lines, and avoiding it is actually very easy, but I think I'm way too lazy for that kind of "refactoring". I mean, it's the "accept rush". But just seeing your solution fail simply because you didn't format the output properly is a real pain in the neck :/

        Also, the "Yes" bit is really redundant. It should've been the string / No from the start.

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

          I understand the "accept rush":) And if the code is already written then there is obviously no time for refactoring. But if you start writing the solution by introducing the bool variable and then serializing it to "Yes/No" only once at the end, it somehow makes it more difficult to forget to set it properly. And there is no chance of forgetting about the output, because it's always there at the end.

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

lol, in A we should use 'a'-'c' only... I should read statements sometimes.

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

    I even asked a question, are 'a' and 'z' considered neighbours.

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

Uhh... thank you! :D

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

    Well share the submission link/username so that i know where to look incase i don't get something from editorial.

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

Hm, ok, that was fast!

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

Woww. Rating lost after one contest = Rating gained after one contest! :P

Such stability. Much wow. :P

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

Aw...Fast system testing and fast rating changing .. good :)

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

Can someone tell me how to deal with precision problems at div1E? I was using FFT(but had same big values due to modular inverse) and modulo being very big, I was getting values with a big error.

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

    There are two possible solutions: the first is using Chinese Theorem (calculating the answers modulo some numbers about 106, then obtaining the answer in long arithmetics), or using the next trick: take and represent each coefficient as ai = bi·M + ci, where ci < M and bi < M. Then the multiplication of polynomials with coefficients ai is reduced to 3 or 4 multiplications of the polynomials with coefficients bi and ci. There coefficients are less than M, so the usual FFT in doubles is OK for them. For instanse, check Endagorion's solution.

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

      I was thinking about Chinese reminder theorem too but it seemed too slow and hard to code. I'll try to implement the trick tommorow(hope it'll work). Thanks

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

Hacked B(in Div.2) three times. Problem C could have been just a little more easier. PS: Thumbs up for the fast system testing and ratings.

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

Well, screwed up somewhere in A and couldn't find the bug. Would have to start over so skipped. Messed up my approach to B.

Looked like I might score zero for the round.

I checked the C, D, and E problems just in case one of them was easy. Bingo! Problem D was a very easy one hidden among the toughies.

So I end with about 1300 points for solving one very easy problem and screwing up another very easy and an easy. I really thought it was going to be a disaster of a contest after the first hour with nothing to show at all. Instead I ended up in the top 15%.

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

    Either use cin or cast to double when working with long double. It's known problem on Codeforces.

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

During the contest, I received an announcement saying that my B was hacked, but it wasn't.

What could it be?

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

I liked the contest, congratulations.

Also I want to say thanks to Codeforces team, and community, for making this a nice place to study and improve. This was my 50th contest and I got (+51) in my contest rating :D

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

So I did the Div2A in the practice room and got WA when just using "cout" for the answer. Got AC with printf(".6lf").

I read the statement carefully and it says if "absolute or relative" error does not exceed 10^-6. So why is the printf needed instead of just cout? I would think the extra digits after the 6th digit would be less than 10^-6 and thus OK within absolute error tolerance.

Should it be both absolute AND relative error < 10^-6? Or is the example about checker saying that for results < 1 it will use relative error?

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

    I think you should use statement like: cout << fixed << setprecision(10) << ans << endl;

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

      Well I know how to print the answer to get accepted, but I am asking WHY it has to be printed to exactly 6 decimal places, because the statement says "relative or absolute" are both OK.

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

        If you don't output at least 6 digits after decimal then your output can fail both the conditions (i.e. relative and absolute both). Just like if you see your submission with cout, correct output is 2.6666670 and your output is 2.666670. The relative and absolute both the errors are >= 10^-6.

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

The biggest mistake to make during rounds is to not read the problem carefully. Could not solve B because I missed I can make those operations only once. Any ideas about the solution if I could use them infinitely?

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

    Haha glad i wasn't the only one. The only solution i was able to come up with is n*sqrt(max(a_i)): go over all the possible divisors up to sqrt(max(a_i)) and for each number a_i, calculate if it's best to delete this number (we can do deletions infinitely so we don't need to care about contiguous segments) or to change it to be divisible by the potential divisor. At 30 billion such operations this is too slow for the given time limit though. We can improve this by taking only into account prime divisors, which brings it down to at most 3 billion operations, which is also too slow, but getting close at least.

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

      Why not primes above sqrt(max(a[i]))?

      Please clarify your complexity analysis.

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

I think it‘s a bit difficult for me,but anyway,I think it's a great round.

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

wat

how is this possible

i don't even

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

Any ideas about Div2 E? I passed 8 pretests and then got stuck at 9. I don't know if my idea is totally correct :/ or there could be some mistake with the implementation :( but as it is so hard, I think an amateur like me obviously can't solve it. So, I guess I passed the 8 pretests submitting totally wrong code :/ anyways, ideas please? I have mu exams going on so I don't wanna check the tests which failed me right now. Will do it 2 days later. Meanwhile, please help :)

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

Why have ratings been reset ?