Eran's blog

By Eran, 14 months 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 dans 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. laekov 5. Denisson

Editorial will be published in the nearest time.

UPD. Editorial

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

»
14 months ago, # |
  Vote: I like it -210 Vote: I do not like it

First Comment!!!

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

    this is codeforces not youtube

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

      I wish high rating for everyone!!!

      • »
        »
        »
        »
        14 months 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 :(

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

          I cursed this round. I am sorry Codeforces.

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

        At least nobody dropped!

    • »
      »
      »
      14 months 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.

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

      you stole my comment -_-

    • »
      »
      »
      14 months 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??

  • »
    »
    14 months 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.

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

Let's Help Mishka

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

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

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

      Yes.But What gets Downvoted no one knows :v

»
14 months ago, # |
  Vote: I like it +47 Vote: I do not like it

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

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

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

»
14 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Hello i am rommel

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

    Hi Rommel! Where is Guderian?

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

Wish all of us can have a good rating after the contest.

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

Looking forward to a story of Limak and Mishka

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

I will be back

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

Can somebody tell me how to hack?

  • »
    »
    14 months 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 :(

  • »
    »
    14 months 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.

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

    you can find it on google

»
14 months ago, # |
  Vote: I like it +246 Vote: I do not like it

Today's date: 22 / 23 / 24

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

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

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

      And the number of fucks given is 20-1

»
14 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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

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

    I think it's contest, not context :D

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

    I wish I can go to Seattle next year:D

  • »
    »
    14 months 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

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

      Not only div2 participants play dota. For example Overtroll is a very good guy with 5k)).

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

      Lots of my local OI team trainers are LoL players too.

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

Good luck everyone

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

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

»
14 months ago, # |
  Vote: I like it -56 Vote: I do not like it

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

»
14 months 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

»
14 months ago, # |
  Vote: I like it +17 Vote: I do not like it

What does 'Later' mean in Russian?

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

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

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

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

»
14 months ago, # |
  Vote: I like it +31 Vote: I do not like it

Delayed! :/

»
14 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I think just now the problem setter has finished his virtual contest of this round !!

»
14 months 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?

  • »
    »
    14 months 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).

  • »
    »
    14 months 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

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

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

»
14 months ago, # |
  Vote: I like it -36 Vote: I do not like it

How does the world look through your eyes?

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

    What the fuck is the deal with those inane comments?

»
14 months 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.

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

    todays contest should be cancelled!

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

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

»
14 months 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...

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

in queue for more than half hour whats happening

»
14 months 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...

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

Took 10 minutes to realize a simple wrong file.

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

There are more than 4000 submissions queued now :-"

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

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

»
14 months ago, # |
  Vote: I like it +124 Vote: I do not like it

Is it rated? :P

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

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

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

    May be the contest will be declared as unrated.

»
14 months 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 :/

»
14 months ago, # |
  Vote: I like it +45 Vote: I do not like it

So this time it should be unrated right?

»
14 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Codeforces, please don't turn into Codechef.

»
14 months 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

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

wow,very fast judging system!

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

It got passed while I was typing the comment:D

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

CFOI-_-

»
14 months ago, # |
  Vote: I like it +59 Vote: I do not like it

Hmmm...... MAXIMAN?

»
14 months 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).

»
14 months 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 :'(

  • »
    »
    14 months 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 :)

  • »
    »
    14 months 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.

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

      You are quite interesting...

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

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

»
14 months 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

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

Can anybody analyze the time complexity of this problem?

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

Did anyone hack successfully?

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

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

»
14 months ago, # |
  Vote: I like it +135 Vote: I do not like it

»
14 months 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

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

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

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

      Segment trees. I wish I could code it

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

      Care to explain ??

      • »
        »
        »
        »
        14 months 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

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

          This can be online with segment tree log^2

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

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

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

            can you elaborate? the online segtree lg^2 solution

            • »
              »
              »
              »
              »
              »
              »
              13 months 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

          • »
            »
            »
            »
            »
            »
            14 months 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.

        • »
          »
          »
          »
          »
          14 months 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?

          • »
            »
            »
            »
            »
            »
            14 months 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

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

      Will you please explain?

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

      Explain++

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

        This problem requires the result of the XOR elements that appear an even number of times in the segment ...
        we know that the XOR of an even number of the same element is null and of an odd number of the same element is equal to that element.
        for example :
        1010 XOR 1010 = 0
        Then 1010 XOR 1010 XOR 1010 = 0 XOR 1010 = 1010
        So, in each segment, you must do the XOR of all the elements with XOR distinct elements of this segment ... (because the XOR function works in the opposite way to that of the problem)
        for example :
        3 3 2
        The number of separate elements is 2 (3 and 2)
        Answer: 3 ^ 3 ^ 2 ^ 3 ^ 2 = 3
        To find the different elements, you can use MO's algorithm or persist segment tree or sorting segment (or BIT or sqrt sparse decomposition or table)) and use the OFFLINE method (stores the queries you're doing and sorting) you can do dquery od spoj first to get the main idea...
        Note: MO's algorithm is slow to the constraints of the problem ...

  • »
    »
    14 months 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

»
14 months 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?

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

    Me Too

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

    Yes..During the competition,I can't log in.....T_T

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

    Yep happened while i was submitting B :| Then after 5 minutes, adding www. worked though

»
14 months 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.

  • »
    »
    14 months 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.

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

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

    • »
      »
      »
      14 months 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?

      • »
        »
        »
        »
        14 months 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.com/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

      • »
        »
        »
        »
        14 months 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.

»
14 months 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

»
14 months 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 :\

  • »
    »
    14 months 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)

  • »
    »
    14 months 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.

  • »
    »
    14 months 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).

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

    Felipe solved it using a well known algorithm named rotating callipers and a sweep line over every x coordinate of the polygon to get the points where the speed changes, finally a simple binary search over those points ;) Good Luck!

  • »
    »
    14 months 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).

  • »
    »
    14 months 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 :) )

  • »
    »
    14 months 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

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

      can u please elaborate?

»
14 months ago, # |
  Vote: I like it +12 Vote: I do not like it

is it rated?

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

How to solve D??

  • »
    »
    14 months 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

»
14 months 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.

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

    Did you use Convex-hull in C?

    • »
      »
      »
      14 months 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 ;)

      • »
        »
        »
        »
        14 months 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.

      • »
        »
        »
        »
        14 months 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

    • »
      »
      »
      14 months 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

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

let's convert it to unRated one :D

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

Did anyone else feel this contest was hard?

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

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

    • »
      »
      »
      14 months 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.

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

    NO ,,, its funny :D :D :D lots of errors :D

»
14 months 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.

»
14 months 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

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

    Could try printf / scanf, the input is huge.

  • »
    »
    14 months 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.

»
14 months 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 :(

»
14 months ago, # |
  Vote: I like it +110 Vote: I do not like it

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

»
14 months 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?!

»
14 months 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..

»
14 months ago, # |
  Vote: I like it +24 Vote: I do not like it

this contest should be declared unrated .

»
14 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Making this round rated proves how unserious this website is

»
14 months 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 !!!!!!! :(

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

    Why do you care if you didn't participate?

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

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

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

How to solve E?

  • »
    »
    14 months 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.

    • »
      »
      »
      14 months 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.

  • »
    »
    14 months 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..!! :/

  • »
    »
    14 months 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 ...

»
14 months 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

»
14 months 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?

»
14 months 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.

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

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

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

    nrO Mike Orz

    • »
      »
      »
      14 months 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?

      • »
        »
        »
        »
        14 months 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.

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

          okay, never mind, unrated:D)))))))))))))))))

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

    thanks :)

  • »
    »
    14 months 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

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

      What if you get all FST?

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

        All my solutions passed, sorry for ur pessimist attitude

        • »
          »
          »
          »
          »
          14 months 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.

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

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

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

    Make it optionally rated please.This is so wrong

    • »
      »
      »
      14 months 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.

    • »
      »
      »
      14 months 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.

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

    khar :/

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

    What does "unsuccessful matches" mean ?

  • »
    »
    14 months 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?

  • »
    »
    14 months 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.

  • »
    »
    14 months 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.

  • »
    »
    14 months 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.

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

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

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

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

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

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

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

      کیرم تو استایل تخمیت

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

    Kiram laye moohat mike

»
14 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I just want to ask why

»
14 months 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...

»
14 months 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.

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

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

»
14 months 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 ?? :-(

»
14 months 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)

»
14 months 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.

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

    why not double

    • »
      »
      »
      14 months 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.

»
14 months 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?

»
14 months 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?

  • »
    »
    14 months 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 :)

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

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

»
14 months 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! :)

»
14 months 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.

  • »
    »
    14 months 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.

  • »
    »
    14 months 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

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

:c

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

    Sorry for that, it just burned quite a lot.

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

When will the problems moved to practice and editorials published ?

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

Why unrated ?

»
14 months 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?

»
14 months 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.

»
14 months 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.

»
14 months 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.

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

Why Round is UnRated !!!? (Unusual)

  • »
    »
    14 months 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.

»
14 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Why unrated? It's unfair...

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

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

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

Is it really that the contest was unrated?

»
14 months 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.

»
14 months 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

»
14 months 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

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

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

    • »
      »
      »
      14 months 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

      • »
        »
        »
        »
        14 months 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.

        • »
          »
          »
          »
          »
          14 months 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)

          • »
            »
            »
            »
            »
            »
            14 months 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.

          • »
            »
            »
            »
            »
            »
            13 months 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))

»
14 months 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?

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

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

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

How many machines does Codeforces have?

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

Unrated :(

  • »
    »
    14 months 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!!!

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

    Please don't curse Codeforces. Don't you think that it would have been so unfair if this contest was rated? Besides, is rating really so much important? Think about the happiness which you obtain after solving a problem! :)

»
14 months 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.

  • »
    »
    14 months 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!!!

»
14 months 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.

  • »
    »
    14 months 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.

»
14 months 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

»
14 months 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?

  • »
    »
    14 months 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.

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

      WTF, so the problem is only optimization!

      • »
        »
        »
        »
        14 months 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.

    • »
      »
      »
      14 months 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))?

      • »
        »
        »
        »
        14 months 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.

        • »
          »
          »
          »
          »
          14 months 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.

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

      wait for editorial

»
14 months 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 :/

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

»
14 months 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.

»
14 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
14 months 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....

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

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

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

    No. I had n log n and tle

    • »
      »
      »
      14 months 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.

      • »
        »
        »
        »
        14 months 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

  • »
    »
    14 months 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!

    • »
      »
      »
      14 months 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

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

I have provided an explanation to problem D here

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
14 months 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?

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

Editorial Please ..!!

  • »
    »
    14 months 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.

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

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

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

      Please allow us to submit solutions now

»
13 months 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.

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

    Look at constraints, 211111 is not enough.

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