Eran's blog

By Eran, 8 years ago, translation, In English

Hi everyone!

Codeforces Round #365 (Div.2) takes place today on 4th of August at 18:05 MSK. As usual Div.1 participants can join out of competition.

I am the author of all the problems, and this is my first round on Codeforces. I advise you to read all the problems, hope you will enjoy them :)

I'd like to thank GlebsHP and danilka.pro for helping me in preparing problems, MikeMirzayanov for the great Codeforces and Polygon platforms and IlyaLos for some useful adviсe.

In this round you will meet Mishka, a little polar bear. She is still young, that's why she may have some problems in finding answers for difficult questions. Will you help her to cope with some of them? :)

UPD. 5 problems, 2 hours to solve them and scoring distribution: 500 — 1000 — 1750 — 2000 — 2250

UPD. We apologize for the inconvenience. All solutions will be judged soon.

UPD. Round is unrated.

UPD. The contest is over. Congratulation to the winners!

Div1: 1. uwi 2. kmjp 3. savinov 4. BigBag 5. KrK

Div2: 1. meteor 2. TmEnd 3. chenjiamin 4. vokeal 5. Denisson

Editorial will be published in the nearest time.

UPD. Editorial

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

| Write comment?
»
8 years ago, # |
  Vote: I like it -210 Vote: I do not like it

First Comment!!!

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

    this is codeforces not youtube

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

      I wish high rating for everyone!!!

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

        Really sorry to say but your wish won't be granted until next round. Unrated :(

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

          I cursed this round. I am sorry Codeforces.

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

        At least nobody dropped!

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

      Ok, I knows. But codeforces is not always a rigid place.Some fun is ok. All in all, I am stronger than you.

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

      you stole my comment -_-

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

      Why are you being so rule... Don't you know he is human too??

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

    Anyone else having trouble submitting these problems for practice?

    It still says Pending System Testing for me...

    Edit: It's open for submitting now.

»
8 years ago, # |
  Vote: I like it -68 Vote: I do not like it

Let's Help Mishka

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

    Let's not decrease Contribution by this kind of comments!

»
8 years ago, # |
  Vote: I like it +47 Vote: I do not like it

May be it's 4th August, not 3rd?

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

Is the time correct? Edit: It's fixed now.

»
8 years ago, # |
  Vote: I like it -39 Vote: I do not like it

Hello i am rommel

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

    Hi Rommel! Where is Guderian?

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

Looking forward to a story of Limak and Mishka

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

Can somebody tell me how to hack?

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

    First you have to solve a problem. If you solved problem A, lock the problem A(in problem page) and go to 'room', double-click someone's (who solved problem A) source code, and click the "Hack!" button. Sorry for the bad english :(

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

    First of all, you need to pass the pretests on the problem you want to hack. When you are done, go to Dashboard and click the padlock which will be on the right of the problem's name. This way you will be able to open every submission for that problem made by someone in your room by going to Room and double-clicking on the cell showing the score and the time of submitting the solution but you won't be able to make further submissions on that problem for the rest of the contest. Also note that you won't be able to use too big test files so in this case you can use a test generator (I think you will see how during the contest), I didn't know that and finished 7th instead of top5 on one of my first contests.

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

    you can find it on google

»
8 years ago, # |
  Vote: I like it +246 Vote: I do not like it

Today's date: 22 / 23 / 24

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

    and division 21. The task is to take 20 place:)

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

      And the number of fucks given is 20-1

»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Nice context time, I can watch TI6 after the context :D

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

    I think it's contest, not context :D

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

    Haha I didn't expect anybody on this site of all places to be Dota fans :D

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone

»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Why you always announce scoring & duration &... just before the contest ?!

»
8 years ago, # |
  Vote: I like it -56 Vote: I do not like it

jibancanyang的后援会路过,坐看羁绊妹子上紫,后援会成员过来留言呀呀呀(excuse me...don't decrease my contribution.....haipa..

»
8 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Number of problems, duration and scoring distribution will be announced later. perhaps after contest :D

»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

What does 'Later' mean in Russian?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unique Timing...But where's the number distribution? :(

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

    scoring distribution: 500 — 1000 — 1750 — 2000 — 2500

»
8 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Delayed! :/

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

Is this the first contest on CF for which more than 7000 people registered?

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

    Good Bye 2015 had > 7000 participants (it's a Div. 1 + Div. 2 competition).

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

    Second one after the round that took place right after the color revolution

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Delay 15 minutes and the number of Contestants reach 7000+.

»
8 years ago, # |
  Vote: I like it -36 Vote: I do not like it

How does the world look through your eyes?

»
8 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Looks like it'll get cancelled or non-rated. I am going to sleep.

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

    todays contest should be cancelled!

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

      +1 to non-rating... 40 minutes for a TLE veredict... really annoying...

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

It's already 20 minutes while i'm trying to log in...

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

in queue for more than half hour whats happening

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I finished B in 10 minutes and successfully submitted it in 28 minutes...

»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Took 10 minutes to realize a simple wrong file.

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

There are more than 4000 submissions queued now :-"

»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

That feeling when the first 90 pages of status are "In queue" ...

»
8 years ago, # |
  Vote: I like it +124 Vote: I do not like it

Is it rated? :P

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

    now that's a good situation to ask such question =)

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

    May be the contest will be declared as unrated.

»
8 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Codeforces became so popular: Codeforces team should think about improving it's server or finding another smart solution :/

»
8 years ago, # |
  Vote: I like it +45 Vote: I do not like it

So this time it should be unrated right?

»
8 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Codeforces, please don't turn into Codechef.

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

That's not deal, I've submitted 45 mins ago, still can't get the result.., sad about that

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wow,very fast judging system!

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

It got passed while I was typing the comment:D

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

CFOI-_-

»
8 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Hmmm...... Huyum_nik?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Me off, cause it will be unrated 90% and cause I got no deal with any bitwise ops(C) (that's my mistake I can't really make myself learn something about bitwise ops..), and got no idea how to solve (D) and (E).

»
8 years ago, # |
  Vote: I like it +65 Vote: I do not like it

After 45 minutes, it finally show the result of my B... And the verdict is wrong anwser on pretest 4 :'(

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

    I accidentally read your nick name as "I am Wrong". Would have fit to your WA perfectly... No offence :)

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

    Maybe, you should have sent a correct solution? There are lines because of such people who send wrong programs.

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

      You are quite interesting...

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

finally , i can see my solutions result. (after 30 min)

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

After 45 minutes from submitting B, I find out that it's a WA. :D
Got B Pretest Passed 10 minutes ago and still not appearing on standings that I solved it. :D
Is it rated? :D
UPD1: Oh, my B solution is being rejudged.
UPD2: Oh, my B solution has been running on test 1 for over 5 minutes now
UPD3: Pretest passed again and still not showing on standings. -_-.
What a nice rated round. :D

»
8 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Can anybody analyze the time complexity of this problem?

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

Did anyone hack successfully?

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

    Submissions sticking on queue for 45 minutes, and you want hacks? :D

»
8 years ago, # |
  Vote: I like it +135 Vote: I do not like it

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

Time limit in D is so bad :( n log n solution with segment tree

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

    its not , it has a simple N+QlogN solution.

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

      Segment trees. I wish I could code it

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

      Care to explain ??

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

        xor of all dinstinct elements occuring even number of times is equivalent to xor of all distinct elements xored with xor of all elements occuring odd number of times , xor of distinct elements occuring odd number of times is just xor of the whole subarray , so you need to find xor of all distinct elements of a subarray , this can be done offline in N+QlogN in the same way as finding number of distinct elements of a subarray

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

          This can be online with segment tree log^2

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

            This can also be online with persistent segment tree in per query.

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

            can you elaborate? the online segtree lg^2 solution

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

              Store all nexts (index). Distinct values [l, r] is number of nexts that next[i] (l <= i <= r) > r. This can be with upper_bound. O(log^2) for each query

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

            Are you sure? I thought so too at first, but I found a problem with my idea... You might be thinking something completely different though, which is why I'm curious :D

            My flawed solution: Store a set in each node of the segment tree. Add all values on the node's segment to its set. This takes O(n log^2 n) time. And when you make a query, you only need to look at log n sets.

            The problem with this: Unless I'm missing something, you can't merge those log n sets efficiently, or get the solution for the entire queried segment from their subsolutions in any other way.

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

          You see the hardest part of this question was to compute the xor of distinct elements. can you elaborate on how you do that offline?

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

            sort queries according to right end point , now go from 1 to N , if arr[i] has occured before , remove arr[i] from last occurance of arr[i] and put arr[i] at i , now for all queries ending at i , xor of distinct elements from l to i is just query(l , i). this can be done easily with a bit

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

      Will you please explain?

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

      Explain++

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

    yep, TLE at test number 14 :( I used BIT Q*logN as well and not pass

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

i don't know why i was forcefully logged out. First submission to problem A: 00:03 & passed pretests at 01:06 anyone else was forcefully logged out every now and then?

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Did anyone manage to get through n * sqrt(n) for problem D? Is it even possible to get through 10 ^ 9 operations like that? Spent whole contest trying, guess it is not possible for me. In c++ ran in 7 seconds locally.

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

    I got tle on test case 15 with Mo algorithm. Then switched to (n + q)logn and it passed for pre tests. Was something like counting distinct number in range but xor of those values.

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

      Same for me, couldn't get O(Q sqrt N) to pass

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

      I was thinking of how to find xor of distinct numbers in a range, but failed to. Now I've only solved problem A :(. Mind explaining how you got it?

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

        It is similar to this: http://www.spoj.com/problems/DQUERY/ Read this: http://codeforces.net/blog/entry/8962 for an offline approach. Here in this problem, just need to use segment tree to update an element at index and calulate xor of a range using segment tree

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

        Keep a XOR segment tree: when you encounter a value for the first time, on index i, in the segment tree update the position i with that value, and rememember that last[ arr[i] ] = i;

        And if you've already encountered the value before, also update the position last[ arr[i] ] with the value before updating last[ arr[i] ].

        After processing each index i, you can answer all queries that have r = i. You will only ask the segment tree for some query(l, i), in other words, your right bound is fixed.

        Personally I did it with BIT, not a segment tree.

»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Getting WA after about 45 minutes!! I only took a minute to debug my code ... of course not that long That really kills :v :3

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

How to solve C? Heck i can't even write a bruteforce solution :\

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

    I used binary search on time before start walking UPD: As I can see there are some easier solutions than mine. Nevermind)

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

    Try transforming the problem into the new coordinate space (Time, Y). That is, the first coordinate X is time and second coordinate Y denotes the same thing (distance from bottom to top).

    I will write a more detailed explanation (with a picture) after a few hours (I'm still working =)) if nobody writes satisfactory explanation.

    PS: no need for binary search.

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

    Imagine that the x axis represents time. If the pedestrian walks at full speed straight up, he'll move with a slope of u/v. Then, you can easily check if he can walk in front of the bus (this line is to the left of the entire bus) and, if he can't make it in front, how long he has to wait for each vertex of the bus to pass (horizontal distance between the line and vertex).

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

    For each vertex, find if it can reach the vertical line before the person can pass the point at which this vertex will intersect with the line. If no/all points satisfy the previous statement, then the person can pass before/after the bus with full speed. Otherwise, you have to go after the bus with different speeds. Start with the lowest (and rightmost in case of a tie) vertex and check the point at which it will meet the vertical line. If you can arrive to this point in a time earlier than the vertex reach time, wait for this vertex to pass the line. If the vertex reached it earlier, then you can move with max speed. Consider vertices in counter-clockwise direction and stop when you pass the highest vertex (at this moment go the remaining distance with full speed).

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

    Instead of moving the bus, just consider the guy to be moving. As the bus is convex we can see that it is optimal to be still for a while and then move at maximum speed. Then we only need to see for how long do we need to wait. Again, as the bus is convex, we just need to see the time needed to pass right through each point and store its maximum (for point (X,Y) it will be X/V-Y/U). Thus, if we can't just walk from time 0, (i.e. among the values calculated there is a positive and a negative value) we will need the maximum value calculated plus W/U, else its just W/U. (sorry for possible errors, first time commenting :) )

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

    Supplement visual guide to the comments above :)

    Transformation of the pedestrian's path.

    Strictly vertical path in XY-plane becomes tilted to the right in the TY-plane.

    Convex bus undergoes absolutely the same transformation, but it doesn't become tilted! After that we should look at the intersections of the transformed figures.

    Here is neat solution of the guy from MIT : 19629479

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

is it rated?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D??

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

    I use a similar offline-algorithm like http://www.spoj.com/problems/DQUERY/ try to calculate the XOR-sum of distinct number in a segment then the ans = the XOR-sum of distinct number in a segment ^ prefix[r] ^ prefix[l — 1]

    prefix[i] means a0 ^ a1 ^ a2 ^ ... ^ ai

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

I liked B and C but don't know how to solve D. There are so many ideas in my head with different time and memory complexities using huge amount of build-in data structures and written by my own but nothing of this, I guess, can pass tests. Please help me. What is your solution for D? UPD: I think, because of 15 given additional minutes, round must be rated.

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

    Did you use Convex-hull in C?

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

      You don't need to compute convex hull, if you are already given a convex hull ;)

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

        Oh, i'm sorry. I mean traverse convex-hull clockwise to get the answer.

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

        But there can be some good ideas using parts of Graham's scan

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

      No, as I said above, I used binary search on time before start walking and check used simple geometry like oriented triangle area

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

let's convert it to unRated one :D

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Did anyone else feel this contest was hard?

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

    Yes I solved only problem A and bugged for B ;(

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

      Same. And it didn't help that I thought my B was pretests passed for an hour and then realized it was actually WA and couldn't figure out how to finish it. Pretty hard contest imo.

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

Anyone who's D's solution passed in spite of using cin and cout ? I did use segment trees, got TLE on pretest 10.

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

19633422 can u tell me why my solution for D task is so slow?

Now work:) printf and scanf. I thought that cout/cin is faster with ios_base::sync_with_stdio(false) than printf/scanf

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

    Could try printf / scanf, the input is huge.

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

    I have been in similar situation, you can try two optimizations: 1. Use scanf and printf instead of cin and cout. 2. Use dynamically allocated array using malloc, new or global array instead of vector. Time limit problem will most probably go away. And segment trees are slow(not asymptotically but practically) so you will most probably have to do these optimizations whenever using them.

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I thought it will be a unrated so i stopped doing contest after submitting B and start watching a movie. Now one a mine facebook friend ping me and realize me that it won't, pathetic :(

»
8 years ago, # |
  Vote: I like it +110 Vote: I do not like it

This was evil! I was about to hack this :P

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

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

    How do you hack this?

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

      You don't. Because you are aiming for int overflow but, since the defender has defined int as long long, your hack will fail.

»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

It would be such a shame if Codeforces ignores the mistakes and makes the round rated. :)
btw i'm saying this although I did good and I would benefit if it's rated
And for god sake, why the hell isn't my pretest passed showing on standings?!

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Please, lets convert this round to unrated.. Because long checking and many bugs..

»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

this contest should be declared unrated .

»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Making this round rated proves how unserious this website is

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

    the terms was equal for everyone. you guys are not logical :/

»
8 years ago, # |
  Vote: I like it -31 Vote: I do not like it

this round was the worst round ever the server dies what is this shit !!!!!!! :(

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

thanks for offering the problems,i like this contest,especially problem D,

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

How to solve E?

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

    I think it's dynamic programming, suppose k=p_1^a_1....p_s^a_s let F(b_1,b_2...b_s,w) be the minimum number of integers among a_1,a_2...a_w you should pick to make the number a multiple of p_1^b_1.....p_s^b_2. That works to get the minimum number of integers needed, although I'm not sure how to change it to get the actual set of number.

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

      This can be easily represented as divisors of the input k, which can be found in time at first.

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

    Just solved E using iterative DP with state[index,value to make] with scary timing..!! :3 from the looks of it there should be a faster soln i think..!! :/

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

    I solved it by bitmaks dp, since 2*3*5*7...*31*33 > 10^12 , so it should probably fit in the time limit. I can't submit it check though, I've heard that the TL is pretty tight.

    And lucky me just read this question's (Here) editorial and learn the approach, and yes you read it correctly, this question has a similar constraint yet a 2 second TL ...

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When after submitting A , my submission list was empty ,it was such a relief. But after 10 min my friend told me I have one submission pending I knew from that moment that this contest will judge my patience :P

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish that Codeforces judging system were faster so that I could submit my solution 1 minute after the contest had ended.

BTW Is there a way to submit a solution quicker after the contest ends?

»
8 years ago, # |
  Vote: I like it +163 Vote: I do not like it

It seems long queue affected many participants of the contest. I counted number of users which got verdict after 15 minutes of waiting and verdict was non-OK. It is about 2000 participants.

Taking into account such a significant number, we've decided to make round unrated. Sorry about it.

Today long queue is not a systemic issue, it is a result of several unsuccessful matches. Be sure, I'll do my best to make the next round quickly judged.

====

Похоже, что длинная очередь существенным образом задела большое количество участников. Я посчитал у скольких участников тестирование было в очереди более 15 минут, а затем был получен вердикт не-OK. Таких участников около 2000.

Принимая во внимание такую значительную цифру, мы решили сделать раунд нерейтинговым. Приносим извинения за это.

Сегодняшняя проблема с очередью не системная, а результат нескольких неудачных совпадений. Можете быть уверены, я приложу все усилия, чтобы следующий раунд тестировался быстро.

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

    nrO Mike Orz

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

      Dear Mike, I submit twice because of in queue judgement. Both of them passed pretest, at 47min and at 101min, but why it shows the time of the last one,at 101min?

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

        You're second submission is considered as a resubmission which costs penalty and the first submission will be ignored.

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

    thanks :)

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

    Nice, last time when I didn't do well, it was rated, this time when I do well its, unrated. This is life I guess..Highly unfair

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

      What if you get all FST?

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

        All my solutions passed, sorry for ur pessimist attitude

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

          So when you passed all the solutions, you say that 'Mike you should make it rated'.I just do not think it is fair in that I don't believe if you, unfortunately, get FST, you will still say that.

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

      Same here. I thougth that I'd become blue again :)

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

    Make it optionally rated please.This is so wrong

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

      Why wrong? Getting WA in the middle of the contest at a very easy problem affects a lot your standings,not mentioning that codeforces was loading a page in about 2 minutes.

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

      Usually when these things happen on a site that involves some type of competition, you have to take a decision. Implementing both is very impractical. Do you realise how much time would it take to manually update rating for everyone who wants? and putting a time implementing a feature for it so just when only something like this happens it is used, is a waste of time and money. ( And it's also not fair, because if some people could actually submit solutions, your rank might probably be a little bit down).

      These issues rarely happen on CF. Just deal with it as if it was an ED round. No big deal, if you did well this time, you can pretty much do it again in future contests.

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

    khar :/

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

    What does "unsuccessful matches" mean ?

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

    How are solution judged? I saw pretestes passed submission for A increasing which show that judgement was going on. However no solution appeared for like first 45 min for B. Isn't it by submission time?

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

    In my opinion people who got problem 1 or 2 wrong deserve to lose rating, but it's not a big deal either way.

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

    It is the second time when I do well in contest and then it becomes unrated.

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

    Mike why won't you try load balancing to more VMs, from example amazon web services or smth similar. They'd be probably necessary only for the first hour of the competitions when the load is quite bigger.

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

    То что была задержка 15 минут, это не так много в тем более это было в начале ближе к середине и еще добавили время. У кого не прошло решение, и они ждали около 15 минут, они все равно знали об этом еще во время контеста и у них было много времени что бы исправить это. Это единственный контест где я так хорошо написал для себя, (никогда не был топ — 50) и сидел до очень поздней ночи что бы написать нерейтинговый контест и еще ждать пару часов своих результатов и потом увидеть что " UPD. Было принято решение сделать раунд нерейтинговым. ". Бомбит ужасно!!!

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

      Я узнал вердикт через 50 минут,ещё и 15 минут ждал чтобы послать.

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

        Это ведь было только в первой середине контеста.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that I solved B, but 10 seconds after the contest over when I try to submit it.

I will submit it again when system testing is over,, I'll be sad if I got Accepted verdict...

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's may be the worst feeling when your code remain in queue for a long time.

»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Anyone can see disappearing Huyum_nik message at the first place in comments? It appears on my screen for a second and then disappears until I reload the page.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As soon as i tried to submit solution i got logged out showing apache format error and since after repeated trying manage to submit after 40 mins later. May be same case with some other peoples too so would it be called a fair codeforces rated round ?? :-(

»
8 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Something strange.... int this codeforce round.... WHO TO CALL??????

(Just a relaxing comment,don't take it so seriously Xp)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

woops, got wrong answer on C because I used int instead of long long, to check if the dude could pass before the car arrived.

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

    why not double

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

      I wanted to avoid precision errors, I just checked if X[i]*u >= Y[i]*v.

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

Were the submissions in a queue, or in a stack? :p :D http://imgur.com/t9AsTHt

PS: I don't know how to paste image here, can anyone please help me?

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

I think the problems for this round were pretty good (I struggled quite a bit honestly) but it sucks that the server was garbage the entire time. I didn't even know my B was WA until more than halfway through the contest. Overall, lots of nice problems just horrible circumstances. Hopefully Eran can write some more problems another time.

Edit: An editorial will still be released as well right?

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

    I agree! The problems were excellent — hopefully they can come back for another round :)

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

      what нахуй exellent problems?? просто realization

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

The round is unrated.I wish I can get higher rating but failed. :) I wish next round is rated! :)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked the concepts of the problems, they were very interesting, but I have a couple observations to make:

  1. As everyone has said, the servers were complete garbage, though this isn't the fault of the writers.
  2. I think the design for problem D was kind of bad, because you have a very large input, and at the same time large numbers. I had to use a map for the occurrences, which led to TLE on test 50. If the numbers in the array were to be at most, say, 1.000.000, there would have been no problem, but by making the numbers as large as a billion, you are making the problem harder and the time complexity greater for no real purpose. For both large input and large numbers, the time limit was too tight.

But I think the writers have good potential! They are able to write hard, interesting and complex problems. I wish them luck in the next rounds they will (hopefully) write.

P.S. I find it is in good taste to make the round unrated, mostly because of the huge server issues. Thank you for that.

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

    If 1 ≤ n, q ≤ 2 × 105 on D then Mo's algorithm will pass easily but i think this way the problem will be very stupid,just apply a well known algorithm.

    The limits are ok,i looked at your code and saw that you used map of vectors but it is very very slow.

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

    Yes also 1 <= N , Q <= 1.000.000 made the time limits even tighter

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

:c

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

    Sorry for that, it just burned quite a lot.

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When will the problems moved to practice and editorials published ?

»
8 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Congratulations for what? For doing the best round in their lives only to realise its unrated?

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Although there was sure some inconvenience, I still think it a good contest~ Many thanks to contributors~~~

The delay and some other problems are largely due to the large number of participants and div 2 only. It doesn't affect that CF is still a great community to improve coding skills. It just mean that this site is becoming more and more popular and the server need to be upgraded. I think we should support the site rather than complain the organizer or the limited source of the site.

That's it. Just feel a little sad seeing so many people blame the organizer and the site.

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

Is the testing gonna end any time soon? I was hoping to submit some code.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem no B 703B - Mishka and trip , Why my this submission : 19639339 got accepted verdict but this implementation, 19639538 , got wrong answer? When I used cin/cout its got accepted , but for scanf/printf it gives me wa verdict. Please help .... Thanks in advance.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Round is UnRated !!!? (Unusual)

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

    Because life can be cruel sometimes, but you need to tough it out.

»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Why unrated? It's unfair...

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

    It's unfair... that's Why unrated !

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it really that the contest was unrated?

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope the editorial will not come out as late as the number of problems,duration and scoring distribution did.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well,Why is the time limit of E is 1s? Some of the Accepted source takes 997ms to passed.And I was TLE because of the large constant.QAQ There are same people's Sources didn't Accepted because of the same reason.Could you make the time limit longer?

These are Accept Sources: 19634240 19636289

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I am not quite familiar with geometry stuff, I wonder what's the idea behind judging if the point we are checking is the front or the back of the bus?

Edit: I think I have an idea now... Almost forgot about high school maths. Btw, is everyone else's contest page show "pending for system test" right now?

Edit2: Just noticed "input are given in counter-clockwise order" FML

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

    Could you explain your idea please? That problem had me completely stumped.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 6   Vote: I like it +1 Vote: I do not like it

      My implementation: http://ideone.com/mFVRYD

      (I can't submit it right now — it says the contest is still pending for system test, so I can't guarantee this code is bug free, as I always miss out small counter-case details. I am pretty sure the approach is correct though.)

      Case 1: The pedestrian will not get hit by the car if he rushes through as fast as possible — in this case we just have to check whether he will reaches point (0,y) earlier than each (x,y) of the car.

      Case 2: The pedestrian will have to wait for the car to past through first.

      In this case we just consider everything as the back of the car, and sort all the vertices in increasing y-axis value. Then you just check for the later event — the pedestrian reaches point (0,y) or the point (x,y) of the car passes (0,y). And as a smart-aleck I missed this obvious observation when I coded, instead I did the following in my code.

      We can check from the lowest point of the car, the sequence of edges which starts from it and has a positive slope is the parts where it could possibly "limit" the pedestrian speed as a part of the back of the car. (This is because it is guaranteed the vehicle is a CONVEX POLYGON, and it is convenient to implement since the edges are given in counter-clockwise order.) Again we check for the later among the two events mentioned above — it's fine to just check these points anyways. Don't forgot to calculate for time (0,0) -> (0,ymin) and (0,ymax) -> (0,w)

      UPD: Just rewrote the code in a much more simple fashion, this should be easier for anyone to understand the idea. http://ideone.com/ZjTybR

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

        My idea is similar. I implemented it during the contest but after my solution, which past pretests, was judged with the system tests gave WA#12. I too have the problem with still pending system testing as I wrote below. Here is my implementation:19631048.

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

          I think you miss out cases where miny>=w and mawy>w.

          Here is a hack case for you:

          5 1 1 2 1 2 3 1 4 3 3 4 1 4

          It's just the test case 1 with w=1, the pedestrian is able to rush to (0,1) with ease, yet your code outputs 3.0s.

          (Whopos just read the constraints again... nvm it's guarantee every y<=w)

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

            OK. So there has to be something else that is wrong.

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

            I found out my mistake (it was in the second case). Here is the AC implementation: 19664924 (complexity: O(n))

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm new here, why is the contest unrated? Because of the delay time caused by long queue?

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

    Probably yes, since it has cause unfairness in terms of rewarding points.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How many machines does Codeforces have?

»
8 years ago, # |
Rev. 5   Vote: I like it -16 Vote: I do not like it

Unrated :(

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

    There were amazing beautiful problems which worth thinking! rating isn't the priority always!!!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem no B 703B - Mishka and trip , Why my this submission : 19639339 got accepted verdict but this implementation, 19639538 , got wrong answer? When I used cin/cout its got accepted , but for scanf/printf it gives me wa verdict.what is wrong with it?Could anyone explain please ? .... Thanks in advance.

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

    you made array with a variable as the size!!!! amazing!!! i don't know but maybe the problem is from this miracle!!!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there someone else having trouble submitting code now?

It just says 'You can't run practice now or contest does not support practice.'

I see some submissions, but I can't submit still.

  • »
    »
    8 years ago, # ^ |
    Rev. 7   Vote: I like it +6 Vote: I do not like it

    When I enter yesterday contest now, it still says pending system testing (and of course I can't submit and see what are the tests of the tasks). Maybe there are more people with this problem. I found that this problem is on the devices (my laptop and tablet) where yesterday I was checking the standings for a lot of time and for example if I open codeforces on my phone, there is no such problem. Could someone offer me some advice or a way to fix it?

    UPD: Now the problem mysteriously disappeared. Finally the contest finished for me :). Does someone still have this problem?

    UPD2: The problem returned again.

»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Please Switch on Practice for this contest.
It shows Contest not over and you cant practice

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is O(N * (number of divisors of K)) supposed to pass in E?

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

    Our correct solution has complexity O(n * divisors(k) * primes(k)). I will try to publish editorial as soon as possible.

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

      WTF, so the problem is only optimization!

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

        Well... That's it! We decided that otherwise it will be too easy for the Div2E.

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

      Do you think excluding O(n*divisors(k)*log_gcd) solutions was a good idea with author's O(n*divisors(k)*primes(k))?

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

        Yep. We tried to exclude such solutions. However it seems like not all tests were good enough.

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

          Guessing author's constant optimizations — yeah, it is what problem E must be.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This round turns into unrated! it's so disappointing!i hope this type of inconvenience won't happen again :/

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Someone help me understand... Why is the contest still pending system tests? I can't even submit a solution now. O__O

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Its taking forever for the system testing to finish. I am not able to submit solutions to any of the answers to yesterday's contest.

»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Why one day after contest it's on "pending system testing" level?!

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

Please publish the editorial and allow to submit the solution.It is almost a day now... UPD :- It is published now....

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will O( N SQRT(N) ) work for D?

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

    No. I had n log n and tle

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

      what was your nlogn idea? you must be calculating it wrong, the intended solution is nlogn itself.

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

        I sort queries. I have segment tree which can make xor on range and can return xor value of range. I iterate through input data and do xor(1,last_place[input [i]], input [i]). In i step I have in tree data about xor(only for numbers with even amount of occur ) for ranges [1,2,3,...,i;i]. Now i can just check valueInTree(query[i].start,query[i].start).

        Now work:) printf and scanf. I thought that cout/cin is faster with ios_base::sync_with_stdio(false) than printf/scanf

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

    Can't you just check it yourself? Just multiply them, ...and tada, the answer appears within a second!

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

      i understand its 10^9 but it is a bit peculiar that the time limit is 3.5 seconds and looks like it is so to make such solutions run

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

I have provided an explanation to problem D here

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Still pending system testing. Why is this problem caused and is there some solution?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial Please ..!!

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

    Editorial is ready, but there are some problems with displaying it. Still waiting fixes.

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

      Thank you! It's so nice when authors answer the comments.

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

      Please allow us to submit solutions now

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

Has anyone solved Div2D with persistent segment tree . My submission (Code) is giving Runtime Error on TestCase 14.I don't have any clue of the reason and have allocated more than enough memory (I think). The idea of pst's root[i] is to store xor of distinct numbers which are as close to it as possible.

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

    Look at constraints, 211111 is not enough.