Endagorion's blog

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

Hi all.

On Sunday, September 7, at 19:30 MSK regular, 265-th, Codeforces round will take place. Problems are prepared by me, Mikhail Tikhomirov. Round will be for both divisions.

Standard (not dynamic) scoring will be used for this round.

Div. 1: 500-1500-1500-2000-2500

Div. 2: 500-1000-1500-2500-2500

I would like to thank Gerald Agapov (Gerald) for his help in problems preparation, Filipp Rukhovich (DPR-pavlin) and Alexander Mashrabov (map) for round testing, Maria Belova (Delinur) for English statements and Mikhail Mirzayanov (MikeMirzayanov) for creation and development of Codeforces project.

This is going to be my third round on Codeforces, and I tried to make problems as interesting and diverse as possible. Hope you will enjoy this round. Best of luck! =)

UPD: round is over. Thanks for participating, hope you liked the problems.

Grats to all the winners:

Div. 1:

  1. tourist
  2. Petr
  3. rng_58
  4. al13n
  5. ecnerwala
  6. qwerty787788
  7. marek.cygan
  8. KADR
  9. Merkurev
  10. hos.lyric

Special respect goes to simonlindholm, the only participant to solve the hardest problem E!

Div. 2:

  1. matthew99
  2. acrrca
  3. ccdream
  4. Chameleon2460
  5. newSolars

Editorial is here.

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

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

Your next contest after Three years....!

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

I wish to see more Math.:)

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

    I think you'll get what you want.

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

      :)

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

        I hope for no math.

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

          Why both hope for math and not math problems got negative votes?

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

            Because it's spammed on each contest announcement?

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

              Then explain positive votes in this comment Edit: it's no longer up-voted (but it was +13)

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

                Oh, I hadn't downvoted that one. Fixed.

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

                  I meant if it's really spam why people in codeforces up voted that comment ? Edit: it's no longer up-voted (but it was +13)

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

                  Dunno, I provided a reason for why downvote (there are dozens of short comments like "I hope there'll X" and "GL&HF" and "thanks for X", and I stopped being interested in reading them after the first 100), not why upvote :D

                  CF voting is really strange, I have no idea why it behaves the way it does. Sometimes I'm thinking the answer could be 42.

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

                  @Xellos I will keep that in mind from next contest.:)

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

                  Hey man, I just keep repeating that because this site is not named "mathforces", and others keep making "Hope for math!" comments. (!!)

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

                  Oh yeah, I forgot that the optimal method to reduce the "Hope for math" spam is to add "Hope for no math" spam.

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

                  While speaking about math, have you noticed that the absolute value of your contribution is a perfect cube? Also the absolute value of mine is a 4th power added to 1 :o. It is a very interesting topic :o.

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

                  Here , I have made the absolute value of your contribution a 4th power added to 3 now :D

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

                  Actually, it is the absolute value of a 4th power added to 3 :D.

                  Also your contribution is a fourth power :o.

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

    why? I think Math is difficult

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

    Math is beatiful guys and haters shut up xd. If it weren't for math, there won't be competitive programming xd.

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

I hope I can do better！

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

I m going 2 rise

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

I think this announcement sets the record for the shortest announcement for a contest ever. Keep It Short and Simple! :)

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

    Keep it simple, stupid! (the KISS principle!)

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

    I like this simple style,Keep it short so that people don't miss part of important message.

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

    Good way to get more upvotes :D

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

Wish to learn new concepts ,new tricks and new things :)

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

Why is everyone in a hurry?! Contest's blog 5 days before contest?! Once they posted it a few hours before the contest :D Oh, and no thanks to Gerald or anybody else?! What an unusual contest blog...

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

It is my first time to compete, I hope i can solve at least once.

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

Good luck and have fun! scores up, up and up!

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

How to register for the contest ? I can't find any link for registration

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

    You will be able to register a few hours before the contest.

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

Long Waiting For this contest

Good luck everyone

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

cheer up!

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

First time above 1700 and I have a question regarding divisions. My friends take part in Div2 but I can't Register to Div2 due to 1700+ rating.

Will I be able to join as virtual something when Div2 starts without ranking or I must register in Div1?

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

What type of scoring will be use ?

Good Luck to everyone

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

    why do u combine

    Unable to parse markup [type=CF_TEX]

    with normal text?
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      I don't know ? 'Cause are different topics ? My question and my wishes ?

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

how to solve Div-1 B?

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

    Bruteforce, I think. There are 6 permutations for each of 7 point (you can fix the first), so it is 6^7 ~ 300k — fast enough.

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

      Or generate all variants for 3 points, build all cube and check points.

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

      And how do you check if it's a cube?

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

        I had an idea to calculate all pairwise distances for some fixed permutation (there are 28 segments in total) and sort them. Now, if first 12 of them are equal, next 12 are equal and last 4 are equal, it's a cube. But I didn't have time to code this solution and can't prove it

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

          i'm convinced this idea is correct, but i dont know why my solution 7712723 gives TLE!

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

            Because that's incorrect idea and obviously your solution is wrong. Also, your code-style is very dirty. Learn Math and don't ask stupid questions anymore.

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

              Lol, that's pretty rude. I'd ask you to learn some good manners first.

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

                Oh, I so ashamed...

                Один стою в белом пальто красивый.

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

            Map is not so fast thing:) Try to rewrite it without map, it should pass — my solution is basically same, but with vector&sort (7708825), and it works in 0.7 seconds.

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

      my solution 7712723 with the same idea TLEd! :(

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

      Could you please explain how we can fix one point if all of them probably were shuffled?

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

It would be great if you could write problem A shorter! At the first, I was confused.

Thanks!

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

How to Solve Div -2 C ?

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

    they key observation is that if we don't have any palindromes of length 2 and 3, then we will have no palindromes at all (other than single characters, ofcourse).

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

      How did you arrive at this conclusion? Have you solved a similar problem before or was it intuition or did you think of this during the contest?

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

        intuition. any palindrome of length n > 2 has a sub-palindrome of length n - 2 as its substring (u can get this by removing the first and last characters).

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

        easy to note that we can build palindrome by add same character to begin and end of another palindrome. just consider the case of odd and even length, so we could just check every 2 and 3 consecutive letters

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

      I made this observation during the contest but do you still have to loop over all possible strings after the input?

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

      Can u explain ur solution !

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

    Suppose you have a palindrome of length at least 4. Delete the start and end characters. Now you still have a palindrome. Thus you only need to consider palindromes of length 2 or 3. Find the rightmost character that you can increment to something satisfying s[i]!=s[i-2] && s[i]!=s[i-1] (within the bound of p of course), then fill the remaining letters with the "smallest" letter possible.

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

I got my first hack on codeforces! I tried a little different strategy this round. I solved B and A quickly and then tried to solve C within the first hour. But I couldn't. Nevertheless, I spent the whole of the second hour trying to hack but was not very lucky until the last 10 minutes. About 7 minutes before the end of the contest I managed to hack a solution!

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

Nice problems!

How to solve D? I was struggling for quite a while, but didn't come up with anything faster than 100 FFTs (or 2 FFTs, but for vector with size 107) :(

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

    My solution relied on the fact that we only need 1e-9 precision. Basically, with probability 1-eps we never get to very high levels.

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

I managed to find a suitable algorithm for 464C - Substitutes in Number, yet couldn't solve it because I couldn't read the input properly. I don't know yet what was causing the quite straightforward input code to fail... Here's my last failing submission : 7713194 If I add assert (c >= 0 && c <= 9); after line 43, the assertion fails...

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

This was a great contest :) Thank you for writing! I liked many of the Div 2 problems.

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

I have a feeling that a lot of A-Div1's will fail.

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

I see some hacks on div1-C, for example Merlininice has quite a few. How can a solution to div1-C be incorrect? It looks really straightforward.

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

    Are you now scared that yours too is incorrect?! :D

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

    Some people did not take the length by module, some took it by module 109 + 7 instead of 109 + 6.

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

      But why does one need the length at all?..

      I guess you're saying that people were computing "length of expansion of digit X" instead of "10 to the power of length of expansion of digit X"?

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

        Exactly.

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

        My solution got hacked also. It was totally a straightforward dp problem. I just couldn't figure out why it was giving incorrect ans. I thought keeping the length and exponent value would do the same thing but totally forgot that if I kept the length, I would have to do modulo 10^9+6 on the length according to FLT. If only I'd kept the exponent value instead :(

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

      10^9+7 instead of 10^9+6 ????
      problem statement say 10^9+7

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

        If we store just length, we're computing 10^len at some point. Using FLT, we can just compute 10^(len mod (10^9+6)) instead, so we can just take len mod 10^9+6 instead.

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

        One should use 109 + 6 in order to keep length. Because it is the period of pows (check little Fermat's theorem)

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

      some took it by module 109 + 7 instead of 10^9 + 6.

      do you mean that if I saved the length instead of power of 10 and make it modulo 10^9+6 I will get AC?

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

    Hey Petr, didn't you make a similar mistake (taking different value for MOD) in a past contest? I remember reading about it on your blog!

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

      If I remember correctly he made a missprint (10^9+9 instead of 10^9+7 or sth similar), not a conceptual mistake like the one mentioned above.

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

    so do ztxz16 and Kostroma.

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

I had this algorithm (which I did not implement) for solving 465C - No to Palindromes!. Is this a good approach?

Treat string as a number in base p.

Let left = 0 repeated n times
Let right = p repeated n times
while(left < right)
{
    int mid = (left + right) / 2;
    if(check(mid)) right = mid;
    else mid = left + 1;
}

The function check(x) tells you if x contains no digit > p and that it contains no palindromic substring of length > 1 (both of which can be done in linear time).

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

Not the contest that I expected and hoped... BTW, Palindromes are AWESOME! Why should somebody be bad with them?!

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

Here's a Brainfuck solution to problem A (reads and outputs as ASCII). The cells are divided into groups of two. The first cell of the group is 1 if the index is in range 0 to n and 0 otherwise. The second one contains input for that index — either 1 or 0.

The code:

>>,-                read n
[[->>+<<]+>>-]+     prepare cells of the second type
[<<]                go to start
>>[>,>]             read input
<<[<<]>>>           go to first value cell
[
    <<[->>+<<]>>    add values from last index
    >>              go to next cell
]
<[-<+>]<            if the index cell is 1 add to the result
.                   output result
→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Weren't E div2 — C div 1 pretests very very weak?

I see naive implementation solutions pass pretests!

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

I tried to hack this solution

by this case

2 0 0

but it gives me Unsuccessful hacking attempt

with this case variable pb will be used without initialization

how this solution pass my case ?

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

    pb will have junk value, but that would not contribute to answer, just that "break" will not be called.

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

How to solve div-2 D ?? I first tried to take all 6 combinations from 24 , that is 24C6 , clearly it isn't suitable !!!

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

When A,B are too easy and others are hard (div2), this will happen: I can see about 1500 rank difference between 2 users while both of them have solved 2 problems. The rank of the participants which solved 2 problems, starts from 400 and ends after 2000. This is a huge difference! I think this shouldn't happen.

Thanks :)

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

    In this contest, if you can solve only A, B which is common with Specialists and low Experts, your score will depend on your time, which isn't kinda bad. If you succeeded in solving C, or even D, E, those tasks will tremendously increase your rating because they are simply made for coders who has ideas and knowledge.

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

I misunderstood Div1-C problem statement :-( But problems are very interesting. Thank you for preparing this round :-)

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

For Div2, a and b was easy and c d e was hard. I have solved A and B but I got rank 1100... To many contestants solved just 2 problems and very big difference in same, two problem solvers.

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

Who else forgot to check if the cube side length is greater than 0? High five!! :'(

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

I got wrong for DIV 2 D , because I used float instead of integer while printing the cordinates , my programs prints the cordinates in exponent form in one of the test case and is judged wrong.

Did someone else also failed system test in this way before ? Link : 7710844

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

Why ratings update is delayed too much in codeforces after system test is finished? (while it's fast in topcoder)

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

    the relation between system tests and rating update is inverse. i don't know why .

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

    My guesses:

    System tests are delayed — because they need to add the newly added hacks to the final tests.

    Rating updates are delayed — because they are figuring out the cheaters in the contest.

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

Good question, thanks ^_^ waiting for editorials...

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

"Editorial will be up in an hour or two." is a Infinite Loop statement.

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

Can someone give some hints for Div1 C?

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

div2 probC

int n, p;
cin >> n >> p;
char *data = new char[n];
cin >> data;

runtime error. changed to

int n, p;
cin >> n >> p;
char *data = new char[1010];
cin >> data;

accepted. life sucks :(

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

Looks like tests in Div1-B are weak — I mean overflow. I have just written an int64 solution, which use values like maxCoord^4 (euclid length of vector product). And it's full solution. Is it difficult to create test to crash this solution?

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

    I think technically you have calculated a hash of the vector's length (have calced it modulo 264) and then you are only interested if two hashed values equal or not, so it seems OK.

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

These submissions are very much alike, aren't they? This 7704944 and that 7706248 And this 7713468 and that 7713301 too!

I'm a policeman:)

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

Oh my rating :))

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

very happy to get 284 point

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

can somebody explain div-1 C it is not so clear from editorial

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

    Didn't read editorial, but may be can help

    First of all, we can notice that after all transformation behind every digit will stay some sequence. Suppose we know these sequences for every digit [0..9], and for digit d sequence has length len[d] and value val[d]. Now, to compute result for input s, go though s and result = result * (10 ^ len[s[i] — '0']) + val[s[i] — '0'].

    Now we need to compute len[] and val[]. Let's use DP technique. Consider len[] and val[] calculated for some suffix of transformations queries [k..m-1]. How compute them for suffix [k-1..m-1]? Use similar ideas were used to compute result. Take query d->t, go through t and value = value * (10 ^ len[t[i] — '0']) + val[t[i] — '0']; length += len[t[i] — '0'];

    val[d] = value; len[d] = length;

    All these formulas come from Horner's method.

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

Country wise standings are updated. Sorry for the delay.

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

Round Stats

→ Reply
»
14 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Why my submission in queue for so long?

→ Reply