Блог пользователя Loud_Scream

Автор Loud_Scream, 2 месяца назад, По-русски,

Всем привет!

В понедельник 24 июля в 17:35 MSK состоится рейтинговый Codeforces Round #425 для участников из второго дивизиона. Как всегда, участники из первого дивизиона могут принять участие вне конкурса.

Это мой первый раунд. Хотелось бы сказать большое спасибо Николаю Калинину (KAN) и Алексею Илюхову (Livace) за помощь в подготовке задач, Ильдару Гайнуллину (gainullin.ildar), Даниилу Николенко (qoo2p5) и AmirReza PoorAkhavan (Arpa) за прорешивание задач, а также Михаилу Мирзаянову (MikeMirzayanov) за системы Codeforces и Polygon.

Участникам будет предложено пять задач и 2 часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

Всем удачи и высокого рейтинга!

UPD1: Разбалловка для этого раунда: 500 — 1000 — 1750 — 2000 — 2500.

UPD2: Поздравляем победителей! Разбор тут.

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

 
 
 
 
  • Проголосовать: нравится  
  • +123
  • Проголосовать: не нравится  

»
2 месяца назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Loud_Scream (предыдущая версия, новая версия, сравнить).

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +31 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

How to solve E?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

5 problems or 6 ?

»
2 месяца назад, # |
  Проголосовать: нравится -59 Проголосовать: не нравится

is it rated?

»
2 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

    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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Who is the hero of round?

»
2 месяца назад, # |
  Проголосовать: нравится -61 Проголосовать: не нравится

is it rated :p

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится -36 Проголосовать: не нравится

    Fuck off man -_- -_-

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится -44 Проголосовать: не нравится

      The guy was obviously kidding. Just downvote him if you don't like his post. No reason to swear.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится -37 Проголосовать: не нравится

        Seriously? I'm getting downvoted for trying to keep the level of discussion decent? Nice! :)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Its my first contest here, any suggestions!!

»
2 месяца назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

Is it rated?

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

deleted

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Хде разбалловка?

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

KAN 'THE GOD'of testing problems _/_

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

unable to register

»
2 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

unable to register

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Hope to become green.

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You have only 2000 pts for D?

»
2 месяца назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

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!!!

»
2 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

anyone else facing a long queue?

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My first Div 1 contest .

»
2 месяца назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

My first Div. 1 contest .

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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..!

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    if that's true than life's weird .

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    damn only noticed that now

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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...

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Too much lag make it unrated :D

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

LGTwins — Legendary Grandmaster Twins?? :DD

»
2 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Oh, that funny task about a bomb...

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

EDIT: Never mind

»
2 месяца назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I using Segment tree + LCA to solve this problem.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            2 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Isn't using DFS + LCA enough ?

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
          Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

          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)

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            2 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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?

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      2 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think we will use LCA and take care some cases

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

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.)

»
2 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Why ternary search doesn't work in task C?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    F

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 :(

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the fourth test for problem B?

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Corner cases for D please?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is D main algorithm LCA?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't want to write string simulation with c++ any more……

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe C is harder than D ?

»
2 месяца назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Problem E is pretty elegant.
Thanks to author.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Some hints please.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      consider those strings as a vector space in field Z5.

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится -18 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 месяца назад, # ^ |
            Проголосовать: нравится +25 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            2 месяца назад, # ^ |
            Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

            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)).

          • »
            »
            »
            »
            »
            »
            2 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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?

            • »
              »
              »
              »
              »
              »
              »
              2 месяца назад, # ^ |
                Проголосовать: нравится +6 Проголосовать: не нравится

              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

»
2 месяца назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Codes by cheaters of today's round:

1) 28850800 by Dipjal.Chhetri

2) 28846680 by pulkit.kapoor

»
2 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It took me some time to completely understand question B.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

System tests massacre on problem B!

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

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??

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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. :'(

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What is testcase 23 for problem B?

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Made such a stupid mistake in Problem B.

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

»
2 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Hope it won't be unrated for some reason

»
2 месяца назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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)

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Me trying to put the bomb in C

»
2 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

When the ratings will be updated?

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

1.28854301
2.28854337
Why submission-1 gets WA ?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

Hope Unrated :D Site was down for 20 minutes >:(

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Why aren't ratings updated yet?

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where's the new rating's ??

»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
2 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
2 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
2 месяца назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

....

»
2 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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).

  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.