Loud_Scream's blog

Codeforces Round #425 (Div.2) announcement
By Loud_Scream, 7 years ago, translation, In English

Hello Codeforces!

On July 24, в 17:35 MSK rated Codeforces Round #425 (Div. 2) will be held. As always, participants from the first division can take part out of competition.

This is my first round. Many thanks to Nikolay Kalinin (KAN) and Alexey Ilyukhov (Livace) for help in preparations of the round, Ildar Gainullin (300iq), Daniil Nikolenko (qoo2p5) and AmirReza PoorAkhavan (Arpa) for testing problems and also to Mike Mirzayanov (MikeMirzayanov) for Codeforces and Polygon platforms.

You will be given 5 problems and 2 hours to solve them. Scoring will be announced before the round.

I hope you'll enjoy my round. I wish everyone good luck and high rating!

UPD1: The scoring for this round is: 500 — 1000 — 1750 — 2000 — 2500.

UPD2: Congratulations to the winners! Editorial here.

Div.2 :

  1. LGTwins

  2. nick452

  3. Torta

  4. ez_zjt

  5. Parachutes

Div.1 :

  1. TimonKnigge

  2. Um_nik

  3. quailty

  4. dotorya

  5. Kaban-5

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

Comments Comments (174)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +31 Vote: I do not like it

Is it just me wondering about that "a." at the end. :P EDIT: Its removed, it must have been a typo. :)

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

How to solve E?

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

5 problems or 6 ?

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

is it rated?

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

I am curious about the process of choosing the author of the contest. does anyone have any information?

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

    I think when you offer contest, you get in queue, then coordinator checks problems and if they're good enough, contest is held.

    Btw, you have to have rating 1600+ to offer contest

    Check this

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

Who is the hero of round?

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

Its my first contest here, any suggestions!!

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

Is it rated?

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

    On July 24, в 17:35 MSK rated Codeforces Round #425 (Div. 2) will be held. :D

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

deleted

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

KAN 'THE GOD'of testing problems _/_

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

unable to register

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

    Same here, I pressed the "register" button, "entered" the contest, and it won't let me submit anything?

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

Hope to become green.

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

You have only 2000 pts for D?

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

    Well we had a lot of rounds where people whine about having a sharp difficulty cut off between C and a 2500pt D, so .... yeah.

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

    For me D felt easier than B(I am not sure about correctness though).

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

does any body have any idea about code b,test 4? my code get wrong answer and i'm doing the same as it said!!!

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

anyone else facing a long queue?

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

My first Div. 1 contest .

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

It took me a lot of time to actually get that this statement in Problem B

"It is guaranteed that the total length of all query strings is not greater than 10^5", means

"Sum of length of all strings over all queries don't exceed 10^5"

I guess the statement was not quite clear..!

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

    damn only noticed that now

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

    Actually this type of statement appears in many problems in the previous rounds too. Better be careful next time.

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

    that shouldn't keep you from coding your O(n) solution since reading will always take O(n)... So if you had 10^5 string with size 10^5, the problemsetter would already have to set a high time limit just for reading, which would allow you to solve the problem in the expected O(n) way...

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

    That is why you can ask questions in the contest. I asked it and got the answer straightaway.

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

Too much lag make it unrated :D

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

You won't believe how I tried to solve D :v

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

LGTwins — Legendary Grandmaster Twins?? :DD

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

Never try to hack out of bounds for cpp solutions. Lesson learned :/

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

Oh, that funny task about a bomb...

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

EDIT: Never mind

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

Intended solution for D isn't bruteforces O(n2),right?

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

    O(n^2) is too much. 10^10 operations would definitely take more than 2 seconds.

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

      Yeah,I know-I'm just surprised with 500+ acc on D.

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

    I using Segment tree + LCA to solve this problem.

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

      I did LCA with sparse table except it timed out because I managed to build the sparse table N^3 times...

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

        Sparse table could not update quickly :). Btw, I also using permutation to try all the possible ways.

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

          No need to update it, you can calcucate all the queries by picking an arbitrary root for the tree.

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

            Hmm, it really interesting :D. Btw, you also use HLD to find LCA ?

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

      Isn't using DFS + LCA enough ?

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

        I think it would be TLE, because it could be maximum n nodes for each shortest path.

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

          TrueLove You don't need to pass through every node on the path to the LCA, you can precalculate with a dp and find it in O(log n)

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

          No I mean in pre-processing phase, I used dfs to calculate the distance f[u] from u to root (which is 1).

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

            4k1502 I don't think so, because sometimes you don't need to travel to root to find the shortest path.

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

        yeah I thought about LCA but my solution was giving WA in pretest 6... I can't see why it wouldn't work -- fix a station A, get the LCA between B and C (call it L). If L equals A, the answer is 1. If L is either B or C, the answer is the minimum distance (A, B) or (A, C). Otherwise, the answer is the distance (A, L). I even permuted A, B, and C to get all possible combinations since the LCA runs fast. Why is that incorrect?

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

        Yes, LCA is enough, just check my submission to prove it.

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

      I think that vertex which is common to all paths between a,b,c is one of the lca(a,b), lca(b,c), lca(a,c).

      When you find this common vetex x you can print the max length of xa,xb,xc.

      28845144

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

    I think we will use LCA and take care some cases

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

      Didn't take care about cases and my solution works fine

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

        but did you use data structures?

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

          I used just binary lifting to find lca

          You can check editoral to see my algo.

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

Problem C reminds me of my junior high PhO times... I have a few nested fractions but have no idea about the whole problem (though there's a feeling that it's about convexity). (Nvm, I was off the track.)

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

    I think it is solvable by cht trick

    here is the accepted code using convex hull trick

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

Why ternary search doesn't work in task C?

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

    F

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

    Did you consider the situation when the people who goes to right are all in the left side of your mid point? However if you move the bumb into the nearest person the time may get less.I realized that after the contest is finished :(

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

Seriously waiting in anticipating for the hidden testcases to show their magic.Too many accepted for D problem.

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

What is the fourth test for problem B?

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

Here is why your B is wrong:

"and the character "*" (if there is one) with any, including empty, string of bad lowercase English letters "

A whole string of bad English letters, not just a character.

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

Corner cases for D please?

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

what's wrong with this code: http://ideone.com/zDWlW5 for problem B

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

    "*" can be replaced by 0 or >1 bad character(s) (not only 1)

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

Could anyone give me some tests on B.I WA on the test 12 so many times

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

    In B testcase 12 in my opinion checks,when * comes are you skipping all the bad characters of a query or skipping till length remaining of strings are equal. ex ab *dddd 1 dddddddddd Check this testcase answer should be YES.

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

      I got it.I really appreciate it

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

Is D main algorithm LCA?

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

Maybe C is harder than D ?

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

Problem E is pretty elegant.
Thanks to author.

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

    Some hints please.

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

      consider those strings as a vector space in field Z5.

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

        So what? This was obvious, but how to solve the problem?

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

          get the basis for those given vectors , if the query vector can be spanned by the basis , answer is 5n - b where b is size of basis , otherwise answer is obviously 0.

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

            Can you explain your solution (to be precise how do you implement Gaussian Elimination and whats the running time)?
            I am familiar with author's variant of Gaussian Elimination which works in O(n × m × min(n, m + q)).

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

            Why the answer is 5^(n-b)? 5^n — number of all possibilities. 5^b — number of all vectors in vector space. Why when one vector has k representations then every other must have k?

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

              consider any vector which can be spanned by the basis , there is exactly one way to represent that vector as a linear combination of basis vectors. Let v1, v2, v3, ... , vn - b be the non-basis vectors , let x = c1v1 + c2v2 + ... + cn - bvn - b , and let the query vector be y , since both x, y can be spanned by the basis , y - x can be spanned by the basis as well and in exactly one way , so the answer is number of linear combinations of non-basis vectors which is 5n - b

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

Codes by cheaters of today's round:

1) 28850800 by code_hard123

2) 28846680 by destinydrifter

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

Is it just me, or did anyone else find the wording of some of the problems confusing?

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

    It took me some time to completely understand question B.

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

    It costs me 3 submissions to get AC B. I think that '*' could only replace by a single letter.

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

System tests massacre on problem B!

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

When participating for 2 hours and only solved A :) EDIT: to solve B i needed to change '<' into '=' :(

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

How to solve C ??? It was a nice question.Thanks to the author

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

    It can be solved by CHT trick.

    Here is accepted code using cht trick

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

      Sorry for my ignorance but wath is CHT trick?

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

      Is It really the level of Div2 C problem ??? I still need to study a lot for solving Div2 Cs

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

        I saw some other solutions there was no cht in it. Maybe I took an overkill of the problem

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

Some HLD with Fast IO Passed D, While my one got TLE with scanf printf :(
What's the meaning of life :( :( :'(

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

I clicked on problem C from today's contest and then the statement was downloaded as PDF file! But with letter A instead of C! So weird, isn't it!?
Here is a screen shot of the file :
Screenshot_20170724_200338
Loud_Scream??

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

I really feel bad for getting wa in first just because of > instead of >=. I feel like crying, in order to submit it in less time i didn't noticed that. It is heartbreaking. :'(

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

    dude, it's just matter of time until you get used to it. i have been through something worse than yours. close to win in local contest 2 times, when they picked top 5 and i got rank 6, and the second times when they pick top 3 and i got rank 4.

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

      Thanks for your reply. Though I feel really bad for this but now i will try to do as many questions of this contest as possible.

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

What's wrong with my code? Problem B div.2 28847526

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it 
    Test :
a
b*bb
1
bbbbbb

    Your Output : NO
Expected Output : YES
    → Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is testcase 23 for problem B?

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

Made such a stupid mistake in Problem B.

I had to just move str.find("*") c++ function outside the testCases loop :(

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

Hope it won't be unrated for some reason

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

how is it that so many times some unrated guy takes one of the first few places? Don't div 1 coders get tired of creating accounts? Or is it really that genius people are being born nowadays at such a high frequency :v (in which case perhaps we don't need to worry about getting conquered by robots)

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

Such an elegant binary search problem,thank you for your contest:)

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

Me trying to put the bomb in C

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

When the ratings will be updated?

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

1.28854301
2.28854337
Why submission-1 gets WA ?

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

    I think this stp.length()-(ptr.length()-pos) is unsigned int, so when it is < 0 it becames about 4 * 10^9.

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

I solved problem D in 1980ms,and now I can't solve it another time.

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

I've got WA on test 57 in problem B:( Can someone help with my solution, please? Can't get where I have a mistake. TIA:) http://ideone.com/QluM6T

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

    Setting testy=0 within the loop gives you a couple more testcases.

    Link

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

      Oh, thank you very much!:) Now I have a full solution.

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

D should be rejudged ... Almost all HLD solutions will fail -_- Even submitting some AC solutions is giving TLE -_- Some solutions passed in 1965~1980ms -_-

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

What is the difference between these 2 submissions for D? -
28842403 — AC in 1965ms (In Contest)
28854711 — TLE on test 70 (In Practice) -_-

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

    It is called Law of conservation of rp in China.

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

Why aren't ratings updated yet?

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

    I think, they're banning cheaters now. At the end of the contest it was 5108 participants, now it's 5087.

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

I know its too much to expect & I should be patient. But tired of refreshing,please update ratings fast.

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

Doesn't LCA(u, v) = u implies that u is an ancestor of v? I am not able to figure out any mistake in my submission. Can anyone tell what could be the mistake? Thanks.

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

28845399
last permutation should be (c,b,a) am I right ?

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

    I think it is correct because (c, b, a) = (b, c, a)

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

Can somebody tell me why this TLEd for problem B. Code

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

    i got TLE to and then i used break ... i think you should try it

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

    even though you check for the bounds, you still search the whole string. Think of the case when the string is 10^5 characters long and starts with a '*'. And you have 10^5 queries of single character. For each query, you will run through the whole 10^5 string, because even though you check the sizes, you never break when you should. Thus, 10^5 x 10^5, TLE.

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

    The first loop FOR(i,1,n) is O(n) and the second loop in else statement FOR(i,0,ind-1) is of order O(|s|) when star is at the end. Therefore net complexity = O(nq). Hence TLEd

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

Wow, the one who took second place in Div2 writes such beautiful codes!

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

Problem B. One can write short solution with regular expressions in languages which support them. Only if language's regexes are fast enough to cope with time limits. I've found a solution in Ruby — Key_v2:28852992 (gsub -> global substitution), mine is similar but 3x slower (in Perl) — 28885266 (s///g -> same).

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

    libstdc++ regexp crashes on large examples, looks like it's the weakest implementation. Visual C++ regexp don't crash but seemingly fail at time limit, can't really test because VC++ is too old on CF. Maybe it's also worth it to test libc++, they don't crash but I doubt they will pass TL too.

    So basically C++ regexps fall short for this task.

    → Reply