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

Автор _kun_, история, 5 дней назад, По-русски,

Всем привет!

Летняя компьютерная школа (ЛКШ) — это летняя школа для учащихся 6-10 классов, увлеченных программированием. ЛКШ ориентирована в основном (но не только) на школьников, участвующих в олимпиадах по информатике — от начинающих до участников международных олимпиад. ЛКШ проходит в две смены (июльскую и августовскую), в каждую из которых приезжают около 200 школьников со всей России и из-за рубежа. Более подробно об ЛКШ можно прочитать на lksh.ru

Сейчас идёт августовская смена Летней Компьютерной Школы и 11-го августа состоится традиционная командная олимпиада ЛКШ. Мы рады представить рейтинговый раунд на её основе!

Раунд будет рейтинговым для обоих дивизионов, пройдёт в 11.08.2018 16:35 (Московское время), в каждом дивизионе будет 5 задач и 2 часа на их решение.

Задачи раунда и олимпиады были придуманы и подготовлены преподавателями ЛКШ: izban, achulkov2, Schemtschik, i_love_isaf27, senek_k, asokol, WreckingBall, burunduk2. Также спасибо Dembel за помощь с организацией олимпиады.

Спасибо _meshanya_, burunduk2, gritukan, niyaznigmatul, manoprenko за тестирование задач!

Спасибо MikeMirzayanov за системы codeforces и polygon!

Да, мы знаем о том, что контест пересекается с ProCon Junior на codechef. К сожалению, учитывая расписание ЛКШ, а также приближающийся финал VK cup, мы ничего не можем с этим сделать =/.

Желаем удачи!

UPD: На раунде будет одна интерактивная задача для обоих дивизионов. Пожалуйста, прочитайте пост об этом здесь: Интерактивные задачи: руководство для участника.

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

Div1:

  1. Marcin_smu
  2. Radewoosh
  3. Swistakk
  4. Panole233
  5. ko_osaga

Div2:

  1. Onuz
  2. aurelio
  3. usachevd0
  4. jebouin
  5. etiennerossignol

Upd Спасибо за участие! В связи с проведением вк-кап пересчёт рейтинг состоится немного позднее обычного.

Upd Опубликован разбор!

Можете также обратить внимание на неоффициальный разбор, который написал neal.

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

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

Ok so now CF will host contests prepared for middle school students. Kill me now!!!!!!

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

    Don't underestimate the complexity of this contest :).

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

    I hadn't been surprised if you would solve nothing from a SIS hard olympiad :)

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

    Says the guy who has solved only two problems in CF and has rating <1500 (No disrespect to lower rated guys but being that arrogant calls for such a response)

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

    Why underestimate middle school students? There are quite a lot middle school students who rates more than 2400 on Codeforces.

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

This will hopefully be a good contest for those of us training for olympiads :)

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

Which problems are going to be based on the olympiad?

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

But Is It Contributed?

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

Or Is It Rated?

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

The start time changed from 16:05 UTC+8 to 21:35 UTC+8... At least I can go to bed before the next day.

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

    I thought that I can participate in this Round before I noticed that the start time had changed.

    The disadvantage of training during summer vacation in boarding schools.

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

mathforces?

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

Hope no server/hardware problems will occur this time :)

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

round #503 and error #503(unavailable Gateway).. another coincidence??... hopefully..not this time :)

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

    Shouldn't it be 502 Bad Gateway & 504 Gateway Timeout?

    (UPD: Comment of hrOarr is fixed)

    <del>(BTW, why didn't the server down in Round #500(Server Internal Error)?)</del>

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

      hope #service unavailable fact... btw error may b unpredictable...

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

      I saw 500 error yesterday, it lasted for a very short time, then changed into 502 error, and then the announcement.

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

        I just said the truth I saw that had already happened. I also hope that it will not happen again.

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

I guess despite the original contest being IOI styled, this round will be CF styled, as always?

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

Hope to be a good contest as it seems to be, wish you all guys better ratings...

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

    You don't know how much I love you, when you down-vote for nothing!!!

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

      I wouldn't recommend you posting here without any serious reasons. Any controversial and/or "meaningless" comments are very likely to be downvoted.

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

        I don't know how those memes can be serious, anyway I won't comment anymore...

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

Great to see izban is one of the problemsetters!

»
5 дней назад, # |
Rev. 3   Проголосовать: нравится -21 Проголосовать: не нравится

Are there any shared problems between both divisions ?

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

Пересекается с днём физкультурника в Архангельске

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

Please provide some more tutorial about an interactive problem.

Please...

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

Everybody jump on the downvote train!

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

Можно ли участвовать, если ездил в ЛКШ.Июль?

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

Great round! The time really fits me.

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

As the prizes of the previous round is postponed, will there be prizes in this round?

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

I hope time limit will be enough

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

Trains of Downvote.

metoo

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

I hope it won't be unrated like Round #502 (Laugh

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

this blog full of downvote comments

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

Is it UNrated like round 502?)) Just kidding, is it rated?

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

_kun_ Is it Mathforces?

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

Why are you people downvoting every single comment? Just for fun? It completely ruins the whole discussion, because if anyone says anything, he will get downvoted to hell.

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

    Also for reading most of the comments I need to click on "here" all the time. Sign of something special gonna happen in this contest I guess (can be negative/positive) ;)

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

Пересекается с Codeforces Round #503 (по олимпиаде ЛКШ)

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

Is it disrated on downforces?

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

Why most of the comments in this post are hidden?I can't find the reason why you downvote so much.(Because of this I upvoted all the comments)

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

It is a shame all comments have a huge number of downvotes, I hope people leave more constructive comments and vote more logically.Please, don't destroy such a great community !

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

I challenge you to Downvote me..

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

I challenge you to upvote me...

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

Why are all comments downvoted?

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

    Someone made a bunch of alts to downvote, probably. If not manually, I'm guessing someone used a bot. (I'm surprised codeforces doesn't have some countermeasure this)

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

      Codeforces uses reCAPTCHA to prevent bots, but it can be passed automatically with little money.

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

        Hosting VK Finals now, I do not have enough time to investigate the situation. But definitely they are not simple bots. Probably, it is some kind of flash mob or hacked accounts.

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

          So how to deal with these downvotes?

          Keep them polluting the contrib. of everyone?

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

please delay/starts it 15 min later than scheduled time because there is a contest at atcoder also.. please this is a request.

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

Downvote is raining Here ...!!!

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

Hi

I made 10 accounts in Codeforces and downvoted some comments here, and of course others saw that and kept downvoting the comments. Some of you may already knew this but my purpose was to show that lots of people here are just dumb followers and they don't have any brain to decide what to do, they just copy others' actions.

So to the guys who got downvoted in this community or as some guy in other blog said are not a clown to make others laugh, don't worry, it's not your issue.

Thank you for being idiots.

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

    Did you know that you are so funny?? That's not being an idiot, when someone sees everyone is downvoting him/her, he/she starts downvoting others... you are the only idiot here... Hey idiot, now go and make more accounts and downvote me..

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

      They did not claim to be funny.

      when someone sees everyone is downvoting him/her, he/she starts downvoting others...

      Why would that make sense?

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

        Mob mentality/conformity, people follow the crowd, when they see a lot of downvotes they are already ready to agree with the majority. I think this is a real effect, but I don't think that downvoting everyone to "prove a point" causes any real change... it is just an annoyance

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

          That is not what I asked. Tour_guide claimed that when someone is downvoted, they start downvoting others.

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

            Sorry, I misunderstood. I suppose he means that person gets very mad and wants to take it out on others, but I think most of the codeforces community is better than that

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

        Why not?? Don't you feel bad when everyone is downvoting your every single comment?? Less people can accept others disagreement and don't react...

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

          I might, I just don't see how downvoting others would help whatsoever...

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

            I don't really know and can't explain, something instinct, I think. maybe you're right...

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

    So do you think this is the right way to tell them they're wrong?

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

    Good job. Most posts above had 50+ downvotes even though you casted only 10. Time for people to wake up.

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

flood of downvotes!!

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

Why someone was so bored to downvote everyone?

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

I have short by the way.

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

That one person who'd like to comment but too afraid of the downvotes.

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

Can i get more than 100 downvotes ?

I'll appreciate it :D

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

If you want to see the comments in this thread without clicking on every link or you have a strong will and always want to see every downvoted comment, then install my brand new super duper userscript created in the last 5 minutes: https://openuserjs.org/scripts/mraron/Codeforces_Show_Bad_Comments (you may need something like tampermonkey addon to get it working though)

[/END of self advertisement]

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

Hope the description of the problems can be concise.

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

Scoring?

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

Anyone join the campaign to turn all comments to upvote (except those ask for downvotes or unhelpful comments) ?

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

Freaking A >(

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

problem c is much harder than problem b

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

Was C not Knapsack ?

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

How to solve problem D?

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

    You can calculate the cost for other have less or equal than k votes, and i have greater than k vote in O(NlgN). then test for all k = 1 to N/2+1

    ----------------- Sorry I confused C/D

    If N % 4 != 0, answer is -1

    If N % 4, Let's think about the sequence of A[1 to N/2], A[N/2 to 1]. ex) 1 2 3 2 3 4 3 2 1 -> 1 2 3 2 3 / 3 4 3 2 1

    Then Since diff is 1 or -1, it it guaranteed existance of answer. Then you can find it by binary search. I want to explain more but i should leave now sorry :(

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

How to solve div.2C?

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

    Iterate the number of votes we want from party 1, then get the minimum cost required for this number of votes to be the majority. Answer is the minimum of the result from all the different number of votes required.

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

    1 <= k <= n, you need to calculate cost (k = 1; k <= n), k is votes, then min of these cost is our answer, firstly you should cut k <= votes[i] (1 <= i <= m) x = votes[i] — k + 1, then cur_votes += x; second need_votes = k — cur_votes then first sum of need_votes added your cur_cost

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

Can anyone explain problem C && D please?

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

Interesting problems, how to do Div1C?

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

For div2c the idea is to always select the minimum voting cost until it's time to choose the last voter... is this approach right? and if it is, how to implement the last part of it ?

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

Div.2 C is bunch of priority queues and sets and maps. I was not able to finish it in time :'(

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

Problem C make me simulate the same example again and again for 1.5h but I finally found nothing qwq.

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

Does every interactive problem on CF have to be binsearch :P? (OK, I know there are many counterexamples, but number of such problems is too high and they are rarely interesting)

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

    This was exactly what I thought when I saw 60 in problem B :)

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

      I didn't know how to solve. Saw 60, and that two queries are definite for as for i and i+n/2, I was sure it was Bsearch. I coded for both way, one was working, submitted and accepted. I don't even how that solution is correct but its working.

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

Any idea for Div1 C?

Btw, C is a bit too hard, but today's problemset is good. Problems are balanced between thinking and implementing. I enjoyed B a lot.

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

    Btw, C is a bit too hard, but today's problemset is good.

    The kinda converse to Div 1 C (that too not constructive, but just the existence of such sets) came in Tuymaada 2010 Junior Problem 8 but it's still unsolved on AoPS !

    I hope the answer to this problem (Div 1 C/Div 2 E) will give some hint on that problem, because that one is bugging me for a while.

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

    This seems to be exactly a constructive version of Chvatal-Lovasz theorem about semi-kernels in directed graphs.

    The simplest proof is indeed constructive and should yield a linear algorithm: pick some vertex v, delete it and its "positive neighbourhood" (the set of all vertices u such that there exists a v → u edge), recursively find a solution in the remaining graph, add v back if you may do that without breaking independence of the set of the picked vertices. Now you have a solution for the original graph (to verify that, just consider two cases: you added v back or you did not).

    Link to the original paper: Chvatal-Lovasz theorem.

    For implementation details, you may refer to this submission: 41500579.

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

can anyone tell me an idea/solution of pb "C. Elections" in recursive + memorizing

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

    You mean DP? Because I'm pretty sure a DP solution is not available for Div 2. C, as in the states you don't know which party have how many votes in order to reach for an optimal state.

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

My story in A

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

Unlucky round for me.

I started by quickly solving A, then moved to C. Wrote a solution in 20 minutes, and only then red the second sample. I really need a browser extension to replace "loop" -> "self-loop". Then I moved to b, and got 2 WA's in test 16. What is the problem?

int answer(int i = -1) {
	if (i > 0) i = (i%n+1);
	cout << "! " << i << endl;
	exit(0);
}

I solved the problem zero-indexed, so I had to fix the indexes by adding 1. But if i = 0, it outputs 0 giving WA. I didn't realize this was the mistake, shuffled some code around, and got "pretests passed". Then only later I realize this and had to resubmit.

But yeah, I couldn't solve C, so I don't mind losing rating.

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

Does anyone know what's the issue causing WA on pretest 5 in div2C?

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

Hi i thought I found someone violating the rule of codeforces contest

higu and adityasr share the same solution for Problem C of Div 2

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

This the first time for me to enter a contest , in fact I couldn't solve any problem as I misunderstood many points and also I haven't practice a lot ,but I hope to do better than this the next time.....

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

See!!

I told you everybody that Benq is going to be the next world conqueror of CP.

rip everybody

Benq wil beat you all!

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

could any one tell me what is that system testing that have started after finishing the contest,please??

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

    In the pretest, only part of test cases are run. After the contest, the system judges all the solution with all test cases and test cases used in hacking

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

How to solve Div1 C? I passed pretest but I'm not sure my solution...

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

I think today's problems are very nice.

But,I think the difficulty of solving B and the difficulty of solving C is too different.QAQ

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

How to solve Div1 C? I passed pretest but I'm not sure my solution...

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

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

    That's crazy. Even the same legend. After more than 1000 contests, it must be really hard to find these coincidences.

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

    I think every time there is an election in Russia, someone "comes up" with that problem. That's why it has already been in a contest.

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

    The main difference is the constraints. My O(n^2) solution was accepted, but in this problem, it will fail as 1<=n<=10^5.

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

    We were not aware about this problem, sorry =/.

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

For div2 C, first lower down every other party to at most k votes, then we can get enough votes from those who need least without considering if he is from the most voted party. Check every k from 0 to m, we can find the minimum cost.

I pass pretest with this solution in 1900ms, and reducing time to 1100ms using priority_queue.

Hope it won't get a TLE on the system test :p.

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

    Wrong answer on test 21……QAQ

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

    I should check every k from 0 to n, not m……:(

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

    Hi. What is K? and why do we have to reduce other parties? Can you please elaborate?

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

      The number of votes that you give to party 1. If you fix the number of votes, it is easy to calculate the min cost. So fix the number of votes (k), but try all possible values.

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

Did someone passed Div1D with O(n3)?

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

    Just found 41488961.

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

    I did, but it took quite some iterations (== random changes to the code) to make GCC on codeforces to compile it as I want...

    It would be awesome if the "run on server" tab provides an option to download the compiled binary. One can at least see what exactly the compiler is doing.

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

    Yeah, but in my case, with a dirty trick. See my comment below.

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

      Yeah that's insane. I have to trust more in CF servers.

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

        As ilyakor's comment above tells us, trusting can be pretty dangerous. It's best to be sure, and testing in a local environment similar to CF servers helps greatly.

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

In div. 1 C, about 70% submissions that passed the pretests, failed later on test 20. Why wasn't this test added to pretests?

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

    To don’t help people with heuristics I guess. Pretests should help you catch bugs.

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

      Maybe I don't understand the idea of pretests, but in my opinion, they should help contestants check if their solution is mostly correct.

      In general, I believe that most heuristics and/or brute-force solutions should fail on good pretests. Also, stupid corner cases should be included in the pretests as well.

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

      Pretests should help you catch bugs.

      No, pretests should give you some idea if a solution is correct. You can catch bugs by stresstesting, but can't realise you're missing something essential by doing that.

      To don’t help people with heuristics I guess.

      Only if you expect a lot of solutions with heuristics that wouldn't pass some type of tests, which isn't very realistic in problems like this one. I'm sure there weren't many heuristics among the failing submissions.

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

Looks like most of the solutions to Div1 D (1019D - Большой треугольник) are with binary search. I didn't come up with the right solution, but managed to squeeze an O(n3) one (41491248) instead, using 1950 milliseconds out of 3000. It involved a trick and a dirty trick. I'd like to elaborate on that, to increase awareness of such tricks for contestants and problemsetters alike.


The trick is just loop unrolling, which is around this part:

enum span = 4;
for (v = j + 1; v + span <= n; v += span) {                    // instantiate 4 identical blocks at a time
	static foreach (r; 0..span) {{                         // so that they can be computed in parallel
		auto t = pjx * p[v + r].y - pjy * p[v + r].x;  // pjx and pjy are p[j].x and p[j].y
		ok |= (t == sp) || (t == sn);                  // t can be positive or negative
	}}
}

The static foreach is expanded at compile time into 4 blocks with r = 0, 1, 2, 3. In C++, one way to do it is to use a #define inside the loop, and instantiate it manually 4 times instead.

The dirty trick is doing all of the above in signed int32: as the program is run in a 32-bit environment, it helps greatly. If we find the triangles which have area equal to s modulo 232, only then we check again using true but slow int64 multiplication and comparison.


Now, as a problemsetter, you can't really do anything against loop unrolling. In fact, in simpler cases, a good optimizing compiler does that itself under the hood.

Against the using int32 part though, it is possible to construct a test case. Make all coordinates divisible by 216, and s divisible by 232. This way, all multiplications modulo 232 will result in zeroes, and the actual O(n3) work will be done by the int64 part of the solution. In this case, making it run for five or six seconds.

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

    I also did it in O(n^3), and without the dirty trick (I did consider it, but figured it was at risk of being attacked). My tricks were to - use pragmas to enable more aggressive compilation - precompute the signed area of triangle (P, Q, origin) for every P and Q, after which the area for a triangle (P, Q, R) can be computed purely with addition (which is less expensive than multiplication on a 32-bit system).

    It would be nice if Codeforces would move to 64-bit one day — these days even the chips in your mobile phone are 64-bit!

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

      Argh. I wrote essentially the same code as you, but without pragmas, so it got TLE. I guess I will know what pragmas to use next time.

      (I also tried putting the points into buckets depending on the coordinates modulo 11, and then only comparing those buckets for which the area is correct modulo 11. But it got WA due to a silly bug.)

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

      mind sharing any good resource on learning these pragmas? Thanks!

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

        I read them in a comment on some previous contest (might have been a different architecture pragma, I couldn't remember so picked something that looked sensible), but I don't recall which contest it was.

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

        Pragmas are instructions or information for the compiler embedded in code, e.g. pragma once (ignore all include-s for this file except the first one) or pragma GCC target() for setting target architecture. Obviously, they're compiler-specific, so you have to read the documentation for a specific compiler. For example, I found this in about 5 seconds, so don't ask for shit you can look up yourself.

        Function attributes are more interesting. You have the optimize attribute, with which you can tell the compiler to aggressively optimize just one function — very useful, since Ofast on everything can slow down some other part of your code. Then there's always_inline attribute, with which you can force inlining of a function that the compiler would usually skip because it's too long (e.g. a lengthy arithmetic expression that's used very often).

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

          Thank you for the useful information. Sorry that you get downvoted for helping :(

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

      I did the same with you, but got TLE with C++11. After the contest, I submit the same code with C++14/C++17 and get a Accepted. :(

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

    What do you think about the following idea: pick random p < 2^16, begin by taking coordinates mod p, and compute hash of triangle areas mod p using integer type.

    EDIT: Never mind, mod is probably slower

    EDIT: okay, seems like Gassa got it to work.

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

      I tried it now but realized that, yeah, we seem to need a modulo operation in the innermost loop.

      I've tried to make the calculations modulo mod-squared. But, if we take the coordinates modulo mod, their product is correct modulo mod, but not correct modulo mod-squared. For example, 1 (modulo 2) times 1 (modulo 2) can in reality be either 1 or 3 (modulo 4), we don't know. So, seems we have to use the slow % operation.

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

        What about a memory access, keep array f[x] = 1 if x is a multiple of p and 0 otherwise?

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

          Now I'm confused. How would it help?

          The example modulo 4 does not work even for non-multiples of 2.

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

            No, just do the original thing, to check if area + S is a multiple of p, just access f[area-s]. (maybe pick p < 2^12 and have bitset of size 2*p^2?)

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

              Hmm, that could have worked, but doesn't for me (attempt: 41503640).

              When the mod is too small, we would have too many false positives. When the mod-squared is too large, the array does not fit into processor cache. I've got TL with mod = 997.

              Actually, scratch that. With a bit of refactoring and mod = 107, this passes: 41503762. Thanks for the idea!

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

      This can still be easily hacked. (it's mostly safe against system test, though)

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

      Maybe we could do something like this:

      Pick a random p ~ 2000. (see note)

      As suggested, we want to find all solutions mod p (of which there are hopefully ^3/p) and test them individually.

      Our basic loop is as follows:

      for each pair of points (P1, P2): determine all P3 which gives right area mod p test these triangles

      Let ABCDEF be some constants. Let P3 = (x, y)

      Now, after fixing P1 and P2, we know that the area mod P is given by Ax+By+C. We want Ax+By+C = S. If A=0, we handle it separately. Else, we divide the equation by A, giving x+Dy+E = S, or x+Dy = F.

      To find all such points such that x+Dy = F, we can precompute x+Dy for each point and each D. That is, we can store a vector of points for each pair (D, F), representing points such that x+Dy = F.

      The complexity for random points should be O(n^3/p + np). Choosing p~n gives O(n^2).

      Note: Of course, a given p can be easily hacked. Just choose S = p^2 and all coordinates multiples of p.

      I'm not sure if a randomly generated p can be hacked; there are not that many good choices of p too.

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

    I got TLE with O(n^2 log n) in Java during contest so was thinking the TLE was too tight, but I guess this proves me wrong.

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

Feeling so uncomfortable in this round.

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

Are you planning to change this feature/bug with bomb on sample other than the first one? It cost me a victory...

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

    It's truly a feature. It's meant to prevent you from failing in very simple ways as sending wrong file or wrong formatting of output/input. It's not meant to not penalize you for WA on third sample.

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

      I was formating output incorrectly on second sample.

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

        Obviously wrong formatting of I/O. Or submitting a wrong solution or forgetting to delete random input generator from your code or other silly mistakes. It's extra lenient, but worth having despite that IMO.

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

How to solve Div1D

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

Nice TOP3! High five Marcin_Smu and Radewoosh :))

Btw, it seems that many people tried some heuristics to C and all fo them failed. I have to admit that I also pushed some shitty solution... But it seems it was less shitty than others :P. I basically keep all the time some set of vertices that is an independent set and when I see a vertex that is not reachable in two steps from others I delete all its out-neighbours from set and add itself. And I do it until I run out of time or until I get a solution — whichever is sooner. And it luckily turns out that second case is always sooner :P

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

I opened problem E after the end of the contest, and found it was actually an extension of my recent CSA problem. (That extension completely changes things, so it's not a copy) Although I don't have any good ideas, I regret myself of not opening E :)

And big thanks to setters for the great round! Problems were really interesting. It looks even better because last round was very poor. Thank you so much for the effort!

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

I'm currently suffering from Post-Codeforces-Round-Depression :P

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

    I'm suffering from Continually-Refreshing-The-Page-Every-37-Seconds-Even-Though-I-Already-Know-How-Badly-I-Did Depression :/

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

Runtime error on codeforces, same test case works perfectly on my pc. Same compiler. This isnt first time its happening. just wow

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

    That happens, for example you over bounded when seeking an element of an array and there happens to be a zero (or anything "make sense") on your PC.

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

    The compiler option may be different. Try to compile it with "-O2" ?

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

    Run your program with Valgrind with a small input, you'll probably find you're reading something out of bounds or uninitialized. Usually that happens to be a 0 in your PC but random data in CF, so it seems to work but doesn't

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

Rating changings ?

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

For anyone interested, I wrote up solution sketches for a few of the Div 1 problems from today -- take a look: http://codeforces.com/blog/entry/61144

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

Editorial ??

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

Can anybody tell me what is the complexity of this code? for problem Div2 C
My idea : To get answer there are only 2 possibilities
1) We change the perception of person with minimum cost
2) We change the perception of person with minimum cost of the party which has maximum followers.

I am using string s to store which people are followers of our party(i.e. party 0).

Then either the first condition holds or second conditions holds for getting the correct answer.
I think to find the answer we need to change at most 1500 characters in s and so my solution should work in O(2*1500*N) where N = overhead for calculation of each dp = O(n). So final solution should work in O(n^2).

I don't know why it is showing TLE on testcase 46 which then I had to add an exception in code:p and get it accepted.

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

I'm finally back to red and not at all happy about it. I'd much rather get a good place because I did well than because almost nobody did well. What's even worse, D is solvable by very optimised bruteforce, A is a ripoff and C, D are "write a heuristic, maybe you'll pass lol" problems.

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

Got TLE for three times on div1.A with an O(n^2logn) solution, which made me upset and unwilling to do anything...

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

Is the tutorial of the round coming soon? It seemed that some solutions of Div2.D can be hacked.

For example, use this data to hack Onuz's solution:

16
0 1 2 1 2 1 0 1 2 3 4 3 2 3 4 5

or use this to hack usachevd0's solution:

24
0 1 2 1 2 1 0 1 2 1 2 1 2 3 4 3 2 3 4 5 6 7 8 9

So I have a little doubt that if the data need to strengthen.

upd: I am so sorry that I had not seen the constraint condition that |a1 — an| = 1.

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

Please, share the editorial of Round #503(SIS Div.2)

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

Why this submission works weird? I submitted the program that only prints ? n 6 times, and then ! n. But the judgement protocol shows me that for the first testcase the program(submitted) prints 7 and 6. There isn't even ? character.

For the second testcase, the program is expected not to print -1 at all, but the judge says so.

Did I misread the problem statements?

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

    The first value is the answer. The second value is the number of times you asked.

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

      You mean, 7 6 from "output" section of Test #1 means "the answer" and "# of queries"? But I can't understand why the value 7 pops up. The code only prints n, which is 8 for the first test...

      Also, the second case gets me confused even more. The code never prints the answer, -1. But the judgement says it does, and the test is passed.

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

        The first value is the answer(0-index). for example, with test case 1, first value must be 3 or 7.

        about second example, you should read your code carefully.

          if(n/2&1) {
            puts("! -1");
            fflush(stdout);
            return 0;
          }
        
        • »
          »
          »
          »
          »
          2 дня назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          OMG... Sorry for my carelessness.

          The root of the problem was my mistake from code. I wrongly printed "the value" instead of "the position".

          To my shame, I doubted the judging system. Thank you Oumae_Kumiko !!

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

разбор будет?

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

Please, share the editorial of Round #503(SIS Div.2)

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

Please, share the editorial of Round #503(SIS Div.2)

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

Thank you for preparing the problems and round. :)

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

This round should be unrated, problem A was absolutely copypasted!!!!

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

Hello there, I'm new to Codeforces. Few days ago I tried to take part in this contest as my first one. When the contest is finished, I checked my code again but couldn't find any problem, so I asked my friend to help with me but we found that with different compiler selected, the result is different. Why and is it unfair?

The following pictures shows that the result of same file submitted with different compiler.  My code could be viewed/download here

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

    After the contest you can see the test case your submission failed on at the bottom: http://codeforces.com/contest/1020/submission/41532464

    It looks like abs() is returning a floating-point value for you in the older version of C++, but it returns an integer in C++11. In particular, this line is the issue because you are actually printing a floating-point number:

    cout << abs(f1 - f2) << endl;
    

    Also, I recommend against using endl. See this comment for an explanation.

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

      Thanks, that helps a lot!

      But I am still wondering why it behaves different from the C++ Standards which refers here(cppreference.com) when using GNU C++(v5.1.0).

      int       abs( int n );
      long      abs( long n );
      long long abs( long long n );
      		(since C++11)
      

      Is it a BUG of the compiler? And why this happens only when the result is very big?

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

well,I'm still waiting for the solution for this contest,it's so slow QAQ