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

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

И снова привет, Codeforces!

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

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

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

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

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

UPD Разбалловка 500-1000-1500-1750-2250-2500

UPD Дорешивание, виртуальное участие, а также возможность просмотра решений и тестов будут отключены до окончания олимпиады в Саратове через 2-3 часа. Надеемся на ваше понимание. Разбор также будет опубликован после конца олимпиады.

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

  1. Spyt

  2. taew

  3. Fop_zzZ

  4. kabuszki

  5. Join_VNOI_Discord

UPD Разбор

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

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

Эх, а имя vintage_Vlad_Makeev с анонса прошлого раунда так и не пофиксили. Или его действительно зовут Григорь (что-то между Григорием и Игорем)? UPD. Пофиксили, значит, не Григорь.

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

You wrote two consecutive rounds! Wow!

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

You wrote two consecutive rounds! Wow!

UPD Never mind, I didn't know that the rounds were based on Olympiad. Sorry.

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

This round is the based on problems from the same contest as today's contest. Does this mean the round, Div 2 in particular, will be of similar difficulty to today's round? It was a great round (personally anyway), don't get me wrong, but it was definitely easier than normal.

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

Why is it so late?

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

Пересекается с олимпиадой Иннополис

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

In this month will be some codeforces round

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

1:35 PM in Hanoi.

It would be good if my class wouldn’t start at 3:00 PM... :<

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

i hope that this round's problems will be as difficult as the previous round's problems

so as the queue

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

Нужна помощь по задаче (не этот раунд). Если есть кто-то, кто может помочь, пишите плз

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

First contest without Russians?

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

An UTC+8-round :)

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

1:35 AM in Cuba , nice!!!

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

I really hope this round will be better than the round before.

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

Six problems? Sounds good. And the time is quite friendly to Chinese participants :)

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

The classic: Is it rated?

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

All right... It seems that today's problems are much better than yesterday's. I like this round very much. -- Though my B was hacked.

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

6.35am(UK) is so early XD

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

    the last contest in Cuba was at 6:30AM and this contest is at 1:35AM , very early XD

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

asd

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

apparently the link described in the rules,

http://codeforces.net/blog/entry/456 and http://codeforces.net/blog/entry/4088

was not found on Codeforces's server on my end. anyone know how to access this?

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

wh2001_ZY will solve all problems in the contest!He's the best!

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

whan I want to hack, I couldn't see other's solution .

why????

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

    You lock your solutions in the dashboard before hacking other solutions, but beware, after locking your submission you won't be able resubmit any solution after

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

How to solve D and E?

I got no idea for D.

For E, though I was not able to submit because of too much code writing but my idea involved range min query and lazy propagation.

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

    I think E requires some clever use of data structure like set . Couldn't get AC though because of time but I think my approach is correct.

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

    I solved E simulating the array with set and map

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

      Yes. That's what I did . but got wrong answer in pretest 7 . Finally when I corrected my solution , Contest was already over. screwed up badly !

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

      Hi , TwiceBig I was not able to solve E in contest timings Will you share your thinking and solution , that would be really great.. I am attempting the problem now, your method will surely help..

      Thankyou.

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

        Hi. Well basically what I do is simulate the array using a set. For that I store a pair of integers. First frequency and second what position of the array it is. Since set has data stored by minimum, I store The first value as negative. Also I have an extra map for helping me in the merge. While there is something in the array ( the set ) I erase the first value of the set, cause it is the next range that has to be erased. When I remove an element I search the left and right element with lowerbound in the map. And if left and right has same value I merge them. So I have to remove from the set the left and the Right. And add the new pair I just merged. And update the map. And that's all. Hope it helps

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

    33347025, got AC with Disjoint Set Union. Each connectivity component — is segment with equal elements. I kept this components in set, selecting component with maximal size. Time complexity approx O(N log N)

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

20 31 31 30 31 30 31 31 28 31 30 31 30 31 31 30 31 30 31 31 29 Взлом для B

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

I thought I finally found the bug right before the end, but still WA on pretest 4! What's pretest 4 on problem D?

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

how to solve C? my recursive solution fails on pretest 5 :|

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

    Make cases for each remainder of n with 4.

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

    If you want code and some help, you can have a look here.

    Code — https://paste.ubuntu.com/26200030/

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

    I just found a segment of numbers which sum to (sum_of_sequence) / 2

    Not sure why it works, and if it's correct(did pass the tests though)

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

    I just got my solution for problem C accepted with only linear loops (O(N) time complexity), but my approach looked pretty weird I think. I did think of modulo 4 but I didn't write code that way. Can anyone suggest or show me proof of correctness? http://codeforces.net/contest/899/submission/33346265

    Get the sum of the first M elements. Get the absolute difference of it and the sum of the rest. M does not exceed N/2.

    Get the sum of the last M elements. Get the absolute difference of it and the sum of the rest. M does not exceed N/2.

    Get the sum of the middle M elements. Get the absolute difference of it and the sum of the rest. M = {N/2 - 1, N/2, N/2 + 1}.

    I wrote a little code brute-forcing all the cases and notice that with some N there exist solutions where the middle elements are chosen, and with some other N there exist solutions where the first (or last) elements are chosen.

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

Any hint on what's 7th pretest in E?

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

Очень классные задания!!!! Спасибо, было ооочень интересно решать))

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

in the end of contest, i tried open hack attempt page but it not opened two min

so sad..

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

Another nice round. It's harder and suits Div.2 better though. Cheers. ;)

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

Problem D. Shovel Sale ********* Note that it is possible that the largest number of 9s at the end is 0, then you should count all such variants. **** if they neither give n<5 in pretest and nor in announcement then standing will be completely different.

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

i didn't like the recent contests on this site :)

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

What was your Hack test case for B?

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

Thanks a lot for the suitable contest time. Due to the inconvenience of the time zone, it's really hard for me to find a CF contest to enter when I am not sleepy...

// Although today I realized contests wouldn't become easier for me when I'm awake :(

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

Hints Clues Solutions anything for D?

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

The system testing is starting now, but upsolving, virtual participation and viewing solutions and tests will be disabled till the end of the olympiad in Saratov (around 2-3 hours from now). Hope for your understanding.

UPD: Everything is up now.

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

I noticed the lack of graph, DP, combinatoric and geometry problem in this year Olympiad.

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

what is C pretest 5?

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

DIV2 A IS SO HARD TO UNDERSTAND PROPERLY DUDE!

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

Wrote a simple stack solution for E after contest. I would be so suprised if it passes, but I dont know why it shouldnt pass. Is it possible that E is this easy? Edit: No its not, I didnt real statement carefully lol.

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

    I think that order of removing matters, without handling that I got wa on pretest 7.

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

      Order does matter, but I dont think it will be problem in my solution. We will see soon.

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

Everybody in Russia uses Gregorian calendar. In this calendar there are 31 days in January, 28 or 29 days in February (depending on whether the year is leap or not)... People like me have no idea that leap year means 29 days in Feb....

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

when wil be rating changes

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

How to solve C without knapsack?

My approach: if n=2, just like pretest. else:

1.Put n in set 1 and n-1 in set 2.

2.For each other element (n-2,n-3,...,1), just check (in descendig order) if it's better that the element goes to set 1 or 2.

How to prove that always works?

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

    I solved it using a simple approach.
    find the sum of integer from 1 to N.
    if sum is even number then answer will be 0 otherwise 1.
    in both the cases method of finding the numbers are same,do the half of the sum of 1 to N and store it in a variable called SUM.
    then start from (i=N ; i>=1 ; i--) and do this if (SUM — i >= 0) then subtract i from SUM and push_back i into you answer.
    you will get your answer vector.

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

      I also thought of same logic but could not submit correct code in time . btw how do u prove your claim?

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

        I wrote down some test cases on copy and checked it manually...
        you can think like this if you are subtracting a number from SUM and then your SUM becomes less than zero it means that you need to subtract a number which should be smaller than current number and i am going from N to 1 so it is sure that i will get that number.

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

I just wonder, if someone can tell me why I am disqualified?

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

    probably because you cheated

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

    Because you, Birjik, used fresh account to take part. It's ugly, unethical, disrespectful to me and the community.

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

      How did you know? There must be other users using fresh accounts too.

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

      I wonder how did you detect his fresh account through his submissions?

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

      First of all, it's not Birjik even though we do share same template code.

      Secondly, my real username is banned from CF (due to I cheated once a few years ago) and I gave you my sincerest apologies for that (several times), and asked to be unbanned in my real account.

      After several attempts, I even changed my PC and could somehow login and was eligible to participate in contests from my original account, but some times later, I couldn't even login into my account. After 5 mins of logging in, the site takes me out and I have to login again. Moreover, in most of the times I can't even register to the competition (due to my account was banned).

      I already noticed organizers about that issue. Didn't receive any reply. Okay.

      Well, so I decided to create my new account since I can't normally participate in competitions from my original account and this decision was made by me not because I do wanna cheat, I just don't have any options.

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

How to solve problem-F?

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

I saw some submissions for D with Digit — DP. Can someone explain their solution using Digit — DP ?

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

for problem C: I noticed that the difference between every two adjacent numbers is 1. So if n is even, there will be two situations:if n/2 is even, answer is 0, or answer will be 1; Similarly, if n is odd, there are also two situations:if n/2 is even, answer is 1, or answer will be 0;

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

What??? Is it semi rated???

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

Good contest, the problemset was perfect. We want more contests like this.

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

Hi,MikeMirzayanov,can you tell me why I got disqualified? I didn't share code with anyone else.

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

    Because you created fake account to participate bro. It's ugly, unethical, disrespectful to me and the community.

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

    Because you (maybe a group of people, and I'm not sure who) used a fresh account to take part. It's ugly, unethical, disrespectful to me and the community.

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

    I want to know why I got disqualified,too.I didn't share code with anyone else,either.

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

      My friend eselppa got disqualified in yesterday's contest too, he solved all problems by himself, he didn't cheat, I can prove it. The reason why this account's ID is very similar with mine is that he wants to play a joke to me. That's not my account.

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

    I found a new problem ... How many "It's ugly, unethical, disrespectful to me and the community." in the replies of this comment. since the answer may be very large print it module 10^9+7.

    UPD : You also have to consider the occurrences in the replies after this reply.

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

      Stop making jokes about cheating, it's ugly, unethical, disrespectful to me and the community.

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

      Good god how did this become a memeful copy-pasta so fast dude. I mean it's ugly, unethical, disrespectful to m-

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

Why I can't submit now?? The contest is over and the system testing has finished ...

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

hello in your contest in b problem you gave test cases that there is two contiguous leap years but its impossible in real (one of them is test case 13) please correct it

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

    Leap years are ones with 29 days in February not 28.

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

      my bad :(

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

        Look at all the people who failed problem B. They all did same mistake as you. It's because of the problem statement, January, 28 or 29 days in February (depending on whether the year is leap or not) , which gives an idea that correspondly leap has 28 days and not leap has 29 days.

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

Когда не сдал D

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

Hello, I found a very weird bug in my code for problem E. It works fine for many test cases except for the case when n = 2 and the 2 numbers are distinct. I checked on my local machine and it gives the error.

*** Error in `./a.out': munmap_chunk(): invalid pointer: 0x00005613cbdd2788 ***

Checking on gdb, I find that the pointer majt remains the same as mait, even though I'm doing majt--; which should make it ma.end() if we are removing the first number (Note that this works for other test cases, i.e. n!=2, even for n=1). I'm unable to figure out why. Any help would be appreciated. Thank you.

Code ID: 33351982

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

Well,the time is best for Chinese!We always had to stay up late for the CF round :(

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

Why are submissions not being judged?? I submitted 4 hours ago and it still writes "in queue" as status. :/

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

    You are erasing from set at the same time you are iterating over it. So when you delete an element the inner structure changes. You should create a temporal set and erase from it

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

в условии написано "в феврале 28 или 29 дней (в зависимости от того, является год високосным, или нет)" значит из условия понятно, что 28 дней високосный, а 29 не високосный, как бы соответствие между ними но на самом деле все совершенно наоборот

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

Wrong answer on test 7 on problem F. Anyone have any idea? I am unable to find my bug. I have tested several cases but couldn't find anything.

Here is my submission 33357864

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

[Deleted] I post it on the wrong topic.Sorry.

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

What's problem with this E code? 33382017

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

Hi,MikeMirzayanov,can you tell me why I got disqualified? I didn't share code with anyone else.Please give me a reason.

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

    Because you, czr, used fresh account to take part. It's ugly, unethical, disrespectful to me and the community.

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

      Oh, you're really ugly, unethical, disrespectful to me and the community. As far as I'm concerned,you,it's your third fresh account! You should be banned by MikeMirzayanov in no time. And I can't imagine a more ugly and unethical behaviour than using a fresh account to point out that I used a fresh account!

      What's more,I do not use a fresh account and it's the first time I participated in a CF Contest!

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

I've been stuck for ages... anyone know what test #33 was on div2E? http://codeforces.net/contest/899/submission/33345602

My answer is 1 + the correct answer. :(