Endagorion's blog

Codeforces Round #295
By Endagorion, 10 years ago, translation, In English

Hello, Codeforces!

On March, 2nd at 10:00 MSK Codeforces Round #295 will be held in both divisions.

The round will be held at the same time with Winter Computer Camp olympiad, the problemsets will be highly similar. The problems are by me (Endagorion) and Evgeny Savinov (savinov). The problems are prepared by members of the Winter Computer Camp technical committee: Georgy Chebanov (gchebanov), Filipp Rukhovich (DPR-pavlin), Alexander Mashrabov (map), Sergey Kiyan (sokian), Konstantin Semenov (zemen), Kinan Alsarmini (Sarkin).

Big thanks to Max Akhmedov (Zlobober) for his help with preparing the problems, Maria Belova (Delinur) for translating the statements in English, and Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon systems.

The scoring is standard for both divisions: 500-1000-1500-2000-2500.

Please note that the Winter Computing Camp olympiad is scheduled to finish later than the Codeforces round. Thus, we ask you not to discuss the problems and solutions in the comments until 14:10 MSK. Also, viewing of other participants' solutions will be closed until that time. The editorial will also be published later.

UPD: you are free to discuss the problems now.

UPD2: the editorial is finally up! Sorry for the delay.

Also, grats to our Div.1 winners:

  1. Petr
  2. hos.lyric
  3. Syloviaely
  4. andrew.volchek
  5. xyz111

Special respect goes to Petr and rng_58 for solving the hardest problem E!

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

Comments Comments (148)
| Write comment?
»
10 years ago, # |
  Vote: I like it +133 Vote: I do not like it

Holy shit!!! There is eight Grandmaster and one International Grandmaster...

→ Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

It's gonna be LEGEN wait for it DARY!!!

→ Reply
»
10 years ago, # |
  Vote: I like it -47 Vote: I do not like it

artofproblemsolving

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +4 Vote: I do not like it

I even had to write my homework at Roumanian, which was pretty hard to do for being able to compete, so I hope it is going to be a round with very nice problems :)

→ Reply
»
10 years ago, # |
  Vote: I like it +299 Vote: I do not like it

Div1 participants be like

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I am scared!

→ Reply
»
10 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Feeling unfortunate for not able to participate in such a "red hot" contest due to exams. :(

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

It's good that I have school just in the afternoon :D

(on the other hand, will I wake up so early?)

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

    Oh, come on, 5 hours till the contest, why sleeping at all?

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

      Because I'd be sleeping at lectures otherwise (again) and it's not very nice to lecturers to always sleep through everything :D

      → Reply
»
10 years ago, # |
  Vote: I like it -10 Vote: I do not like it

To sleep or not to sleep...

→ Reply
»
10 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Such a beautiful day on most places in planet earth, would love to get some minus from the awesome people in codeforces.

→ Reply
»
10 years ago, # |
  Vote: I like it -13 Vote: I do not like it

wish you all best luck

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is it possible to unregister for the contest now ?

I registered earlier but just realized that I can't participate due to some reasons... I just don't want my rating to be screwed up because of such a mistake of mine...

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

    if you don't submit anything your rating will not be changed, also you can unregister by finding your name in the list and then clicking on the X sign

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

    If you don't submit anything , your ratings will not be screwed

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The contest is very bad time in IRAN

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

where's the score ditribution ??

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +120 Vote: I do not like it

7 Problems and 10 Red problem setters...

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

    Not everyone in the list is a problem setter :)

    → Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I have missed my academic Classes and waiting for Codeforces Round 295.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

No rooms???

Edit: Fixed

→ Reply
»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

where is rooms?

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

:'(

→ Reply
»
10 years ago, # |
  Vote: I like it +121 Vote: I do not like it

nice modulo used, first time 1000000007, second 1000000009, third 1000000007

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

    Yeah.I got a wrong answer because that.It's stupid.At least, they could put it in statement description in this form, not 10^9 + 9...

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

      Yyyy, is 1000000009 clearer than 10^9 + 9 ; d? But I agree that those modulos were pretty stupid...

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

        You can copy-paste 1000000009, which removes some room for error.

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

          Yes, that's what I wanted to say.If you read 10^9 + 9 and type one more 0, your program will get WA and you'll never know why :))

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

            Cause of this I write mod = (int)1e9+9;

            → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
          ModInt.h:
template <uInt64 _Key = 1000000007ull>
class ModInt

          I always use my template like it, so I'll write code such as "ModInt<>", rather than "ModInt<1000000009>", because of stupid habit.

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

    Unpredictability.

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

    Now I know what was wrong with my code :(

    Single change of line gets acc :/

    → Reply
»
10 years ago, # |
  Vote: I like it +50 Vote: I do not like it

See more on Know Your Meme.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Were there any successful hacks during this round?!

Edit: Xellos beat me to it :)

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

    A pretty solid amount. If we're talking both divisions obviously.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

I almost solved E in Div.2 I think I've got right answer for (1 <= n <= 15) But how can I get n Combination k when (n,k > 15)?

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

    Good! Today you have answer for n,k<=15,tommorow to n,k<=30 ... after around 7500 days you certainly have correct solution :D

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

mogityantt testebi da amocanebii,meore amocanis 4 testis shemdgenels movutyann suyvelaperiiiiii ( :) <3 best wishes!!! )

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Problems were fantastic, I LOVED this contest. It was more think-based than algo-based.

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

    shen chemi dzma gemeixede aqett O_o mogityann azrovnebaa ,ra iyoo kaii mitxarii ertiii haa?

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem C Div.2? Ô.Ô

→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Today was very nice time for Korean Users.

I always woke up in dawn to compete.

→ Reply
»
10 years ago, # |
  Vote: I like it +35 Vote: I do not like it

In case anyone missed it:

we ask you not to discuss the problems and solutions in the comments until 14:10 MSK

That's 2 hours from now.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Div2 D and E were HARD. (at least for me, unexpectedly harder than the usual D2 D and Es) :(

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It was nice. thank you.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

this round is hard :) but has got nice problems.

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it -11 Vote: I do not like it

Div2 C was easier than B :'( :'( :'( That's unfair...

UPD: Wait!! Don't downvote, I'm sorry. Div2 C was the hardest one among all.

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

    I don't think so. Div2 B was simple if you just look backwards than forward. Div2 C took me 30-40 min with all that analysis :P

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Damn it! Whatever, problem C took me 15 minutes but the contest was over :'(

      → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +36 Vote: I do not like it

The system test was so fast because of the very small number of sources which passed the pretests :)) Problem A scared a half of the registered peopele in div1...even me, but I had woke up already so what did I have to lose?Excepting the rating, of course :))

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

    Hm, that possibility of not submitting code if one solved it too late is wrong and should be changed...

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

During contest, I tried to hack B problem with N == M. Why it is not a valid input? Where does the problem statement say that M has to be different that N?

Update: Got it. I have to sleep more, lol!

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

    The first and the only line of the input contains two distinct integers n and m (1 ≤ n, m ≤ 104), separated by a space .

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

    Read the input line properly, its given distinct n,m

    → Reply
»
10 years ago, # |
  Vote: I like it +125 Vote: I do not like it

Codeforces round 287 : Rank 192, rating change 1582 to 1699
Codeforces round 295 : Rank 95, rating change 1612 to 1699

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

    I'm a bit luckier than you. My rating now is 1698 -_-

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

    I undersatnd you, man.Just take a look at my rating.I had contest when it increased being on positions like 300 and now, it decreased me ~100 taking position 300.So a differnce of differnces of more than 100 having the same position :(

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

    You got your brother man!! :D check this out http://codeforces.net/profile/dc26

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 9   Vote: I like it +20 Vote: I do not like it

    Kind of similar story :p

    Codeforces Round #295 (Div. 2) 114 3 +52 1699
    Codeforces Round #294 (Div. 2) 366 3 -52 1647
    Codeforces Round #293 (Div. 2) 212 4 +73 1699

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

    1699 to 1699 ._.

    → Reply
»
10 years ago, # |
  Vote: I like it +48 Vote: I do not like it

I spend very much time understanding the meaning of Problem B.QAQ

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

    I still don't understand the idea of that problem.Was stupidly easy.You had just to implement it without needing an idea or something.I say this even thouth I solved it...it wasn't interesting, and compared to the others it doesn't find its place in this contest.The rest of the problems seemed ok event thougth that A and C were counting problems and I didn't read D and E during the contest

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

    There were only 20 minutes left when I truly understood the meaning of Problem B.T^T

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

    Question like this (involving complicated, non-trivial process) should deserve explanation of the sample input at least.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell how to solve div-2 E ??

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

    maybe DP, and with some combinatorial mathematics?

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

      i know a n*k solution using dp but that will time out .

      → Reply
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I still can't view other's codes yet...

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

How to solve Div1 C?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +14 Vote: I do not like it

    Above formula works when k > 0. When k = 0, then simply output s

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

      please explain how u arrived at this formula .. thnx

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

      I'd appreciate a brief explanation.

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

    Consider some digit d and all summands, where this digit is the i-th least significant. It will add 10id to the answer for every way to choose the +s that makes that digit the i-th least significant in some summand. That means there are no +s on the next i positions (between two digits) and there is one (or the end of the string, which gives 2 cases) on the i + 1-st position. There are no other restrictions, so we just need to put K - 1 +s on N - 2 - i positions or K on N - 1 - i positions; the number of ways to do that is given by binomial coefficients.

    Another optimisation lies in adding up the same thing for all digits d farther than i from the end of the string at once, by quickly counting how many such digits there are.

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

      I was thinking the explanation and then I found that your explanation is much clearer than mine.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the test 8 for the Div2-C?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    5
    ACGTC
    Answer: 1 ("CCCCC")

    Maximum possible value for a string is MAXIMUM_NUMBER_OF_ITERATIONS * n * n.
    For "ACGTC", MAXIMUM_NUMBER_OF_ITERATIONS is 2 for 'C'. So this value is 50.

    UPD: MAXIMUM_NUMBER_OF_ITERATIONS means maximum frequency.

    → Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Why I can't see others code and test cases?!

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

i need see the tests cases :(, i will not sleep until that happens :(

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

why are the solutions not visible yet !!! ?? I hope the other contest is over ??

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Eagerly waiting for the editorial !!

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 C?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Call f[c] the number of letter c in the string. Call maxF is the maximum value of all f[c]. Call count the num of letter c that f[c] = maxF. The answer to this problem is count^n. I found the answer by writing brute-force solution first, then try some input to observe the rule.

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

      What is the proof of your solution ?

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

        Let s be the string given in input and t a string which maximizes ρ(s, t). Take one character (let's call it c) from t. By shifting s and t in all possible ways, c is going to be at the same position as s[i] exactly n times (for i = 0, n — 1).

        So, the character c adds to ρ(s, t) the value n * count[c], where count[c] is the number of appearances of c in s.

        Then, ρ(s, t) = n * sum(count[c]), for every c in t. In order, to maximize this, you will have to choose c for which count[c] is maximum.

        Let num be the number of c's for which count[c] is maximum. The answer will be num ^ n, because, for every position in t, you have num characters to choose from.

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

    k => Amount of letters with bigger frequency in input

    n => Lenght of input

    sol = k^n % MOD

    My solution

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

    http://codeforces.net/submissions/dc26


    Observe a particular character. In following cases, I am calculating distance of only 'A'.

    ABBB, ACCC -> 4
    AABB,ACCC-> 8
    AAAB,AAAC-> 36
    AAAA, ABBB-> 16

    Hence you can see, formula is something like L*X1*Y1
    where
    L=length
    X1=frequency in 1st string,
    Y1=frequency in last string.

    So Distance reduces to summation of N*X*Y for each of 4 characters, "A, C, G, T"
    Now N and X are constant.
    We have to decide Y to maximize the product.
    Now Suppose my String was AAAC. Now what string should I choose to maximize the product.

    Frequency of A is 3, C is 1. So A will be the major contributor, I will get maximum when my other string is AAAA

    Now if my string is of type AACC, both A & C are contributors. So I can make a string of C's and A's
    I know the length i.e. 4 in this case. Now for every position , I can select either 'A' or 'C'.
    So m answer here is 2^4.


    Similiarly.
    "AACCTT"
    I can chose, 'A' 'C' or 'T' for every position.
    So answer is 3^6.

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

http://codeforces.net/contest/521/submission/10108767

I thought this would TLE, since it first calculates the power and then the remainder (does it?). Could anyone give some insight into this? I'm not sure how Ruby calculates that, but I would imagine it uses big integers.

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

    Is this what you want?

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

    What is the logic behind this solution ??

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

    Well there are only 4 characters, and the max results has 60k digits, which should be able to fit in the time limit.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to solve Div1-B without using multiset?

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

    You can use priority queues. I'm not sure this is the answer you are looking for :)

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

      Div-1 B why is evryone converting m to n ... how is that easier than converting n to m

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

        You mean storing a point (x,y) as (y,x)? Because people needed to sort the points by y and then by x. Reversing them means that you can use the default pair comparator.

        → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You also can sort all of the cubes and use two iterators for the current upper cube and the corresponding cube it lays on.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me how to solve div.2 C?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    He won't tell, but you can see this submission: 10118102

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

      Thanks a lot. this " j=(j*z)%M;" Can you tell me why? my English is poor please forgive me

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

      I knew it .thanks a lot

      → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This is really a nice round. It proves that it was a good idea to challenge a Codeforces Round during class break.:) The problems are really nice,and this is my first time of Rating going up:)

BTW,the contest ID of 520 in Chinese has a quite romantic meaning.

Best wishes to all of you:)

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is there any editorial for problem Div.1-D?

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

    The editorials for all problems are coming. I'm sorry for the delay.

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

    Short description: div 1d was greedy. if we use assign op for any skill, then it's optimal to use as first op, so change highest assign op for every skill i to "sum b-a[i]" and discard the rest.

    Now every mult op multiplies answer by b, sum op multiplies answer by (a[i]+b)/a[i]. Greedily take highest multiplication factor until you can't pick any more operations. Print operations used for a skill in the order "type 1, type 2, type 3".

    Note that when you use a sum operation in a skill, factors for the other sum operations on the same skill change (mult doesn't affect anything because it's only done in the end). The way I solved this was keeping only the highest sum op for every skill in the priority queue and updating factors when needed.

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Div2-E / Div1-C?
I could find just a dp solution which takes N * K.
Any helps would be appreciated...

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why doesn't my solution of Div1 B work? Isn't the answer a modification of Kahn's algorithm? And what's pretest 4 about?

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    The solution is not a "greedy" topological sort of the graph. You can also remove nodes that have non-zero in-degree but after their removal, the connected component they are part of must remain connected. So you should greedily remove nodes that don't affect "connectedness".

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

    first person can take 0, 1, 2, 6, 9 he will choose 9

    second person can take 0, 1, 2 he will choose 0

    first person can take 1, 2, 4 he will choose 4

    second person can take 1, 2 he will choose 1

    first person can take 2, 6 he will choose 6

    second person can take 2, 3 he will choose 2

    first person can take 3, 7 he will choose 7

    second person can take 3, 8 he will choose 3

    first person can take 5, 8 he will choose 8

    second person take the remaining 5

    so the result will be 9041627385 % 1000000009 = 41627304

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the logic of Problem C(DIV 2) ?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

520B - Two Buttons I know that turning m into n is easier than the opposite, but why is this code wrong? Can you give me any simple counterexample? 

while(n != m){
        if(n > m)
            n--;
        else{
            if(m % 2 == 0){
                m /= 2;
            }
            else{
                if((n-1)*2 >= m)
                    n--;
                else
                    n *= 2;
            }
        }
        sol++;
    }
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try n=3, m=7.

    That code goes 3 -> 6 -> 5 -> 4 -> 8 -> 7, when in fact it is better to go 3 -> 2 -> 4 -> 8 -> 7.

    → Reply
»
10 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Heh, after reading that savinov is also a problemsetter, having #285 in my mind (when I have written two full of hate comments and they turned out to be my two most upvoted comments ever :P) I was scared that some noninteresting problems will be included. And after publishing editorial it turned out that he set one problem — guess which — of course the most shitty one ( ͡° ͜ʖ ͡°) (I hope that it's clear it is B).

B was just straightforward simulation. Could anyone point me something interesting in that problem :P? Moreover it was not nice to code (not that awful since that is still an easy problem, but ratio awfulness of code / needed thinking is still very high). Not to mention that when coding it I got sick of it and switched to C (which turned out to be a good decision, since it was easy) and then read D and couldn't resist solving that very interesting problem (kudos to Endagorion!), even though I was aware that EV of my rating will be higher if I will return to B.

What is more, it got terrible and very confusing statement. In the very title we are told that this problem is about cubes, I have always thought that cubes are something living in 3D space, it turned out that I was mistaken. Then "Let's consider a coordinate system such that the OX is the ground, and the OY is directed upwards." — ok, so OZ is that only one remaining. Then "The figure turned out to be stable. This means that for any cube that is not on the ground, there is at least one cube under it such that those two cubes touch by a side or a corner." — ok, so if directly under one cube there is another one and it touches it by whole face then it is not stable and if area of tangency region is 0 then it is stable? Great idea! Then some confusing part about clarifying that statement which I unfortunately omitted looking for some helpful infos in latter part of statement. And after reading the whole statement I realized "ok, so those 'cubes' are 2-dimensional, good to know" ( ͡° ͜ʖ ͡°) (and of course I needed to reread the statement completely).

I have always thought that Codeforces rounds is not a place for some "ACM Out Of Nowhere Regional"-style problems which statements can be compressed to "You got some stupid rules — simulate it".

I am aware that this is pretty offensive and sorry about it, but I just couldn't help writing that. I think that simply savinov's rounds will be the only ones I will omit purposefully. Maybe it's too big amount of hate for posting just one noninteresting problem (of course I have seen much uglier problems), but facts that it was given together with Endagorion's problems and its terrible statement empowers that impression significantly.

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

    I thought Problem B and D are very similar, so I don't understand your claim.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      Did you participate parallely in Div2 contest? Then Div2D and Div1B are undoubtedly similar :).

      In what sense they are very similar? Their contents were surely very different and for me "problems X and Y are similar" means "statements of X and Y were similar/they followed one idea/similar techniques were used" and all of those options are clearly absurd.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +23 Vote: I do not like it

        It's true that problem B is an implementation problem, but it was interesting and I failed 3 pretests as I didn't think cases that if one box is removed, then some 'free to be deleted' boxes are no more free. If pretests were a little weaker, then the problem could a decent reservoir for hacks.

        In my view problem D was quite similar, in the sense of solving technique, as the greedy condition for each item was more evident for me than problem B. I resubmitted only because I didn't keep 'assign -> add -> mult' order. With 'long long' requirement, there were several traps, and I can understand acceptance rate was very low, but this is not because this problem was superbly interesting.

        In the both problems the main idea was 'use priority queue to decrease time complexity from O(n) to O(log n)' and the data structure to do this was very similar. So while I could be misleading about saying the problem statements were similar, not that much about the solving techniques.

        Anyway, I enjoyed all A-D problems, and didn't have any clue about problem E. (I'm very weak to graph problems, so...)

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

          You know, you also keep a priority queue in Dijkstra, but I won't call it similar algo to those ones. In B one has to come up with an ingenious observation "We want to maximize number (with fixed length). Let's maximize greedily the most significant digit!" and update available values (which for sure doesn't have anything in common with D), while in D you can just take a prefix of upgrades sorted in some funny order without any modifications during choosing them consecutively, so I still no longer see any common things other than greediness.

          Moreover I guess that you have at the moment 2572 rating not for no reason and D might have been clear for you, while I think it was in fact very tricky, while B was straightforward and just demanded some carefulness when coding it (D also).

          The most tricky part in D was in my opinion observing that we can choose to buy upgrades in other order than we have to perform them. But things get even more complicated, because if we will perform adding and multiplying only then for each upgrade we know how many times it will increase result, but things get complicated when we are dealing with assingments, because for addings the ratio after performing it and before changes if we will perform an assignment or not, but next observation is that this is in fact not an obstacle since we can simply treat greatest assignment as an ordinary adding (and forget about others). I consider that reasoning very nice, suitable for D problem.

          By the way I didn't notice that we can choose to buy upgrades in other order than we have to perform them and computed best way assuming that we use exactly k upgrades on that skill for all reasonable values of k. I noticed that if we won't perform all multiplyings (other than those with b=1) then we can perform at most 1 adding and iterated on that number and whether we perform assignments (I used logarithms to compare profits since they were too big). Then I observed that 2 * prof[i][j] >  = prof[i][j - 1] + prof[i][j + 1], what allows us to do everything greedily. I think that those observations are also pretty nice, but unfortunately I didn't make it work since my code turned out to be pretty tedious and vulnerable to many small mistakes.

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

    It should have been mentioned that Vasya and Petya are cosmonauts working on this experiment in zero-gravity conditions.

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

    Ok man, at least you didn't walk up to the computer screen at 2 AM in the morning, and see that all problems but E are math.

    Man you have no idea how I felt after that -__-, and you're complaining about 1 problem.

    There needs to be more diversity in CF rounds, you can't just make 4/5 problems math, or dp, or whatever. It's just not interesting when you do that.

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

      Lol, you will have hard time in competitive programming if you call such problems "math" ; d

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

        You can't argue with tags man.

        Shop math, sortings Pluses everywhere combinatorics, dp, math, number theory DNA Alignment math, strings

        Now if we do a simple string search on "math" we can see it in all three of these problems.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          In that sense absolutely everything here is math, go ahead and whine everytime when you see a "+" or "product" in a statement since that immediately indicates that this is a math problem --> shit problem.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            ← Rev. 2   Vote: I like it -21 Vote: I do not like it

            I'll go ahead and do that, thx.

            BTW I should say I was joking about the tags (and this) ^_^

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

          You can't argue with tags man.

          And what if I tell you that everyone who solved a problem can edit tags? :) So you can solve/copy-paste solutions for whole div1 problemset and then easily make it 5/5 math (according to tags).

          In some sense all programming is math.

          And problems which you mentioned aren't math in bad sense of this word. I am glad that there are not a lot such problems at CF at all.

          P.S. Have you ever tried Project Euler? Or Ad Infinitum contests at HackerRank?

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

    You know, when I was solving this problemset — I was actually happy that problem B was 2D instead of 3D)

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

      Of course I was happy also, but fact that I learnt that after few minutes is not nice :P.

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

    Well. I feel like I should reply something.

    Regarding problem B, I don't feel like this problem stands out from the problemset in a bad way. It probably didn't feature wonderful insights, but I like this problem too; if I would have created this problem, I wouldn't hesitate to include it in some of my rounds.

    The statement might not be in the best shape, I must agree. However, this is quite certainly not savinov's fault. The point is that the problems were prepared collectively, with me being the lead of the process. We decided to change the problem B in the last moment due to unforeseen circumstances (basically, it turned out that the former problem B was featured in some contest earlier), and savinov kindly provided his problem. It might have had some issues, but then again, every problem has issues until it is triple-checked by different people. So, plainly, it's my fault that the problem didn't get the attention it deserved.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand the solution of DIV 2 C. I spent a lot of time thinking of it and I can't understand why we care only for characters which occur most frequently. Having string s = "GAAAGGCCCCCCGGG" we count occurences of each letter : A -> 3 G -> 6 C -> 6 so the answer will be 2^15, becase 15 is the length of word and G i C appear the most frequently

so for example we count strings like GTTTGGCCCCCCGGG , because here also G i C appears 6 times , but p(s,t) = 1080 which isn't maximum. I believe that maximum is where t is for example GAAAGGCCCCCCGGG or GACAGGCCCACCGGG so A also has contribution to result.

Here is my code calculating these values http://ideone.com/ZedQOQ

I'd be grateful for help

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

    The strings you provided don't attain the maximum value. Have you tried computing the value p(s, "GGGGGGGGGGGGGGG")?

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

      Thank you. The result for GGGGGGGGGGGGGGG is better ( 1350)

      → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

waiting for new contest !!... I want to became CM

→ Reply