Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

_kun_'s blog

By _kun_, history, 4 months ago, translation, In English,

Hi!

Summer Informatics School (SIS / LKSH) is a summer school for students in grades 6-10. SIS is focused mainly (but not only) on students participating in the Olympiads in Informatics — from beginners to participants of international competitions. SIS is held in July and August, each of them is visited by about 200 students from all over Russia and abroad. The language of the camp is Russian. Additional information about SIS is posted at lksh.ru

Right now, the August branch of the Summer Computer School is running, and on August 11 the traditional team Olympiad is going to place. I am happy to present a rated round based on it!

The round will be rated for both divisions, will be held in Aug/11/2018 16:35 (Moscow time), in each division there will be 5 tasks and 2 hours to solve them.

The problems of this round and the SIS olympiad were authored and prepared by SIS's teachers: izban, achulkov2, Schemtschik, i_love_isaf27, senek_k, asokol, WreckingBall, burunduk2. Also, I would like to thank Dembel for his help with olympiad's organization.

Thanks to our problems testers: _meshanya_, burunduk2, gritukan, niyaznigmatul, manoprenko!

Thank you, MikeMirzayanov, for the codeforces and polygon systems!

Yes, we are aware, that this contest clashes with ProCon Junior on codechef. However, given the schedule of the SIS and the approaching VK cup finals we can't do anything with it, sorry for that =/

Good luck!

UPD: The round will have one interactive problem for both divisions. Please, read the post about interactive problems here: Interactive Problems: Guide for Participants.

Congratulations to winners!

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 Thank you for participation! Due to vk-cup conduction rating recalculation will happen slightly later, than usually.

Upd The editorial is published!

You may also check the unofficial editorial, written by neal.

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

»
4 months ago, # |
  Vote: I like it -37 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

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

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Which problems are going to be based on the olympiad?

»
4 months ago, # |
  Vote: I like it -46 Vote: I do not like it

But Is It Contributed?

»
4 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Or Is It Rated?

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it -31 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it -30 Vote: I do not like it

mathforces?

»
4 months ago, # |
  Vote: I like it -19 Vote: I do not like it

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

»
4 months ago, # |
Rev. 3   Vote: I like it -40 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
    Rev. 5   Vote: I like it -43 Vote: I do not like it

    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>

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it -27 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -13 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Original contest is ACM styled like most team olympiads.

»
4 months ago, # |
  Vote: I like it -34 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -33 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -36 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -12 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Great to see izban is one of the problemsetters!

»
4 months ago, # |
Rev. 3   Vote: I like it -21 Vote: I do not like it

Are there any shared problems between both divisions ?

»
4 months ago, # |
  Vote: I like it -84 Vote: I do not like it

Please provide some more tutorial about an interactive problem.

Please...

»
4 months ago, # |
  Vote: I like it -90 Vote: I do not like it

Everybody jump on the downvote train!

»
4 months ago, # |
  Vote: I like it -63 Vote: I do not like it

Great round! The time really fits me.

»
4 months ago, # |
  Vote: I like it -13 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -64 Vote: I do not like it

I hope time limit will be enough

»
4 months ago, # |
  Vote: I like it -132 Vote: I do not like it

Trains of Downvote.

metoo

»
4 months ago, # |
  Vote: I like it -88 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it -43 Vote: I do not like it

this blog full of downvote comments

»
4 months ago, # |
  Vote: I like it -68 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it -62 Vote: I do not like it

_kun_ Is it Mathforces?

»
4 months ago, # |
  Vote: I like it -20 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it -89 Vote: I do not like it

    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 months ago, # |
  Vote: I like it -78 Vote: I do not like it

Is it disrated on downforces?

»
4 months ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

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 months ago, # |
  Vote: I like it -30 Vote: I do not like it

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 months ago, # |
  Vote: I like it -89 Vote: I do not like it

I challenge you to Downvote me..

»
4 months ago, # |
  Vote: I like it -73 Vote: I do not like it

I challenge you to upvote me...

»
4 months ago, # |
  Vote: I like it +217 Vote: I do not like it

Why are all comments downvoted?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +78 Vote: I do not like it

    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)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +83 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +64 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it -29 Vote: I do not like it

          So how to deal with these downvotes?

          Keep them polluting the contrib. of everyone?

»
4 months ago, # |
  Vote: I like it -37 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    you can AK ABC in 85 minutes and take part in CF

»
4 months ago, # |
Rev. 3   Vote: I like it -72 Vote: I do not like it

...

»
4 months ago, # |
  Vote: I like it -232 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -62 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      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?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it -16 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it -15 Vote: I do not like it

            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

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it -10 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

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

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

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

»
4 months ago, # |
  Vote: I like it -16 Vote: I do not like it

flood of downvotes!!

»
4 months ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

Why someone was so bored to downvote everyone?

»
4 months ago, # |
  Vote: I like it -15 Vote: I do not like it

I have short by the way.

»
4 months ago, # |
  Vote: I like it +326 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    hhh

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    It's lucky that you still have the chance to be afraid.

»
4 months ago, # |
  Vote: I like it -53 Vote: I do not like it

Can i get more than 100 downvotes ?

I'll appreciate it :D

»
4 months ago, # |
Rev. 2   Vote: I like it +71 Vote: I do not like it

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]

»
4 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Hope the description of the problems can be concise.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Scoring?

»
4 months ago, # |
  Vote: I like it +61 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Freaking A >(

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

problem c is much harder than problem b

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D?

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

How to solve div.2C?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem C && D please?

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Interesting problems, how to do Div1C?

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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 ?

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    You can do it without any of those things.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I did not come up with a more simple idea so I wrote a bunch of these things mixed. XD

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please explain what does cost[i][j] denotes in your solution for Div1 A ,it's computation part ?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +127 Vote: I do not like it

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)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
    Rev. 5   Vote: I like it +49 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it +52 Vote: I do not like it

My story in A

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    You get WA with below input.

    2 2 1 1 2 10

    for(int i=n-1;i>=0;i--){

    *for(int i=n;i>=0;i--){

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe you select the voters who originally support Party 1 to let them change. Before I fix it, I got a WA5

»
4 months ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -45 Vote: I do not like it

See!!

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

rip everybody

Benq wil beat you all!

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

»
4 months ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +79 Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +74 Vote: I do not like it
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +78 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wrong answer on test 21……QAQ

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Did someone passed Div1D with O(n3)?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Just found 41488961.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

»
4 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +17 Vote: I do not like it

      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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

»
4 months ago, # |
  Vote: I like it +113 Vote: I do not like it

Looks like most of the solutions to Div1 D (1019D - Large Triangle) 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Now I'm confused. How would it help?

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

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
            Rev. 2   Vote: I like it +10 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it +20 Vote: I do not like it

              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!

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +34 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I was formating output incorrectly on second sample.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve Div1D

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Just brute force, as discussed above.

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't piss me off...

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Fortune favors the bold xD

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it +41 Vote: I do not like it
        5 5
        2 3
        3 4
        4 1
        4 5
        5 2
        
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Nice! I admit I was lucky!

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +55 Vote: I do not like it

          Why doesn't a problem like this with lots of heuristic solutions just have all directed graphs of size <= 5 as tests? There are only (24)5 = 1048576 directed graphs of size 5, so filling every test with as many size-5-or-less graphs as possible would only require like 10 tests.

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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!

»
4 months ago, # |
  Vote: I like it +30 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Im suffering heavily from post system test depression....

»
4 months ago, # |
  Vote: I like it -16 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating changings ?

»
4 months ago, # |
  Vote: I like it +81 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Editorial ??

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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;
          }
        
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Thank you for preparing the problems and round. :)

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

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

»
4 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can see the code problem B?

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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