That was a mistake.

Right,the 2014 Code Jam World Finals will coming!On August 15th, the reigning champion, Ivan Miatselski (mystic), will make his return to the Finals to face off against the top 25 Code Jammers in Los Angeles.

click here for more information

also for dp!!!

Why would you hope for that

I also hope you'll not cheat again! Have you seen your other pupil and newbie accounts? Competing for RATING and CHEATING wont make you learn anything! I'm wondering how you got rank 20 div2 as a new account! :)

mobinTE

Mobin_Teymoori

Mobin_Teymoori

Mobint3ymoori

mr.mobin

mobinTEY

mobin2000

mobin_t

I think he did not find a new combination for his name and just created this new account Mobin-Teymoori! :)

why? for cheating?

We don't understand what your meaning,Please use English. ：)

Please don't bomb us

kind of ironic that i missed this round due to attending a friend's marriage. :)

Pashmak = matrix :D

I could never understand ethnic of national pride. Because to me pride should be reserved for
something you achieve or attain on your own, not something that happens by accident of birth.
Being Irish isn't a skill, it's a fuckin' genetic accident. You wouldn't say "I'm proud to be 5'1 1. I'm proud
to have a predisposition for colon cancer." So why the fuck would you be proud to be Irish, or proud to be Italian, or American or anything?
(c) George Carlin

That could also mean short but extremely hard solutions :D

Added in post.

see his rating in the graph 1884 :D

i saw another example of this few days ago ... may be they want to change master rating in 1850-2050 :D

Take a look at his contest list. It shows that he participated in both online and onsite version of MemSQL Start[c]UP 2.0:)

here is a screenshot of his Contests page. i think this is definitely an issue.

Soooooooooo many contestants that out-of-competition participants have to use 4-digit room number :p

Maybe it is a record high register number for a single division contest :p

Problems are too easy. I will go to bed now.

Congratulations:)

It is div2 contest, it should be very easy. Maybe not so much as today, but generally it should:) And i don't understand authors who give for div2 rounds problems like 424E - Colored Jenga — it is not a div2 problem at all.

Room assigment is done this way to decrease your impact on div2 standings — i guess there will be almost nothing to hack for div2 users, if you'll add 2-3 red coders to div2 room.

No! I believe that it was a really good pretest that is also open for hackers!

there are K^D configuarations for any students becaue can choose any of the K busses on a given day and there are D days.

so if N > K^D , one these configs will repeat.return -1 if this is true.

Else think of how 4 digit binary no.s are arranged. - 0 0 0 0 - 0 0 0 1 - 0 0 1 0 - 0 0 1 1 - 0 1 0 0 - 0 1 0 1 - 0 1 1 0 - 0 1 1 1 - 1 0 0 0 - 1 0 0 1 - 1 0 1 0 - 1 0 1 1 - 1 1 0 0 - 1 1 0 1 - 1 1 1 0 - 1 1 1 1

• Digit at place 0 have peiod of 1
• Digit at place 1 have peiod of 2
• Digit at place 2 have peiod of 4
• Digit at place 3 have peiod of 8

Note that thse places are analogous to days in our question and value of these place will be between 1 to K instead of 0 to 1

Hope this helps.

In short, before the first day you have the group of n students, and every day you break every group of g>=2 students in min(g,k) new groups. If g <= k, then each student gets its own bus, otherwise the group is split into k new groups of about (g/k) students.

Okay, here's a full proof and stuffs. Shorter solutions are present above.

Claim: If n > k^d, then there's no solution.

Proof: Induct on d. For d = 1, if n > k¹ = k, then by Pigeonhole Principle, at least two students go to the same bus and they become good friends. Now suppose our claim is proven for d = i. To prove this for d = i + 1, we see that if we have n > k^i + 1 students, by Pigeonhole Principle again kⁱ + 1 students will go to the same bus on the first day, and we can invoke our induction hypothesis on these students for the remaining i days. Thus if n > k^d, there's no solution.

Claim: If n ≤ k^d, then there is a solution.

Observe all d-digit numbers in base k, including leading zeroes. (This means the numbers 000, 001, 010, 011, 100, 101, 110, 111 for k = 2, d = 3, and 00, 01, 02, 10, 11, 12, 20, 21, 22 for k = 3, d = 2, for example.) Since there are k^d such numbers, we can assign each student to some number so no two students share a number. Now, on the i-th day, all students whose i-th digit (from either end, but let's suppose from the right) is j goes to bus j + 1. For example, with k = 2, d = 3, we have the students 000, 010, 100, 110 in bus 1 on day 1, and the students 010, 011, 110, 111 in bus 2 on day 2. This gives the required schedule.

Now our task is to implement the above.

Checking the first claim is simple; however, since k^d can potentially go to (10⁹)¹⁰⁰⁰ = 10⁹⁰⁰⁰ (over 9000...not), we need to handle some overflows. The easiest method is to declare a temporary variable tmp that is a 64-bit integer, initializing it to 1, then loop d times, multiplying k to tmp and comparing it with n. If after all d iterations we still have n > tmp, then there's no solution. Otherwise, at the first moment n ≤ tmp is true, the value of tmp is at most kn, since before this tmp < n is true and we multiply tmp by k. Since n ≤ 10³, k ≤ 10⁹, tmp ≤ kn ≤ 10¹² fits in our 64-bit integer.

Now, after we check this, we can start constructing our numbers. We can check the i-th digit from the right of a number j in base k in a simple way: (j / k^i - 1) % k, with  /  being truncated division and % being modulo. This is true since dividing by k^i - 1 means we're removing the last i - 1 digits, which makes the unit digit to be the i-th digit originally, and "modulo-ing" by k means we throw away all digits except the unit digit, so now we have the i-th digit alone.

If we assign the numbers to the students consecutively starting from 00... 0 = 0, it becomes a simple iteration to find the bus numbers. For day i, iterate over j = 0, 1, ..., n - 1; find the i-th digit of j in base k, add by one (since the possible digits are from 0 to k - 1, but the buses are from 1 to k), and that's the bus number of the student.

Here's my solution in C++, which should be rather straightforward.

one can also use DFS to solve this problem.

see my submission below for more information. The basic idea is to go through all permutations using for loops, and stopping when we have enough of them.

http://mirror.codeforces.com/contest/459/submission/7470821

Something like this.

first calculate l[i] = f(1,i,ai), r[i]=(i,n,ai); then you just need a BIT(binary indexed tree) to find the answer :)

I don't think "saying good things about Mr. mirzayanov" increases your contribution

although Codeforces is the fastest online judge

Hahaha same here. I was fooled. But the big problem is that I spent on it lot of time to make a silly mistake at the end.

I had the same problem.

Character #13 is carriage return. Looks like you put a new line while you should have put a space. Which problem are you trying to hack?

...actually, it's also possible that you're using Windows-style newline \r\n (or Mac?-style \r) while the validator expects Unix-style \n. Yeah, which problem are you trying to hack?

whats that?

problem B,if we use "int",it can be Multiplication overflow. TAT

I tried to hack a guy with that case in the last few seconds. Guess what I got ? An apache error :)

I hacked 6 solution by 2 3 1 4 :D

right, but even more congratulations to vanhanh.pham! :)

Could anyone tell me why it had happened?

This code submitted with another account too. So both of 'em got skipped.

My java solution runs test 9 in 1.5 seconds... The time constraints seem a little harsh, especially when we are asked to print out as many as 1,000,000 ints on 1000 lines during that time.

I believe that $I64d and %lld mean the same thing now on CF, whereas %ld and %Ld are both wrong and there have never been any replacement warnings about them.

%ld is for long, but not long long

Yo can have, for example 10⁵ 3s, and 10⁵ 4s, so 10⁵ * 10⁵ = 10¹⁰, so you needed long long

The result (number of pairs) can be up to N*(N-1)/2

The counter of flowers don't need to be long long, if you remember to cast the multiplication it_min->second * it_max->second to long long first. If both variables are ints, when you multiply the two, the result will still be an int and it might cause an overflow.

After all, you can't do this to print 10¹⁸ due to overflow: int a = 1000000000; cout << a*a;. The same reason with why you can't do cout << it_min->second * it_max->second; without risking overflow.