Recent actions

My solution is quite strang and not elegant. I recommand you to read this guide:http://codeforces.com/blog/entry/51567?#comment-354676. I think this guide is more easy to understand and to write the code.

Created or updated the text

got the case where it is failing input :- abcfefg output :- abceffg

Please also discuss the approach for problem E.

What special about test case 17? could not pass case 17 after multiple tries. my solutions:- 26491308 , 26469800

Can you provide a link or even better explain it yourself the details of the optimization ?

What is the logic behind problem E?

Just a moment after I posted, I realized sorting was enough to assign contiguous mice to a hole.

As for the hole capacities, yep, I meant that (and I missed it's as simple as that!)

Thank you :)

+4

The group of mice assigned to some hole is always contiguous, i.e. there will never exist a situation that a,b,c are three consecutive mice (in increasing order of coordinate) but a and c are assigned to hole-1 but b is assigned to hole-2.
And what do you mean by how I deal with hole capacities? If I have to assign some suffix of the first x mice to hole j, then I can assign atmost the last capacity[j] mice to hole j.

How do you deal with hole capacities and the fact that contiguous mice are not necessary assigned to the same hole?

+3

Is it normal that problems B and C now have duplicate tests? For example, there is the test #48 "1 // 1" that repeats further as #50, 51, and 54. Problem C also has such tests, e. g. "a" by #40, 41, 42, 45, 47, and 51.

+1

I'm unable to submit a solution for the contest. It shows that System Testing is going on, while it was over hours ago.

On clicking the submit button, it shows the message "Practice is allowed only for finished and unfrozen contests".

nice warm up round man....

thanks for all these... i luv this website <3

My java solutions with proper documentation

Hope it helps.

+16

You can solve it using dynamic programming. Let DP[j][i] denote the minimum cost to assign the first i mice to the first j holes. For each state, iterate over the leftmost mouse you will assign the jth hole to. This takes O(m*n*n) time.

But notice that for a fixed j, the optimal left-point is non-decreasing for non-decreasing i, i.e. optima[j][i] <= optima[j][i+1]. So you can speed up the DP using divide-and-conquer optimisation.

Code

Nice contest and nice problems

http://codeforces.com/contest/797/submission/26402069 why this submission always wrong at 25th test case???who can help me ??

+31

I don't know the time complex of the std. But the time limit makes me think that the std have the time complex of O(n2).

My solution's time complex is , and it costs 858ms.

First it's easy to come up with the DP of O(n3). Then let's look at the programme carefully, and we can find out that it's very similar to Knapsack problem. And this classic problem have a classic way(divide each original item into items) to optimize it to

We can use the same way to opimize the original problem. Then we solve the origine problem in

+6

I noticed that if I submit a solution after a previous solution got hacked, then my new solution runs only the original system tests, and not the hack(s) that caught my previous solution(s). That's too bad, because that way I can be "Accepted" again without fixing my problem (in fact, I have no idea whether I fixed my problem unless the hacker is kind enough to keep trying the hack on my new solution).

UPDATE: Appears to be fixed now.

I tried reloading many times, and also clearing my browser cache/cookies before trying again. This happens after I submit the input for hacking by the way.

+3

There were two mistakes.

One was a syntax error at line 92. Second mistake was I was remembering the nodes which are visited instead of values.

AC solution: 26398128

Its quite confusing . He has considered even more cases . Can you read my code once and tell me , which case I might be missing ??

+1

Your code fails for this testcase : abcbabbcc

Your code outputs aabbccbcb whereas the correct answer is aabbbcbcc

26389948

^This implementation is similar to yours. You can refer to this one.

+17

That's how you try to cheat even in an unrated round!!

ScreenShot

Can anybody tell why my code is failing in one of the tests ?? https://pastebin.com/GC45xUAa

Reload

+6

It's my first time to try hacking here on CF. Not sure how it works. It seems to be just stuck loading forever. Is this supposed to happen?

No successful submissions on E in Python 2 or Python 3. I tried to rewrite one Java solution to Python, it TLE-ed on test 7. Isn't the time limit of problem E too tight for Python?

+3

Can someone tell me where I am wrong in D?

I made a fucntion checkValid which takes node,l,r as arguments. And marks true if value[node] lies between l and r both inclusive. Then, I call checkValid with left[node], and with the intersection of (-inf,value[node]-1) and (l,r). The same process is repeated symmetrically for right node.

I am getting WA at Test Case 20. And my answer differs by 1 from expected answer.

Submission Link: 26396243

Can someone please help me in finding mistake in my Solution for problem C.

+40

Please discuss the approach for problem F.

Ah, I see. Thanks! I completely missed the fact that when p changes the array element chages as well.

In the first operation p = 1 p = p + a[p] + k p = 1 + 3 + 1 p = 5 In the second operation p = 5 p = 5 + 7 + 1 p = 13 p > 10

Can someone explain to me why in the second test for E the 8th number is 2?

10
3 5 4 3 7 10 6 7 2 3
10
4 5
2 10
4 6
9 9
9 2
5 1
6 4
1 1 <-
5 6
6 4

p = 1, a[1] = 3, k = 1, n = 10;
Initially p = 1. After first operation p = 1 + 3 + 1 = 5. After second operation p = 5 + 3 + 1 = 9 < 10. What am I missing?

Thank you man!

How did you manage to solve A and B if you consider yourself as dumb? :)

I am so dumb :( ....I really do not know anything :(

Check the edit up there /. You can't use 1000 not because of time but because of overflow on short int operations.

You can solve it greedily.

for (char c = 'a'; c <= 'z'; c++)
{
  // Try to place current character 'c' in the target string.
}

I still get TLE even with this :/ 26394497

How to solve C ????

Never thought I could make more points than some reds or oranges. Strange contest =)

The precomputation is probably too slow. Change 10^3 to sqrt(10^5) and it will probably pass.

Edit: you didn't calculate the dp properly http://codeforces.com/contest/797/submission/26394436

Did someone pass TL42 with mincost maxflow on F?

sqrt decomposition

Just precalculate answers p, k for p <= n && k <= B, and use naive algo when k > B. If B = sqrt(n) complexity is O(N * sqrt(N))

Can anyone tell me why im getting TLE on E. My idea is precompute for every k below 1000 in O(N) each and just simulate all k bigger than 1000 (worst case scenario is 100 operations if im correct) 26393091

+8

very interesting problem set. I hope to see more problem set like this! :D

+16

How to solve F?

+30

Why not all the contests have clear problem statements like this one. Thank you for this interesting contest.

+3

OOPS, I missed it, I'm very sorry .. thanks KieranHorgan and yinanzhu

+28

Really?

+10

Exactly. When the educational round starts (16:35) 11 hours after the Code Jam round ends (05:30).

-42

is it rated?

+2

Google code Jam round 1A

Educational Codeforces Round 19

You must messed up the time zone of either contest. Hope you find out before it's too late.

+4

Actually It doesn't.

so, go for only one, which you like more!

-29

It overlaps with GoogleCodeJam round 1A !

UPD: It doesn't overlap .. thanks for yinanzhu and KieranHorgan

ohh so that was the problem. Thank you ^^ I will keep that in mind from now on

It should be 1LL << (levels - 1) — shift amount doesn't promote the type of expression to long long.

If ak%i == 0 then we don't know if (pki,pki+1) can combinate all box, If it can make it, they will be the maximum size. If not, then(pki-1,pki) also can combinate this box ak, so I think we should try this case.

Why we are treating the case when a[0]%k==0 differently?

Why on earth would he do that ?

Sorry, my mistake. I've just found a bug in my source code. CodeForces forever !

Created or updated the text

Actually, the solution worked.

I had error in implementation. The algorithm is passing all the test cases.

My AC Solution: Link

+4

Java has a method called Arrays.sort(); that uses a quick sort method to sort an array. Quick sort's average run time is O(nlogn), but it's worst case scenario sort is O(n^2). People used a worst case scenario input/generator to hack many java solutions.

P.S. To fix this just use Integer instead of int for your array since to sort objects, java uses a merge sort instead, which runs in time.

+9

In problem A, Anti-quicksort hack cases work.

+9

for problem A, there are more than 150 hacks in java.what's wrong with java ?

I think the method you decide if a node is a left child or right child is wrong, because everything else that you said is like mine solution. Instead of checking if current_node is a right child or left child by some formula, I simply keep a stack on the moves I have made. You can look at my solution if you want 25872554

And here is my poor code... I'm sorry about I forgot it.25873907

  1. Let the number of ball in box noted a1 a2 ... an;
  2. First you will find the minimum ai in this array (marked as ak).
  3. Then, let's enumerate all size as (ak/1, ak/2, ... ak/ak), let pki = ak/i, if (ak%i == 0) we will try that (pki, pki+1) and (pki, pki-1), otherwise, we wil try (pki, pki+1);
  4. If we discover a pair (pkj, pkj+1) can combinate all box(a1,a2,...an), then we find the maximum size of set is (pkj, pkj+1);
  5. Output the sum of Pi = ai/(pkj+1) (PS: if (ai%(pkj+1)) != 0 then Pi = Pi + 1) for answer.
+1

Yup, the problem turned out to be bitwise operations, i simply changed the line root=1<<(levels-1); to root=(n+1)/2 and it got accepted.

thanks, binary search seems not appropriate to this problem. I'm turning to learn with tutorial....

Well, when I switch to c++14 from c++11 I got more YES, but still wa on test 3. I feel quite confused.

+1

Maybe the stl is different.

+14

Someone pls help me with this. this program runs pretty well on my own computer. But it does not work in the test. It got wa on test 3, where the output should be all YES (and it is on my computer)

25863026

the problem C's datas are too strong,,,I had WA many times.

-8
+1

I also got a WA on test 10, then I removed all the pow() operations and computed the values on my own, and this got me an AC. I think it's due to the inaccuracy of pow(), that you are getting a WA.

You can, but probably you will have many bugs in code (like me :P). So, you can try :)

When are the editorials scheduled?

isn't it able to solve with normal logic?

What is wrong with this approach of D ?

IF str[i] = 'R' do curr_node = curr_node + 2^(tree_height-curr_height -1 ).

IF str[i] = 'L' do curr_node = curr_node - 2^(tree_height-curr_height -1 ).

IF str[i] = 'U' , I divide curr_node by 2 until it becomes an odd number. If obtained_number+1 is divisible by 4, this implies curr_node is right child of it's parent. currr_node = curr_node - 2^(tree_height-curr_height).

Else currr_node = curr_node + 2^(tree_height-curr_height).

I am maintaing curr_height accordingly at each step and also checking for the bounds.

Getting WA at test case 6.

It can be solved by dynamic programming.

It can be solved with DP

+3

Find K = sum%3. If its 0, you are done.
Otherwise, you have to remove at max 2 elements to make it a multiple of 3.
So there are few cases only that you have. I maintained a vector of pair for both cases, when K is 0 and when its 1. Find for each case the resultant string and take the one with minimum deletions. (Also for more optimization you won't remove digits like 3,6,9 anyway.) Here is the code.

I made a function that receives a number x and returns info = {value, level, left/right, difference with parent} about it in log(n).
You can observe that for node x, value of left child is x-dif, value of right child is x+dif. dif reduces by 2 on each level.
Using this, it becomes easy to process up, left and right queries.
Here is AC code.
Here is same code with comments.

How to solve C ? Is this a greedy problem ?

How do I solve C?

Hi,

Thanks to the organizers for these problems.

Just to be sure : I get an error on the C, it's said my output is not "0", it's "0" followed by a random character. I think there is an error in the evaluation test. In fact, my string is obtained this way :

string s; s=""; s+='0';

The result must be : s=="0" (cast of '0' in a string format), don't you think ?

Thanks, Regards.

-18

ARE YOU ON DRUGS?

+10

Generally speaking, only 25% of world population speaks English, rest of the people use google translate and add "Sorry for my poor English" at the end.:-D

Sorry for my poor English.

Good to see educational rounds back. I am Hoping for the rounds to be on Saturdays(2nd and 4th of the month) so that everyone can participate as it is a weekend.

I did that solution during the contest, but i keep getting WA on test 10, do you have an idea why that happens 25855671

I used two variables l and r to mark the leftmost (smallest) number and rightmost (largest) number of the subtree of current node.

For 'L' and 'R' operations:

When l = r, it means that the current node is at the deepest layer, so we should ignore these operations. Otherwise, shrink the range by making l = mid+1 for 'R' operations, or r = mid-1 for 'L' operations, where mid = (l+r)/2 (the current node).

For 'U' operations:

When l = 1 and r = n, it means that the current node is the root, and we should ignore this operation. Otherwise, check the (x+1)th bit where xth bit is the lowest bit containing 1. If that bit is 1, the current node is in the right subtree of its parent. If that bit is 0, the current node is in the left subtree of its parent. Expand the range by moving l and r pointers.

+11

How do you solve E?