vovuh's blog

Codeforces Round #575 (Div. 3)
By vovuh, history, 5 years 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 awoo Piklyaev, Maksim Neon 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 Neon Mescheryakov for improving tests of the problem F! :D

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

Comments Comments (112)
| Write comment?
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Sofa!

Vovuh makes a lot of div3 rounds!

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

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

Nice! A round just for us newbies.

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

How can a normal round be ICPC rules!

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

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

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

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

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

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

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

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

Hope the statements are easy to understand and very short.

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

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

I wanna be blue.

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

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

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

    I don't want to become pupil

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

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

Queryforces!

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

wtf this is harder than a div2 contest

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

How to solve problem C?

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

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

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

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

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

So, how to solve D2?

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

    → Reply
  • »
    »
    5 years 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.net/contest/1196/submission/57674284

    → Reply
»
5 years 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.net/contest/1196/submission/57694392

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

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

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

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

I got 3 of them :(

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    how to slove it ?

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

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

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

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

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

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

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

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

    hhhhh

    → Reply
»
5 years 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.net/contest/1196/submission/57688661

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

    can you please explain your approach?

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

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

    5 3

    2 4 6 8 10

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

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

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

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

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

    1 4 2 1 3 5 4

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

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

Any hints on how to solve Problem F?

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

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

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

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

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

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

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

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

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

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

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

Someone really wants to get their opinions established in D2

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

    Implementation, implementation i esche raz implementation!

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

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

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

    Sometimes such shit happens. But do not be upset.

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

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

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

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

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

    No d1 solutions are very close

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

57693377 and 57690563 i think they are cheating.

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

How to solve problem E ?

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

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

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

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

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

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

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

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

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

    it cost me over 1 minute to show problemA

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

→ Reply
  • »
    »
    5 years 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.net/contest/1196/submission/57661674

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

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

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

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

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

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

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

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

    → Reply