Topcoder Single Round Match 681

9 лет назад, # ^ |

Does not seem good to me :( Can't log in :(

→ Ответить

dush1729

9 лет назад, # ^ |

← Rev. 3 →

Same here ;_; Unable to launch arena.

→ Ответить

9 лет назад, # |

← Rev. 2 →

Before start of challenge phase plugin froze for me. Now I can't log back in :/

→ Ответить

SandorGarcia

9 лет назад, # |

I could not compile during the last 2 minutes, I got something like server busy, is this common in topcoder??

→ Ответить

MathCrusader

9 лет назад, # ^ |

Me too. I was trying to upload a fix to my solution, but couldn't before time ran out. The worst part was there was more than 4 minutes left when I was trying to upload. haha, oh well. I've been competing on TC for a while and this hasn't happened to me before.

→ Ответить

mrgreen

9 лет назад, # |

Unable to launch arena

→ Ответить

MathCrusader

9 лет назад, # ^ |

Try the Web Arena. It works for me, but the Applet doesn't.

→ Ответить

mrgreen

9 лет назад, # ^ |

pfff, unrated anyways.

→ Ответить

motherofgod88

9 лет назад, # |

java applet doesnt work, use www.arena.topcoder.com

→ Ответить

fruwajacybyk

9 лет назад, # |

Are there any official announcments? Is challange phase canceled?

→ Ответить

KOTEHOK

9 лет назад, # ^ |

+14

They sent the following: "Challenge phase will be starting as currently scheduled. Given the frequency of issues (and the fact that access to topcoder.com was actually down for several mintues), the match will have to remain unrated today."

→ Ответить

bas

9 лет назад, # ^ |

Round unrated, challenge starts in 2 min.

→ Ответить

9 лет назад, # |

Match today is unrated, as per announcement.

→ Ответить

minimario

9 лет назад, # |

+11

Well...how to solve Div 1. 250? I thought of Binary Search, but I couldn't find good way to check if something could be attained.

→ Ответить

totsamyzed

9 лет назад, # ^ |

← Rev. 2 →

+11

Yes, binary search is good.
Now swipe left to right, when at position p, add segments which begin here in a set.
Now to get mid at current position you should always take from segment with minimum r (I don't know any formal proof, but it's right intuitively)
Whenever you can't take, stop and say that mid is bad.
Also, after processing position p, remove the segments which over here from your set.
By the way, it reminds me of this problem

→ Ответить

aranjuda

9 лет назад, # ^ |

Proof for that is easy. Suppose there are 2 segments A and B. Both have the same left end-point 'p1' but end-point for B 'p3' is > end-point for A 'p2'.

Let's say you can allocate k points from each. And m = p2. Also, let's assume: distance(1 -> p2) = k distance(p3 -> m) = k Now, if you allot points from B first, you will exhaust all k points that you could allocate before p3 is reached. And you have no way to choose parts till m.

Optimal solution: 1 -> p2 points allotted from A, the rest from B.

→ Ответить

Ra1nWarden

9 лет назад, # ^ |

I did maxflow and apparently the range of the data is not feasible. I think it sounds like some interval related problem. I am not sure how to use those continuous intervals.

→ Ответить

9 лет назад, # |

← Rev. 3 →

+66

I am the writer of this round. I'm very sorry for technical issues that caused the round to be unrated. I'm not sure what went wrong during the match. It seems that topcoder.com went down during the round.

Here are solutions.

div2 code: http://pastebin.com/tiX7gjQw

div1 code: http://pastebin.com/GqPkiviy

div2 easy: do what's stated in the statement
div2 med: Let's look at the absolute value of the difference between x and y coordinates. We need at least as many L/R characters to make the x coordinates coincide (similarly for U/D characters for y coordinates). This is also a sufficient condition.
div2 hard: This is a bitmask dp. Below just a summarized version of the code, so read that first. We go bit by bit from high to low. The bitmask represents which numbers are strictly less than max, and other numbers are currently equal to max. Also, once we fix the bit of the 0-th number in the list, all other numbers are determined. Take a look at the code for more details.
div1 easy: Binary search for the answer. After you can do greedy or max flow on compressed graph (greedy is much easier to code though). The greedy takes parts from an available shop with the smallest b[i].
div1 med: I thought this was a div1 easy when I first came up with it, but it is a bit tricky. You can do brute force. Here's a brief proof on why this works. Let's look at the max number in the range. Then, we have a recurrence T(n) = min(a,b) + T(a) + T(b), where a+b+1=n. By the "small-to-large" principle, T(n) is O(n log n), so the answer is always small. I'm also sorry that it's impossible solve this problem in some languages like C#.
div1 hard: Compute probability that a pair of coins contributes to the final answer using an O(N^3) dp. Then, add up vals[i]*vals[j]*pr[i][j] to get the final answer. When I came up with this problem, I was trying to think of a dp based on a range But, I discovered that approach didn't quite work, since after splitting, the two parts are not independent.

→ Ответить

Ra1nWarden

9 лет назад, # ^ |

+10

Can you explain the maxflow method for div1 easy? How do you build the compressed graph? I represented each shop and each item part as a node and it is too large to fit in.

→ Ответить

ikatanic

9 лет назад, # ^ |

Try grouping parts covered by same subset of shops.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

You can see rng_58's code for a nice implementation. The basic idea is that you can compress coordinates first. There are only at most 100 numbers in the input, which splits up the parts into 100 different intervals. So you only need to have a node for each interval rather than for each item part.

→ Ответить

ffao

9 лет назад, # ^ |

+34

d1-500 was so cute :) (And definitely not an easy!)

900 was a bit easier than usual, maybe it could have been a 600 in a more difficult round, but I'm fine with it as a 900 too. The admins tend to know their stuff when it comes to difficulty :P

→ Ответить

9 лет назад, # ^ |

Yes, I think it could have been a med. But, it seemed that it was very tempting to try and fail dp on a range, which was why we thought it was ok for a 900.

Basically, the idea for dp on a range is similar to this problem: https://community.topcoder.com/stat?c=problem_statement&pm=11781

→ Ответить

Zykd

9 лет назад, # ^ |

Hi can you explain about the div2 hard problem im kinda new i didnt understand the question can u please elaborate please? thank you :)

→ Ответить

klamathix

9 лет назад, # ^ |

Random opinion: I've never seen an n = 10.000.000 work with an O(n log n) solution, I scratched every idea that could go above linear while thinking about the Div1-Medium. I think in the end I came up with something that is O(n) time and O(sqrt(n)) memory, but I didn't have time to code it. If it's correct or there are other O(n) solutions, I think this problem should either have a smaller N or a bigger N and more points awarded.

→ Ответить

9 лет назад, # ^ |

+24

Random opinion 2: Given how input was generated, it was probably hard to construct evil testcases here :P.

→ Ответить

klamathix

9 лет назад, # ^ |

+10

^ This too. I've actually wondered about this for every problem that had generated inputs in TC. Maybe the TC staff can shed some light on how they build strong test-cases this way?

→ Ответить

9 лет назад, # ^ |

Another issue about generating inputs — it is really uncofmortable to construct countertests during hacking phase if input needs to be given as few seeds to generator :(.

→ Ответить

kingofnumbers

9 лет назад, # ^ |

actually I used stack idea which fail if input was decreasing array, I thought the input is random but then I was hacked with the following test

n=10,000,000

x0=(2^50-1)

a=0

b=(2^50-1)

→ Ответить

flashmt

9 лет назад, # ^ |

← Rev. 2 →

+13

I also implemented the stack idea and noticed that test case (it is actually in the sample ones). So I did a "dirty" hack by reversing the initial array whenever the stack size exceeds 30000 (doing some manual testing on Arena yields this limit). I'm not sure if there exists a test case that causes my solution to fail but I feel that it's quite difficult to generate such one randomly. It passed in the end.

→ Ответить

9 лет назад, # ^ |

For me med was by far the hardest problem in that problemset :pp. How do you implement this bruteforce?

→ Ответить

9 лет назад, # ^ |

The only thing we need to know how to do is go backwards and forward in the sequence. For each number, walk left and right until you hit the end of the array or a number >= to yourself. You can see my code for details.

→ Ответить

9 лет назад, # ^ |

The trickiest thing in the whole solution is that we can go left. Have you ever seen input generated with some similar formulas that allowed to go left and when that was useful to solution? I have seen such thing for the first time, usually we are not supposed to delve into those formulas. And you didn't even mention it in your solution, so I thought that maybe you have some other approach on your mind :P. What is funny is that it came through my mind that maybe we are able to construct an inverse, but I discarded that idea, because I thought it is not working because of that modulo (1 << 50) — 1 xD.

Btw nice problem and if I'm not mistaken it is possible to construct solution without possibility of going left that works in O(n) time and O(sqrt(n)) memory, but it was too complicated for me to complete coding it in time. We divide sequence to parts og length $\text{[math]}$ , keep maximums within them, use typical algo for intervals between them and then determine radiis of those maximums (for every maximum we need $\text{[math]}$ time, but it is not easy to code it given time I was given).

→ Ответить

acmabhi

9 лет назад, # ^ |

← Rev. 2 →

can you add some explanation/references on how to compute the inverse in order to go left ?

→ Ответить

Gassa

9 лет назад, # ^ |

$\text{[math]}$

Here, x is the previous value and y is the next one.

The equivalence is true modulo any integer.

→ Ответить

ffao

9 лет назад, # ^ |

← Rev. 2 →

For each number, move left until you find a bigger number, move right until you find a bigger number, add radius to answer.

Edit: and I agree that med was the hardest in the problemset :p

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

+13

Keep leftmost and rightmost value of your current range; finding next element to the right is trivial (simply use formula from problem statement), and deriving previous element is also not hard:

long long get_prev(long long x)
{
	x-=B;
	if (x<0)
	x+=(one<<50);
	x^=A;
	return x;
}

→ Ответить

SandorGarcia

9 лет назад, # ^ |

← Rev. 2 →

For div1 med I tried to implement it the somewhat classic way to solve it using a single stack which stores a decreasing sequence, this is linear in time and I expect it to run in O(sqrt(n)) memory as this is the expected length of the longest increasing/decreasing subsequence in a sequence of N random numbers, could you confirm if this kind of solution may get accepted?

Also, does the generated sequence behaves like a 'random' sequence?

EDIT: I see now you could create a fully increasing sequence with this generator (which is irrelevant to my solution, can you also create a fully decreasing one?

→ Ответить

9 лет назад, # ^ |

+18

It's not too hard to generate cases where the numbers are all increasing or decreasing, which would break naive stack-based solutions. For example, a=0, b=1, x0=0.

→ Ответить

SandorGarcia

9 лет назад, # ^ |

Ok, thanks a lot for your reply, and for yet another great problemset.

→ Ответить

k0st1a

9 лет назад, # ^ |

Could you provide more details on part about "small-to-large" principle ? Thanks.

→ Ответить

http://codeforces.me/contest/600/problem/E http://codeforces.me/problemset/problem/601/D

9 лет назад, # ^ |

Off the top of my head, here are some problems that use this trick:

→ Ответить

k0st1a

9 лет назад, # ^ |

Though it is not clear why this principle is the case in div1 medium problem.

→ Ответить

ikatanic

9 лет назад, # ^ |

← Rev. 2 →

+10

So comment with 2nd sample test 'Don't forget, the answer is modulo 1,000,000,007.' was a trap :).

→ Ответить

MathCrusader

9 лет назад, # ^ |

← Rev. 3 →

For the 500-point problem, given the input generators, is it possible to construct the hardest test case for the correct answer? If I'm not mistaken, the worst case for this complexity is when the maximum entry is close to the middle (but not quite at the middle). However, let's just say that we want it exactly in the middle every time. Are there seeds that could generate something like the following for n ~ 10,000,000?

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

Obviously, you cannot get this exact sequence (since, for example, in the third sequence 1->2 and 1->3 and 1->4, which is impossible), but can you get a sequence where the max is in the middle every time?

→ Ответить

saketh

9 лет назад, # ^ |

+30

Another way to prove it's NlogN for D1 Med:

Let's say that element i is covered by element j if the radius for element j extends over element i. If we take the sum over all elements i of the number of elements j covering i, that's on the same order as the sum of all the radii, which in turn determines how much work is done by the brute force algorithm.

Suppose a particular element i is covered from its right by elements j_1, j_2, ..., with i < j_1 < j_2 < ...

Each j_i needs to be at least twice as far away from i as the j_(i-1) before it; otherwise, j_(i-1)'s radius wouldn't extend far enough to cover i. So, each i can only have log(N) elements j covering it from the right. The same logic applies for the left.

→ Ответить

Fcdkbear

9 лет назад, # ^ |

← Rev. 2 →

May you please a little bit more on how you get this equation:

T(n) = min(a,b) + T(a) + T(b)

I can't see why this is correct

UPD Sorry, I get that, it's so easy. I am probably too tired after implementing O(n) solution :)

→ Ответить

Guliash

9 лет назад, # ^ |

My solution for div2 hard passed all of the system tests, but I think it isn't correct.

http://pastebin.com/x3yJgTcc

→ Ответить

PrinceOfPersia

9 лет назад, # |

← Rev. 2 →

After centuries my wrong approach (at least what I thought of my solution for div.1 medium) passes the system test and contest becomes unrated.

→ Ответить