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

Автор fcspartakm, история, 7 лет назад, По-русски

Привет, Codeforces!

16 декабря 2017 года в 14:35 MSK состоится очередной раунд Codeforces #451 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Обратите внимание на необычное время начала раунда!

Раунд будет рейтинговым.

Этот раунд проводится по задачам муниципального этапа Всероссийской олимпиады школьников по информатике 2017/2018 года г. Саратова. Задачи были подготовлены силами Центра олимпиадной подготовки программистов Саратовского ГУ. Убедительная просьба к участникам муниципального этапа в Саратове не принимать участия в этом контесте.

Хотелось бы сказать большое спасибо Григорию Резникову (vintage_Vlad_Makeev) и Николаю Калинину (KAN) за помощь в подготовке задач, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также Алексею Рипинену (Perforator) и Роману Глазову (Roms) за прорешивание задач.

Участникам будет предложено шесть задач и два часа на их решение. Разбалловка 500-750-1500-1750-2000-2500.

UPD Разбор

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

  1. Namys

  2. MSeashell

  3. zhouyidong

  4. ITMO.MansNotHot9

  5. meoconn

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

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

A friendly round for Chinese! :)

But, I registered for it and it doesn't show that I'm out of competition. Why?

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

I really think that CF had a difficult time, but at least last 3 contest had a decent queue and nice problems. I think CF is going in a right direction, mentioning the number of contests.

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

Last week, I saw that c.f. Round 451 would be held at 18:35 MSK. Why it comes to 14:35?

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

MikeMirzayanov , there is a clash between tomorrow's atcoder match and this , can something be done? , I dont want to miss either one of these! fcspartakm

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

    Unfortunately, we can not move the round because of the onsite high-school olympiad and Russian AI Cup Final Round. Usually we avoid such clashes but this time we can't choose start time.

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

Nothing is mentioned related to rating.

»
7 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Is it -rated?

»
7 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

MEOWWWWWWWWWW~

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

May as well be a nice warm-up before ECL Final :)

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

Will it be Sunday tomorrow in Moscow or it is just typo ?

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

GOOD LUCK !!!

»
7 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

Is this contest rated? lol

»
7 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

Not cool it overlaps with arc tomorrow. Why so early?

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

Just curious, is that a rated contest?

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

CAn yUU please, SiR, stop deleting my "is it rated?" comments/censor me ? We live in democracy which means I can freely act like a retard , not in communism where i would be put in some gulag.

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

    No

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

    You have the freedom to post senseless comments, and everyone else has the freedom to vote it down into oblivion. This results in you being hidden for negative feedback.

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

please make sure the time limit is enough

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

This is my frist contests after cet-4 , best wish for my cet-4 , besides i want to rise my points!

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

Hope for short statements <3

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

When you open Codeforces for no reason and you see a contest is about to begin in 30 mins :P. I always get an email for contests saying "Attention! Unusual start time" but this time when the timing was really unusual I didn't get any email. Not cool Codeforces :(. Anyways, it's nice to see so many upcoming contests lined up before New Year.

"The scoring distribution will be announced later." When?!

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

Scoring distribution please?

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

Good Luck!!! Удачи!!! ;)

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

Nice time start point for me:)

»
7 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

The round was the best for me

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

Very nice difficulty distribution of problems.

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

Liked the fact that there were no long queues. Keep it up.

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

is D some directed graph problem

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

    I think that greedy will work fine here. Remove the last alarm clock while there is at least k alarm clocks in segment.

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

      Did you use binary search in your solution?

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

        No binary search is needed. Since times are <= 10^6, you can create a vector of bools from [1, 10^6] and iterate over windows of size m to simplify implementation.

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

    D was DP+ segtree After sorting.. when u see that u are at a time ti such that there are >=k alarms within time ti-m+1, just turn of the ith alarm. maintain the sum using segtree

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

    Greedy on time and sliding window may help you.

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

    I think problem D is two pointers + data structures

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

How to solve F?

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

    If the length of c is n, the maximum length of a and b is n or n - 1.

    With each possible length of c, we only need to check for 2 cases.

    To calculate a, b, c in each case, we can use Hash. The hash value of a + b is the sum of hash value of a and the hash value of b.

    And remember to check if there is some 0 at the beginning of a, b, c when the length of a, b, c is greater than 1.

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

      Can you please explain, how are you using hashing? I am not aware about the concept of hashing. Also, how can you say the hash value of (a + b) is the sum of the hash value of a and the hash value of b?

      Thanks.

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

How to solve problem D?

I thought of segment tree solution but was unable to get it accepted. :(

Edit -

My basic idea was to assign 1 (in the array) to the minutes when alarm clock rings and in each iteration, find the sum from i to i + m minutes, say it p.

If it is less than k, then no problem. Otherwise update the array from range L to i + m and make each element in it 0. It can be done by lazy propagation and about finding that value L (from where we have to update the range) , it can be done by simple binary search.

Can anyone tell me, what I was missing or was I wrong with my logic?

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

    I solved it using BIT tree. Just maintain at each index how many clocks are there and while checking for any time i just see the number of clocks present between i and i+m time interval and if it is greater than or equal to k just update index i+m with negative value equal to abs(val[i+m]-(k-1)).

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

    I think it's somewhat greedy but not sure about that!

    What i did was that first make an array of alarm point(as there are only 1e6 alarms and all distinct!) and then take a window of size m and if it contains more than k then i start removing from last on alarm(as removing this makes sense and help to optimize our answer for the next step). Finally slide the window and calculate the number of alarms thus removed.

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

Problem D. Change the statement without seeding an anouncement?????? consequence -> consecutive

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

Hints for D? I was thinking binary search but am not sure and couldn't get it to pass

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

How did people manage to solve D in 5 minutes? =)
Is it some kind of a standart problem?

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

    A sliding window algorithm did it for me. Hope it passes the systests.

    UPD: It did. XD

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

      I know what sliding window is, but I don't know how to solve this problem.

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

        use greedy technique for that. Delete last alarm clock.

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

          Why is it correct to delete the last one?

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

            Because if another alarm clock intersects with the previous ones, it's better to remove an alarm ending at an earlier time instance compared to one ending later.

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

            Cause, that will help the most. The first alarm clock will be the first one to leave the span of m minutes. So, there may be a case that there exists exactly k-2 alarms in the range starting from last alarm clock.

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

            Cause that clock will be part of more up coming window.

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

This round is true Div.2 round: when most of the problems are solvable for Div.2 participants.

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

Why change the statement and not send a annoucement???? consequence -> consecutive Consequence ??? How can i know this...

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

Hey, this submission(33299805) says runtime error...while checking with Diagnosis in custom test, its says,

p71.cpp:57:24: runtime error: member access within misaligned address 0xbebebebe for type 'trieNode', which requires 4 byte alignment
0xbebebebe: note: pointer points here
<memory cannot be prin...
Runtime error: exit code is 1

I don't understand.. Why this happened? it's ruined my mood & I have left contest.. Now, there will be a disaster in my rating. :(

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

Lol, can someone(MAYBE CF ADMINISTRATION) explain me why I can`t hack one submition twice?

I hacked once and got an "Invalid input" because of the EOL in the end. After I corrected my test CF says "Submit already challenged". LOL, REALLY??? So then I must know if the EOL is needed there before hacking????

Due to this issue I didn't get 200 points on hacks.

THX, CF.

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

What is testcase 7 in F ???

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

EDITED

In Problem-E, my first submission got WA in pretest 9. But, then I relocated my long long ans = 0 variable at the top of main function and got pretest passed after submitting. Why did that happen? I was looking for the bug for such a long time, maybe like 30 minutes. Then I just gave up and then did the above thing on a whim and got accepted. but why?

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

    declaring long long ans in main might have garbage value. oustide main is 0

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

    maybe you did ans += something; before there is any value on ans, the value of ans before declared, inside main is random, CMIIW

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

    You also changed your comparator function.

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

      The change in comparator function looks insignificant to me. Either way, the sorting will be the same

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

Is greedy work for problem E?

»
7 лет назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

It is rated?

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

I am getting Wrong answer on pretest 8 for 2nd problem (B) My submission

Can someone please help? I used the Extended Euclid algorithm to solve it.

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

    There is another "NO" case.
    Suppose "X" is non-negative and "Y" is negative.
    You obviously want to make "Y" non-negative by subtracting numbers from "X", right?

    Here, there is a possibility of making "X" negative even though you manage to make "Y" non-negative.

    In short, "X" and "Y" cannot be both non-negative in this case.

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

Speed up this system testing, I can't wait to see how many problems will fail from the 6 : |

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

Very Good Contest! Great thanks to the author!

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

I got some issues hacking. From the second hack, it always navigates to the hack summary page without the hack popup where I can enter my hack case.

So I am not able to hack others in the same browser. I have to switch to a different browser or use a different computer. Did it happen to others?

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

My solution (33309422) for problem C gets wrong answer on pretest 1. Whats wrong here ?

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

    You have to print how mnay lines of output you have

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

      Thanks. I feel so terrible for such a silly mistake...

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

        It happens to all of us at some point; if you ever see a problem with a VERY early pretest (like 1, 2, or 3), you can use the fact that CF will judge the example test cases as the first pretests (at least in my experience they always have). So if you fail test 1, you can diff check with the sample output and find out that you have a formatting error.

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

      Yep, I too didn't do that in my first attempt! Got a WA. :/

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

can someone please look into my code why it is giving RE on sample test(3).

code : https://ideone.com/8dFo4E

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

    One doesn't simply code trie when the string lengths are  ≤ 10.

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

      yeah but i have wasted a lot of time in it! please help.

      btw i didn't think that trie is making problem it's only when we have a string of length 1. if i remove all those then it runs fine. And when there are string of length 1 then builder is not working correctly. please help!

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

UPD: I have changed my MIND.. if you want to downvote me then you are welcome :)

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

IS O(sqrt(ai)*n) sufficient to pass the tests in problem E ??

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

    sqrt(ai) ~= 3.16*10**4 (max)

    n = 2*10^5 (max)

    no of steps ~= 6.3*10**9

    extremely low chance of passing, unless the constant factor is really low

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

I think the diagnosis process makes the system test so slow. But I am pretty sure that many of the contestants do not or less care the diagnosis result. So this is just my small suggestion, what about running the diagnosis only when the contestant wants? For instance, by clicking run diagnosis button on submitted code. This may reduce the server load a lot, making system test faster, and contestants can know their ratings earlier, which most of the contestants care about. Can I share your opinion?

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

My first Div.3 contest!

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

Good contest, comprehensible statements, short systest pending time.

Many thanks, although I lost my perfect chance to solve the last problem for the first time, just because I forgot checking the leading zeroes :<

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

That moment when Div.2 E is easier that Div.2 D... like way easier.

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

the E task should be D or even C

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

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

Can anyone plz point out my mistake in E, I wrote a pretty easy solution- http://mirror.codeforces.com/contest/898/submission/33306957

Thanks

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

My solution for D gives runtime error on testcase 3 but runs fine on my system http://mirror.codeforces.com/contest/898/submission/33302108 Help please!!!

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

For problem C I think my output for the first test case is correct ,can anyone tell me why my first test case output is wrong.

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

I really don't think this round is good. The rates of algorithms used in the contest are not in equilibrium. 3 problems(ABC) don't need any skill or algorithms, and C is just grand-grand-great simulation. And 2 problems(DE)are just greedy, which doesn't need advanced algorithms. Even DP and graph theory don't exist in problems. And the quality of the problems aren't high as well, here "quality" means the well-situated difficulty for Div. 2. (Because I can only AC around 2 problems before, but this time I can do 4 if I have a little more time)

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

    I'm beginner and I'm glad to see such problems like A or B. No one in the entire world started walk right after birth. Those problems actually makes me think that I can solve more then just 1 or 2 problems in the next contest. And yeah, it keeps me motivated, and don't give up from CP. If the contest was too easy for you, move to div1 and try to beat tourist:)

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

      Actually I don't think the round is too easy for me. As what I said, I can do 4 if I have enough time. I am still far from AK(solving all). But I just think it's much easier than most of the div2 contest before:) Maybe the round still has an advantage that it gives us encouragement. Maybe what I said in the last discussion is not fit, so I pay apologize about it. But if all of the div2 contests on codeforces are "encouraging rounds", what will it be like?

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

Can someone discuss their F solution ?

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

Good work! Very interesting tasks.

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

%zu printf specifier is not recognized... this cost me an accept in C :(

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

For Question B, if we do brute force according to editorial, we will get TLE on test 49 for Python...

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

Hey guys, I didn't do well yesterday because I was stuck on Problem C for a long time. I used std::set to store the telephone number, and I iterated the set to check if they were suffix to each other, and I delete the elements while iterating and I got runtime error. Can anyone please tell me how the set works while erasing the elements. Thanks a lot.

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

For Problem F,I use unsigned long long without modulo (let the hash overflow naturally) and Rabin-Karp Algorithm to check whether the answer is ok,the verdict shows TLE on test 77.However,if I add a modulo which is only 23333 (only about 2e4) and use the same way to check,it got accepted in only 78ms.So can I assume that you intend all the hashing algorithm without modulo to fail?I don't think it's good for a hashing problem,especially when I use Rabin-Karp to check and it still can't pass.:D

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

    I think, during the contest someone passed pretests with overflow hash and someone just hacked this solution, as a result a counter-test for overflow hash was added in the final test set.