cdkrot's blog

Codeforces Round #503 (based on SIS olympiad)
By cdkrot, history, 6 years 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, peltorator, craborac, asokol, Morokei, Burunduk2. Also, I would like to thank Kurpilyansky for his help with olympiad's organization.

Thanks to our problems testers: meshanya, Burunduk2, vintage_Vlad_Makeev, 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. wnsh
  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

Comments Comments (193)
| Write comment?
»
6 years 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!!!!!!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years 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 :)

    → Reply
  • »
    »
    6 years 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)

    → Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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 :)

→ Reply
»
6 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Which problems are going to be based on the olympiad?

→ Reply
»
6 years ago, # |
  Vote: I like it -46 Vote: I do not like it

But Is It Contributed?

→ Reply
»
6 years ago, # |
  Vote: I like it -37 Vote: I do not like it

Or Is It Rated?

→ Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years ago, # |
  Vote: I like it -30 Vote: I do not like it

mathforces?

→ Reply
»
6 years 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 :)

→ Reply
  • »
    »
    6 years 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 arbitrary_A is fixed)

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it -27 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Original contest is ACM styled like most team olympiads.

    → Reply
»
6 years 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...

→ Reply
  • »
    »
    6 years 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!!!

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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...

        → Reply
»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Great to see izban is one of the problemsetters!

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -21 Vote: I do not like it

Are there any shared problems between both divisions ?

→ Reply
»
6 years ago, # |
  Vote: I like it -84 Vote: I do not like it

Please provide some more tutorial about an interactive problem.

Please...

→ Reply
»
6 years ago, # |
  Vote: I like it -90 Vote: I do not like it

Everybody jump on the downvote train!

→ Reply
»
6 years ago, # |
  Vote: I like it -63 Vote: I do not like it

Great round! The time really fits me.

→ Reply
»
6 years 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?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -64 Vote: I do not like it

,

→ Reply
»
6 years ago, # |
  Vote: I like it -88 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

this blog full of downvote comments

→ Reply
»
6 years 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.

→ Reply
»
6 years ago, # |
  Vote: I like it -78 Vote: I do not like it

Is it disrated on downforces?

→ Reply
»
6 years 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)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -71 Vote: I do not like it

    And I downvoted your comment

    → Reply
»
6 years ago, # |
  Vote: I like it +217 Vote: I do not like it

Why are all comments downvoted?

→ Reply
  • »
    »
    6 years 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)

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
        • »
          »
          »
          »
          »
          6 years 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?

          → Reply
»
6 years 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.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -72 Vote: I do not like it

...

→ Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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..

    → Reply
    • »
      »
      »
      6 years 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?

      → Reply
      • »
        »
        »
        »
        6 years 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

        → Reply
        • »
          »
          »
          »
          »
          6 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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

            → Reply
      • »
        »
        »
        »
        6 years 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...

        → Reply
        • »
          »
          »
          »
          »
          6 years 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...

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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...

            → Reply
  • »
    »
    6 years 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?

    → Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

Why someone was so bored to downvote everyone?

→ Reply
»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I have short by the way.

→ Reply
»
6 years ago, # |
  Vote: I like it +327 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    → Reply
»
6 years 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]

→ Reply
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Hope the description of the problems can be concise.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Scoring?

→ Reply
»
6 years 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) ?

→ Reply
»
6 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Freaking A >(

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

problem c is much harder than problem b

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D?

→ Reply
  • »
    »
    6 years 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 :(

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

How to solve div.2C?

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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

    → Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Interesting problems, how to do Div1C?

→ Reply
»
6 years 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 ?

→ Reply
»
6 years 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 :'(

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    You can do it without any of those things.

    → Reply
    • »
      »
      »
      6 years 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

      → Reply
»
6 years 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)

→ Reply
  • »
    »
    6 years 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 :)

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years ago, # |
  Vote: I like it +52 Vote: I do not like it

My story in A

→ Reply
»
6 years 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.

→ Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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--){

    → Reply
  • »
    »
    6 years 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

    → Reply
»
6 years 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

→ Reply
»
6 years 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.....

→ Reply
»
6 years 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!

→ Reply
»
6 years 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??

→ Reply
  • »
    »
    6 years 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

    → Reply
»
6 years 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

→ Reply
»
6 years 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...

→ Reply
»
6 years ago, # |
  Vote: I like it +79 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it +74 Vote: I do not like it

Is DIV1A/DIV2C same as http://mirror.codeforces.com/contest/458/problem/C

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wrong answer on test 21……QAQ

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years 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?

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Did someone passed Div1D with O(n3)?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Just found 41488961.

    → Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
    • »
      »
      »
      6 years 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.

      → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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!

    → Reply
    • »
      »
      »
      6 years 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.)

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
      • »
        »
        »
        »
        6 years 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).

        → Reply
        • »
          »
          »
          »
          »
          6 years 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 :(

          → Reply
    • »
      »
      »
      6 years 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. :(

      → Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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?

        → Reply
        • »
          »
          »
          »
          »
          6 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years 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?)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years 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!

              → Reply
    • »
      »
      »
      6 years 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)

      → Reply
    • »
      »
      »
      6 years 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.

      → Reply
  • »
    »
    6 years 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.

    → Reply
»
6 years 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...

→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I was formating output incorrectly on second sample.

      → Reply
      • »
        »
        »
        »
        6 years 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.

        → Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve Div1D

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Just brute force, as discussed above.

    → Reply
»
6 years 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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't piss me off...

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Fortune favors the bold xD

      → Reply
      • »
        »
        »
        »
        6 years 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
        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Nice! I admit I was lucky!

          → Reply
        • »
          »
          »
          »
          »
          6 years 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.

          → Reply
»
6 years 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!

→ Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years 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 :/

    → Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years 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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating changings ?

→ Reply
»
6 years 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://mirror.codeforces.com/blog/entry/61144

→ Reply
»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Editorial ??

→ Reply
»
6 years 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.

→ Reply
»
6 years 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.

→ Reply
»
6 years 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...

→ Reply
»
6 years 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 wnsh'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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years 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?

→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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;
  }
        → Reply
        • »
          »
          »
          »
          »
          6 years 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 !!

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Thank you for preparing the problems and round. :)

→ Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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://mirror.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.

    → Reply
»
6 years 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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why so many downvotes here?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe something wrong with the checker of problem D?

The coordinates are all integers, so the area of the triangle should be xxxx.0 or xxxx.5.

But why the checker says the area of my triangle equal to xxxx.1?

Submission here: 137387839

cdkrot

→ Reply