Vovuh's blog

By Vovuh, history, 4 weeks ago, translation, In English,

<almost-copy-pasted-part>

Hello! Codeforces Round #575 (Div. 3) will start at Jul/24/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD: I also would like to thank Ivan BledDest Androsov for help with problems preparation, and also danya.smelskiy, greencis, chenjb and STommydx for testing the round!

UPD2: Editorial is published!

UPD3: I also would like to thank my friend Maksim Ne0n25 Mescheryakov for improving tests of the problem F! :D

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

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Sofa!

Vovuh makes a lot of div3 rounds!

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

If you are to say "You will be given 6 or 7 (or 8) problems" to the notice, why don't you announce exact number of problems later?

»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Nice! A round just for us newbies.

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

How can a normal round be ICPC rules!

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

Hope the statements are easy to understand.(I understand the problem wrong for too many times!)

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

Vovuh: Announces a new Div. 3 round
Me: Aw shit, here we go again...

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

Thanks to Mikemirzayanov for this great platform. You are doing a tremendous job. making 2 or 3 Contests almost in every week.. :)

»
4 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

MikeMirzayanov, after some updates on Codeforces when I copy my code into IDE on every empty line there is a strange symbol which brokes my compilation. Is it going to be fixed?

Maybe anybody had such problem, how did you fix this? I use Codeblocks. Few time ago there wasn't such problem :(

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

    It is not an error.It is a common thing,but yeah it causes problems for most of the users. In sublime-text i paste the code with Ctrl+Shift+V and it works for me

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

    I'm also facing the same problem. Whenever i try to copy my code from CF using copy button and paste it on by IDE , the code doesn't compile. However , when i copy my code manually using cursor the code does compile. Strange.

    MikeMirzayanov , please fix this.

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

    I ran into the same issue. If you're on Linux/Mac you can use perl -pi -e 's/[^[:ascii:]]//g' to strip all non-ASCII characters from a file.

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

Hope the statements are easy to understand and very short.

»
4 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

i wish this round will be a real div3 not a hidden div2

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

I wanna be blue.

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

    For blue you need 185 point it means you must solve 4 or 5 problems in div 3

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

      Certenly,solved only four or five problems in div.3 is not enough to became a Expert.At least six(or AK!) problems is enough.

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

    I don't want to become pupil

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

»
4 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

Serouisly!!!! This is supposed to be a Div3 Round?

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Queryforces!

»
4 weeks ago, # |
  Vote: I like it -49 Vote: I do not like it

wtf this is harder than a div2 contest

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

How to solve problem C?

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

    Make a variable to store the area where any robot can get. This area whould be a rectangle, so just store x and y of left bottom angle and x and y of the right top angle. Next for the first robot get the area where it can get. In python it would be like this:

        if r[0][2]:
            pos[0][0] = -100000
        if r[0][4]:
            pos[1][0] = 100000
        if r[0][3]:
            pos[1][1] = 100000
        if r[0][5]:
            pos[0][1] = -100000
    

    where r is the array of all robots an pos is an array in shape of [[x0, y0],[x1, y1]]. Set all robots reachable area as first robot's, because we've checked only one so far. Now get the same area for all of the other robots and compare it with all robot's area:

            if robot_pos[1][0] < pos[0][0] or robot_pos[0][0] > pos[1][0] or robot_pos[1][1] < pos[0][1] or robot_pos[0][1] > pos[1][1]:
                print(0)
                break
    

    This huge line can't even fit the screen, but it checks if current robot's area intersects with all robot's area somewhere. And if it does, then set all robot's reacheble area to this intersection area:

    pos[0][0] = max(robot_pos[0][0], pos[0][0])
    pos[0][1] = max(robot_pos[0][1], pos[0][1])
    pos[1][0] = min(robot_pos[1][0], pos[1][0])
    pos[1][1] = min(robot_pos[1][1], pos[1][1])
    

    And then if our loop through all robots didn't break, then it's possible for all robots to reach a single point. It's any point in their area. 57687425

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

    Keep the four variants: min_left, max_right, min_bottom, max_top

    if f1_i = 0, min_left is not less than x_i

    if f2_i = 0, max_top is not greater than y_i

    if f3_i = 0, max_right is not greater than x_i

    if f4_i = 0, min_bottom is not less than y_i

    if on i'th iteration current value of some of four variants don't meets this conditions, update this variant

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

    My thanks to Vovkaez and to kazak. I almost got it during contest, I changed some conditions. FeelsBadMan

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

Good problems, have to sweat in each problem but it was nice. The round more resembles div2.

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

So, how to solve D2?

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

    Use prefix sum to count the number of incorrect positions in string from pos 0 to pos i, and do it for the 3 ways: RGB, GBR and BRG. Then iterate over al possible k substrings and get the minimun answer by doing: pref[i]-pref[i-k] for all 3 different prefixes.

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

    You can also use sliding window/two pointers technique to solve in O(n) My code: https://codeforces.com/contest/1196/submission/57674284

»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Hi guys,

In Problem C, even O(n) complexity algo is getting time limit exceeded. Can someoone help here, please ? http://codeforces.com/contest/1196/submission/57694392

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

    MikeMirzayanov I believe the time complexity for Java should be increased as i tried fastest possible i/o in java, still i am getting time limit exceeded.

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

      nothingtolose I believe it is a bad idea to allocate new int[100005][6] on each testcase. Imagine the number of testcases $$$q=10^5$$$.

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

I got 3 of them :(

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

    I just finished 1 of them which makes me so sad,how can i finish as many problems as possible?

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

      You just gotta keep practicing bro. I was in your position a year ago but this time I managed to solve all but the last one. Just keep at it!

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any more details on how you progressed during the year?? Would be helpful to know...

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

It was similar to D2. How are the questions difficulty supposed to be? Div 3 B = div2 A? Div 3 c = div2 B?

Also how to solve D1 & D2?

Overall good contest..

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

    There is 3 type we can do $$$RGB, BRG, GBR$$$ and for every $$$i$$$ $$$mod$$$ $$$3$$$ position we need to check if this position equal to that $$$3$$$ substrings, because of it we create $$$3$$$ counters which counts all positions where $$$i$$$ $$$mod$$$ $$$3$$$ of string is not equal to the position, and for D2 we just need to find $$$pref[i] - pref[i - k]$$$, because its like we adding one letter by deleting first letter, to understand it you can check my solution 57672041

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

Python don't work for D2, :'(. Got penalty and had to rewrite code in C++.

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

    Same here. Had to rewrite B too, though I optimized it in C++. But D2 was exact translation.

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

      Hey vsinha! Would you like to try my previous comment and submit the python code for D2 and B again to see whether it now satisfies the time limit?

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

        It worked. I resubmitted D2 and it got AC. Thank you very much for the tip. I'm not submitting the python version of B, it perhaps suffers more from a poor algorithm than IO limits.

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

          =) I think for B as long it is an O(n) algorithm, it should work perfectly

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

    Hi islingr! I looked at your D2 python code. Do you want to add the lines

    import sys
    input = sys.stdin.readline
    

    on the top of your code and submit it again to see whether it will now satisfy the time limit?

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

      Using this I could only pass one extra test case and then the it TLE'd on the next test case failed.

      However, making a few changes in the code and using this did make it work. Thanks.

      Here's the final code which worked.

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

I really liked problem B, spent ~ 5 attemps to understand that i need change int->ll

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

    how to slove it ?

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

      You can calculate remainder of sum on prefix, if you find some place where remainder is odd, add it to answer and say that now remainder is zero(we calculate remainder of sum on prefix from that position). Now leave first k-1 elements of that array add n to answer and check that all ok. All ok if sums on that subarrays is odd and answer have size equal to k.

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

        you're right,it seems simple,but during the contest,i thought the way,however i couldn't prove it,so i try to dfs it,which got me into trouble. What a sad evening....i can't fall asleep.

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

      Here is my code

      I initialized an array of size n; then, for each element, I determined if it was even or odd, and kept track of the total number of odds. If it was odd, I would mark that array with a "1"; if it was even, I would mark it with a "0".

      Now, if the number of odds % 2 doesn't equal k % 2, or the number of odds is less than k, I printed NO.

      Otherwise, print YES and print every index of an odd number and keep subtracting from k until you have one left; then, just print n as the index.

      I'm bad but it worked.

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

        I was also doing the same , don't know what's wrong with my soln

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

          got it . I was failing at test case like this when last element was not odd . 1 10 3 2 3 9 4 6 4 2 5 8 8

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

For Problem C:

I sorted according to X then according to Y and found intersection point for X and Y.

The intersection point will be a point for which on left side all robots are coming towards it or equal X coordinate and on right of it all robots should be coming towards it or equal X coordinate.

Same thing for finding Y coordinate.

Am I missing some corner case here ? As I was getting WA on test case 5.

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

Were there any scoring table on the right side, there were not for me.

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

anyone has a good explanation for problem E before the editorial shows in the next era? :)))

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

    Assume b>=w (you can shift all squares over if needed). Make a line bwbwbw...bwbw until you run out of w's. Then you can place the remaining b's by connected them to the top or bottom or left of this line. If there are still b's left, it is impossible.

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

      i checked your solution and i think i got it..thanks..nice aproach..

»
4 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

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

    amazingly when i submit my d1 code in d2 it worked correctly for the first 15 testcase

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

    It feels bad man. When I submitted D1, I had only 5 minutes left. And I thought okay now I am done I guess. But It actually worked perfectly fine :(

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

    hhhhh

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

I think k can be $$$ 10^5 $$$ in problem F and you can see my solution.

https://codeforces.com/contest/1196/submission/57688661

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

    can you please explain your approach?

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

During the contest, for Div2-B, I thought that the only condition for "NO" answer is

if((k%2==1 && sum%2==0) || (k%2==0 && sum%2==1)) pf("NO");

Here sum is the sum of all numbers in the input.

Now I added another condition for "NO" which is ans.size()!=k and it got accepted. Can someone give me a testcase which can help me understand this behaviour?

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

    5 3

    2 4 6 8 10

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

      Even with just the first condition, it's giving correct answer "NO". I want to know a case where this condition is alone not sufficient.

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

      5 2 2 4 6 8 10 rr459595 answer Yes but really answer is NO

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

        Oh, thanks. So it's just a necessary condition and not sufficient :(

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

    there are only two condition of "NO" let n=no of odds 1)if n<k 2)n>k and n-k is odd

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

    1 4 2 1 3 5 4

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

      k%2 ==0 and sum%2=1. So the answer is "NO" and the answer is really "NO" right? How is first condition failing?

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

Any hints on how to solve Problem F?

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

    You can see that if you sort all edges by weight, the k+1 edge and another that weight more than k-th aren't in our answer(forger for them). Now you have k edges, up to 2*k vertices have at least one edge, and you can run Floyd–Warshall_algorithm for vertices which have edges and get AC.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it -9 Vote: I do not like it

    You will need to use Floyd-Warshall's algorithm to solve F. Its asymptotic time complexity is O(N^3) and space complexity is O(N^2), so you cannot employ it right away.

    However, there is one thing you need to notice: if a path is k-th in the final sorted distance matrix, it will not include any edges that are longer than the k-th shortest edge given. (Agree that the k-th shortest path is obviously not longer than the k-th shortest edge, at least because the set of edges is a subset of all paths and we already know k — 1 one-edge paths shorter than k-th edge).

    Now sort all the edges and pick out only k shortest ones. Compress the coordinates and create a graph consisting only of these edges.

    Run Floyd-Warshall's, which will have the asymptotic time complexity of O(k^3).

    Slice the distance matrix you're running Floyd on across the diagonal. Find the k-th minimum on any of these slices (they're the same). Output the result.

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Dafuk is wrong with me Spent 1 hour on C and 17 minutes on D2 and D1

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

Is there some added advantage on asking query-based test cases? Do they do it so they can test on more cases this way?

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

    From what I understand it's purely for ease of judging

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

    I think questions based on online queries ( and even offline ) pose kind of a challenge to the solver compared to the other type because of vast number of queries to answer in such small amount of time and is more practical i think ? Hope the answer helps!

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

      Are you saying that having several separate test cases is worse than having the same test cases compiled into a single query-based test case?

      I'm assuming that the former works by generating a single output file from the code and running it several times. The latter would work by running the same output file only once in this case. But even then I don't see how there would be a significant benefit from doing this.

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

        No, sorry for any misunderstanding, what i meant was that sometimes query based questions require a more algorithmic or cunning approach compared to the ones which doesn't. But i cannot say the same in this contest though(Though i agree that many might disagree with me).

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

          Yes, that makes sense if the tester is expecting an $$$O(1)$$$ or $$$O(log n)$$$ solution. But I suppose for $$$O(n)$$$ and $$$O(n log n)$$$ solutions, it hardly makes a difference.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Someone really wants to get their opinions established in D2

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

    Implementation, implementation i esche raz implementation!

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

Any suggestion how to solve F, without Floyd–Warshall_algorithm? I solve it by Floyd–Warshall_algorithm, but I belive that exist some quite good idea how to solve without Floyd-Warshall_algorithm, maybe for k<100000

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

Blin! I don't solved B, where odd subsegments, cos i forgot to write 0LL in accumulate(a.begin(),a.end(),0LL), i wrote accumulate(a.begin(),a.end(),0). This is obidno!

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

    Sometimes such shit happens. But do not be upset.

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

      What is your most offensive error or stupidness in contests? (My subj is here)

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

        I build segment tree with vector in parameters, get memory limit and I spend a lot time to see that so bad, because vector each time copied.

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

Please notice these two codes 57693377 and 57690563, (2018030102067 and Mole_Q) i think they are cheating. 57676867 and 57674699 2018030801054 and 2018030401051 are similar, too.

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

    Wow, nice job. But i'm interested about how did you find it that they are cheating

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

    No d1 solutions are very close

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

57693377 and 57690563 i think they are cheating.

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

How to solve problem E ?

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

    if(B>=W) build such structure bwbwbwbwbwbwbwbw after you can add b to top or to bottom or to left if you add all and you must add more answer is no this is case (B>3*W+1) else same things as B>=W but swap white and black

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

    I think it can be solved like this : Think of it like a tree , just with this constraint that the tree cannot have more than 3n+1 of the colored nodes which are in majority.By drawing 1 or 2 configurations, you can realize that to get maximum number of nodes of the majority type, one of possible tree is a straight one.So if you select minority nodes = a, then connecting those must be a-1 majority nodes, and the rest can be taken till we fill the required quantity of majority nodes! Hope it helps!

    Consider the picture for example( :D) : Link

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

Mechorca 2018030401093 2018030801054 maybe they are cheating

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

I am just wondering, what is the purpose of hacking in a round where the tests are strong ??

I'm not saying that I want what happened in Educational Codeforces Round 67 (Rated for Div. 2) to happen again, but won't it be more fun if there was a problem that has a test where everyone forgets about ?

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

Couldn't solve E due to lack of time during the contest. Now realizing, easiest E ever??

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

Why does a BFS solution of E fail while one with DFS pass?

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

    i think it should solve with Dfs because we need to go deeper in a chain not by level so it make sense to use Dfs not Bfs

    if we go by level then maybe there is some cells that have a common cell with white color (if white is the greater one)

    i can draw something if you don't understand :)

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

I cant make sure about this, but I wonder if this k shortest path routing can be used to solve problem F or may be Im wrong, let me know your thoughts. Why I know this? Because this was a topic for homework at my uni, and I chose this approach to find k-th shortest path in a weighted graph.

»
4 weeks ago, # |
  Vote: I like it +55 Vote: I do not like it

Big day for Codeforces. We set a new record. The total number of registered users on Codeforces Round #575 (Div. 3) is 12619! Our servers are ready for more. Let's see what happens next!

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

    Great! Btw there was a little delay today, between submissions and judging (the 'in queue' period was larger than that in the usual rounds).

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

    it cost me over 1 minute to show problemA

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

if e can be solved by bfs? help me !! 57713663

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

It is really frustrating that a O(n) solution written in Python3 (PyPy) can exceed the time limit for problem B!

It seems that I am only reading in the values of n, k, l, and doing constant time comparisons in case of 200000 queries. Does anyone know any trick of how I can change the syntax to reduce runtime? I am attaching my code. Thank you!!

Python Code for Problem B

q = int(input())
for _ in range(q):
	n, k = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if n == 1:
		if l[0] & 1:
			print("YES")
			print(1)
		else:
			print("NO")
	else: 
		s = sum(l)
		if k % 2 != s % 2:
			print("NO")
		else:
			p = []
			cnt = 0
			for i in range(n):
				if l[i] % 2 == 1:
					p.append(i + 1)
					cnt += 1
					if cnt == k:
						print("YES")
						print(*p[:-1], end = " ")
						print(n)
						break
			if cnt < k:
				print("NO")

Update: It seems that using sys.stdin.readline() is much better than input(), right?

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

    same here. this is my submission in python3 and got hacked https://codeforces.com/contest/1196/submission/57661674

    Anyway to optimize the code or should I start to learn c++ again?

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

    Java suffers from it too. Time limits or numbers should be a little easier. Well, now I know that printWriter is 10 times better than System.out.print and tokenizer is twice better than split... But it is just implementation...

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

For E I had used ideone not knowing that it was public. Somehow it looks like others have managed to submit my own code to E before I submitted it. I don't know what has happened and am very concerned. I do not know how to prove it but perhaps if you look at code style you can see that it is my code?

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

    I apologise for mistake with using ideone, I did not know it was public in this way. Will not use in future.

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

      Specifically, the void sol() function I use in all my submissions for the contest while none of those copying off me have used it in other solutions.

      I sincerely apologise for the trouble that my use of ideone caused.

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

I'm not able to understand problem E properly. I mean if b=1 and w=5 why can't the answer be (2,1),(2,2),(2,3),(2,4),(2,5) since this is also a connected component.In this way answer should always be possible.We can print b & w coordinates in this linear fashion. Please help inspite of trying hard i'm unable to understand the problem.

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

    if b = 1 and w = 5, you need to output 1 black cell and 5 white cells, so in a total of 6 cells. However, you only have 5 cells. In addition, (2,2) and (2,4) are white and (2,1), (2,3), (2,5) are black, so you actually have 2 white and 3 black instead of 5 white and 1 black.

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

    For chessboards, adjacent cells should have different color, and it is stated that (1,1) is painted white. Your answer is connected, but (2,1) is black, (2,2) is white, (2,3) is black, (2,4) is white, (2,5) is black, which is 3 black and 2 white. one black cell can have at most 4 adjacent white cells, so the proper answer for b = 1, w = 5 is "NO"

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

A very truly great contest for rating less than 1600. All problems were of good quality. Enjoyed the problems.Please make Div.3 like this only.