Recent actions

That's perfect division, first instance I got to know splitting so perfectly.

very good contest

I wonder,how fair is it to a guy , who attain 7'th place (world wide) in Codeforces . And gets 195 minus rating ..

It even hearts me :'v

And I also sometimes wonder how it feels to be Tourist . :)

I still don't understand Div2 E till now. Anyone care to explain?

1 second isn't an unusually small TL for me.

Who are the local winners?

Your calculations are correct but I meant something else. You may assume that reading is constant but sometimes there are many ways to do something simple — so simple that participants don't care about it. For example, pushing numbers from the input to a vector (it's slower that writing to an already allocated array/vector) or using set instead of vector & sort & unique to count different values. So I meant a non-constant X that matters more for small TL. Also, I would expect bigger language differences for times close to 0 — I wouldn't set TL 0.1 if the intended solution is 0.03.

Also, I've consciously chosen TL to fail solutions like Radewoosh's one.

Ok, it explains an unusually small TL. I don't think choosing a good base for calculations was important in this problem but I won't argue about that (your decision was fine IMO).

Don't get your point. Suppose that reading takes time X. So we are probably interested in ratio (because X is independent of solution). . The lesser TL is, the greater will be.

Also, I've consciously chosen TL to fail solutions like Radewoosh's one.

Good point :)

But rounds are made not only for tourist. Also I've expected much more AC for problem E. I'm sorry that E appeared to be more difficult than I've expected.

TL of 1s is fine if the intended solution is 350s but bigger difference would be better (why not?), unless there exists a solution in slightly worse complexity that you wanted to fail. Also, I would say that the ratio TL/intendedSolutionTime should be bigger in problems with small time limit, because simple things take more percent of time there (e.g. reading or iterating over 1e6 values). Though, now I think that I don't consider such things/aspects myself when I'm choosing TL :D

That's really funny

"(finalists should be stronger, right?)" — do you expect tourist in round called "something's final" to be stronger than tourist in a usual round ; p?

You went to my account? o.O

..... I came up with this idea and then forbade it.... that's too stupid

EdwardSnowden, is this true?

Codeforces exceeded time limit when going through all the zeroes in hardcoded constants in your code.

I hadn't participated in elimination round so it was impossible to participate in final round. (Because I hadn't placed in top 200)

I know I could have got $1000 if I participated in both contests. It also makes me sad but t-shirts are more (because 50 participants won them)

You would have got 1000 dollars if you participated in the right contest and your problem is the T-shirt? :)) I think CF should implement a system such that you can't register at the wrong contest. And now, just for the record, was it possible for unqualified contestants to take part in the official round?

I want t-shirts but I forgot participating in elimination round lol

Div1 version: Few failed systest, few hack attempt (and no successful hack), and few active participant (391 active of 656 registered) :/ Fortunately the problem is not bad :)

E: Surely, E is pretty OK, this problem is by far not straightforward (however it is easier if you are not a retard like me and read that sum of b's is <=3e5). And dividing bignum by int is indeed lot easier than typical division, I thought that much more involved operations will be needed which led me to disliking this problem prematurely. Probably that problem without bigints wouldn't make much sense, so their existence here is very well justified.

F: OK, if you say it took you 2 hours to tackle the case 1 - 10n then I guess it is not easy, so it significantly increases ratio I mentioned :p. However I wouldn't call parsing "combining some ideas in one problem", that's very nice expression for that ;p.

I get your idea that "all this other stuff like parsing and other operations are kinda boring" and I partially agree. But it was hardest problem in a not usual round (finalists should be stronger, right?). So I decide to add some coding part (but you should agree that parsing is relatively easy in this problem).

Maybe it is just unusual to see "parsing" problem in a short individual competition.

And Div 2 C

They are looking for cheaters before computing rating. There are definitely no cheaters on the onsite event, so they have immediately calculated rating for them.

F: Then maybe the part about the intervals would make a good problem D or E.

Still waiting for rate changes

Your explanation is great, but an example would be even more awesome :)

I still have difficulty visualizing how all this permutation stuff works.

Let's give names to 5 skewers: a, b, c, d, e. Rotated skewer a can be named as A. How will this original configuration change with time?

E: Division bigint by int isn't very hard, is it? Also I think that there is something else in this problem (not only bignums) and this something is what the problem about.

F: Well, I added this parsing part to 1) combine some ideas in one problem 2) make it harder to code. But yes, the only hard part is those intervals and yes, it still can somehow be done. Maybe not brilliant but some ideas are needed.

The editorial is here.

Codeforces rating system is kinda odd. If I had participated in div 1 round I would got a good increment (like +50), but with final round I get only +4. If there is no mistakes then the only conclusion I can make is not to participate in small-amount-of-participants rounds in future.

Wow. I was thinking about 2 hours on how to avoid O(n2) for case 1 - 10n. You are very smart person.

And when I was writing then solution about a half of the time I was sitting with pen and paper.

didn't see*

Congratulations to winners!

The onsite participants only standings page is available by the link http://codeforces.com/contest/756/standings?list=2c7ac9b338b4906db6d101641a3b06b4.

Sorry, I do not understand your previous comment context correctly.

Once or twice. Look at times of AC's, they're kinda close to limit. But I know, that it's fair, one limit for everyone and things like this...

i think there is a problem with the site right now.i see the updated rating of tourist when i open a profile and the previous rating when i open the contest section on profile.

Rating of Final Round participants is updated, not other two.

Created or updated the text

Exactly like the problems, the interesting ones are harder to get.

Only few people have their ratings updated till now like tourist. Does the process of updating take too much time??

Never would have thought there is such a big difference in speed between int and long long.

Why the hell codeforces hides comments with too many negative votes? They are more interesting for me :D

I solved F without using any bignums.

Same shit

Imagine the skewer that starts at position 1. If pi makes one big cycle, then after n steps, this skewer will be back where it started. At this point, we would like the skewer to go through all these positions a second time in the opposite orientation. This only happens if it ends up back in position 1 after being flipped an odd number of times.

This happend with me too, wtf

Thank you, C++, for being so tolerant to typos...

  • if (sums[left >= time]) -- passed pretests(!), WA 21
  • if (sums[left] >= time) -- AC

Lol, I referred to problem E when telling about bignums xD. Should have mentioned it :D.

F is surely not about bignums, but I don't like F because it has very low ratio of "difficulty of getting idea right : difficulty of coding it" and that is more or less what I use to sort problems by how fun they are. We need to parse everything (hooray) and what is left to do is to make some rules producing (length of expression mod P-1, value mod P) for every expression. Only rule which I didn't figure out was those intervals, but I didn't think about it for longer than 15 seconds, but I guess it still can somehow be done without some brilliant ideas.

Btw, I do not predict your comment to get downvotes ;p.

If only the problem could say these words, I would have been better rated today :P

The problem is that arriving at the solution is straightforward and the difficulty lies entirely in coding it. I personally don't find that very fun.

If you have an even number of 1's, by the time a skewer gets back to its original position, it will be in the same orientation as it was, however if there are an odd number of 1's, it will get to it's starting position in the reverse orientation.

Idk how good that explanation was, tell me if you need me to come up with an example.

I understood the cycle part during contest... however didn't get the part about even number of 1's ... please explain why even number of 1 won't work

My solution works about 350 ms. Have you ever heard about numbers in base 109?

Well formally this is DP. But, come on, sum[i - 1] - sum[j] would be real DP :)

When will be editorial?

(Want to get my -100 comment)

I'm the author. What is the problem? Swistakk is also welcomed.

bignums is a lot of fun

Really? It is a problem about bignums?

Yeah, I thought this was a little misleading.

I understood the question as:

  • You only pay for a bus ticket when you board a bus, and the length of the trips don't matter
  • The ti values are the times when you board a bus
  • The 90 minute ticket lets you pay once and board an unlimited number of buses for 90 minutes

I feel you lmao, reading is hard sometimes.

Well I got that we can transform the problem to counting different subsequences, but I do not understand why do we need to find this number for every length. Can you explain in a bit more details.

The analogy of trip was badly written I believe. The trips are instantaneous are point in time so to say. So if trips happen at 1 30 50 minutes. its better to take a 90 minute ticket/pass than 3 individual tickets.

so I was doing.. min( dp(i-1)+20, dp(last trip 90min ago) + 50, dp(last trip 1440 ago + 120) ) etc.. Finished coding 5 mins after contest end :(

That is definitely DP, and instead of binary search, you just do linear search, so wouldn't work for slightly tighter constraints :)

Got it passed in 1.5 seconds.

The code running O(n2) times was the following (3.5 seconds locally on a random test):

code 1

First, branching gets in the way of instruction-level parallelism. So, get rid of branching by switching f to int64 (it was int32) and taking the remainder in an O(n2) outer loop (down to 3.05 seconds):

code 2

This was still not enough: my compiler is dmd which sometimes produces suboptimal code. Locally, this is already fast with gdc or ldc, but they are not present on Codeforces.

So, the next thing was to streamline accesses to the transition table (1.55 seconds):

code 3

This looked fast already. But I added manual loop unrolling, just to be sure it happens (1.3 seconds):

code 4

Overall, the optimization effort took 5.5 minutes between the two submissions (one, two). Actually solving the problem took way longer for me.

This won't. There would be a combined contest for div1 and div2 if that was the case.

Holy Shit I didn't saw that fucking permutation thing :(

I agree Div2 E was really hard to understand

discussed here! already

You can do the dp in O(N2) by using a prefix sum table.

Waiting for rating update...

try to use BinarySearch :)

Does that happen immidietly ?

Div-2 D is written so badly . I am still not able to understand it. Can any one help?

there is already a discussion here.

binary search the answer. allocate the answer to k. allocate k-1 to adjacent guys etc etc.. if not able allocate, search for lesser answer.

I did, with no optimizations at all. It passes in 1840ms.

thanks both of you, I understood the question now. I was trying greedy so couldn't get sample case 2 correct.

Your pi values don't include 5, so this isn't a valid input.

The case would be invalid since array p needs to be a permutation.

So I was trying to access the problem for practice and suddenly this happened. Some kind of bug or hidden feature? o.O

Will these problems be added to archive, and when?

Can anyone suggest how to solve Div2 B?

Maybe I'm misunderstanding your code, but this looks like DP to me — you're using the previous outputs (his[j]) to calculate the latest output (his[i]). Nice that there's no need for a binary search, though.

How does that works for this test :

7

2 3 4 7 6 1 6

0 1 0 0 0 0 0

waiting for problems to added in practise.

Noo, mine gets wrong answer too. XD And I don't know why.

Is there a time limit after which you can see other's solutions ?

Did almost everyone else do ON2)? I just wouldn't imagine this passing along with modulo operations. I did waste some time figuring out how to reduce to O(N2). I did like D as a problem though.

I did, but I solved that in 13 mins and then have been optimizing it for 20 mins. I needed to change a bit flow of my algorithm to gain better use of cache and erase my beloved macro "#define int long long" and it passed in 748 ms. Maybe that cache thing was not necessary because deleting that macro sped up my program from 3,5s to 750ms on CF >_>...

Another way is to do exactly what statement says.

	vi a(n);

	for (int & t : a) cin >> t;
	vi his(n, 0);

	his[0] = 20;
	cout << 20 << endl;

	for (int i = 1; i < n; ++i) {
		his[i] = 20;

		int paid1 = 0;
		for (int j = i - 1; j >= 0 && a[j] + 90 - 1 >= a[i]; --j) paid1 += his[j];

		if (paid1 + his[i] > 50) {
			his[i] = max(50 - paid1, 0);
		}

		int paid2 = 0;
		for (int j = i - 1; j >= 0 && a[j] + 1440 - 1 >= a[i]; --j) paid2 += his[j];

		if (paid2 + his[i] > 120) {
			his[i] = max(120 - paid2, 0);
		}

		cout << his[i] << endl;
	}

No DP, no binary search. 144kk operations worst case = 500 ms.

Thank you :)

I did, 1900ms.

edit: And yeah, I also spent 30 minutes optimizing it..

What about this one ?

Sure!

First of all, imagine that the time ranges on the tickets work backwards (ie: buying a 90 minute ticket at time 100 covers all trips from times 11 to 100). Then, for trip ti, we would like to calculate the minimum cost ci. There are three options:

  1. Buy a ticket for one trip. This costs ci - 1 + 20.
  2. Buy a ticket for 90 minutes. Use a binary search to find the earliest trip tm that would be covered by this ticket. This costs cm + 50.
  3. Buy a ticket for 1440 minutes. Again, find the earliest trip that happened in the past 1440 minutes. This costs cm + 120.

Total time is because of the binary search at each step.

EDIT: I refer to problem E here :D.

Not sure whether this comment was sarcastic or not, but if you really want to than I also think that bignums is a lot of fun, especially when TL is very strict (I didn't solve that problem, but heard that from friends), so that you can't use Python.

Now it will send you into space :)

Roughly O(sqrt(M))

Your check function logic is not right. Here is link to my accepted code : here

Upsolving!!!

Nice time limit in E.

do you mind sharing your approach for D? (div 2)

Strangely, this gave TLE with C++11 and passed in 1263ms with C++14. Never knew C++14 had so much better optimizations.

C++11

C++14