Thanks for the reply! Actually I misunderstood that 'Output' was an answer and 'Answer' was my output ;)

Could anyone please explain why this code prints wrong output compared to my local execution environment? (Problem D)

http://mirror.codeforces.com/contest/1469/submission/102626247

input:
1
5

expected(local):
7
6 7
5 7
4 7
3 7
7 2
7 2
7 2

actual(codeforces):
7
4 7
5 7
6 7
7 3
7 3
3 2
3 2

And I spent almost 2 hours to solve E.

I don't think XOR 1 2 XOR 2 3 XOR 1 3 is enough information for find out what is a2

Seems like cout is not flushed so not inputs are provided.

What a bitwise math. Thanks!

So how can I find a1 anyway?

I got 4 WA on A and almost kill myself when got AC

Pretty nervous having sense of getting WA on systest D. :o

You can sweep the entire column.

I smell math for this round either

My pleasure. Actually I thought just like you at first :)

by statement of problem C,

... is the answer given by the jury's solution.

and the jury's solution is printing more than 6 decimal points.

No it actually has difference 1.3333337 — 1.333334 = 0.0000003(3e-7) which is smaller than 1e-6

I think printing %.6f would be fine and can not be hacked.

So you mean the ancilla bit has information about the result which is result = (result + initial value). And we can get the answer by using that 'information' ?

Round was ended earlier than Russia vs Spain. What a surprise.

Oh I see.. So the type of oracle should be determined by kind of "behavior of the function". Thanks!

A quantum bit will be set to |0 >  if measured value is 0 otherwise |1 >  after measuring so yes, it will break the superposition.

Is XOR used only for satisfying inversability? If so, Can XOR(CNOT gate) be replaced by any another two-bit unitary operation?

Thanks. I suddenly wonder how multi-bit logic gates actually work on a real quantum computer atomically :| Amazing!

Nickolas, One question please. Are the inputs of Problem G any random state of qubits? Like, x[k] = α|0 >  + β|1 >  with any proper α and β?

Thanks. Actually I saw Deutsch-Jozsa algorithm before(Yet not fully understood). But how this can be applied to Problem G?

Is there any materials for quantum oracle? I'm stuck in G :'(

Excited to code Q#. Are the problems typical problem-solving style or some kind of different one? Like, using unitary matrix or something.-

Then there's no systest so there's maybe also no such 'during' system testing ? ;)

DP round :o

(Correct me if i am wrong until this point)

As long as you use correct algorithm, (like tarjan's SCC or something) I think it would be fine.

count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.

You can just count number of SCC vertices which has 0 indegree, but when counting, exclude a SCC vertex which contains the capital vertex.

Solving all problems in 25 minutes (me) VS Scoring 1 point in 90 minutes (South Korea)

I'm seriously wondering which one is harder.

ummm :| I think you should read this

Since h is strictly increasing, it is optimal to distribute as much as favorite cards to each peraon. eg. Let 3 people likes card 1 and each person has 2 cards. If number of card 1 is greater than or equal to 3×2, just distribute 2 cards for each and leftovers are 'dont care'(any other will have it and it has no effect to score) Else if the number of cards is less than 3×2, now the problem is distribute m cards to 3 people while maximum the score

https://stackoverflow.com/questions/31821951/c-difference-between-stdlower-bound-and-stdsetlower-bound

3 1 1

2 3

Your answer = 2 (1 -> 2, 1 -> 3)

Correct answer = 1 (1 -> 2)

Consider any single number of card. Now the problem is 'For given N cards and M people, each person can have at most k cards. What is the maximum score?'

My idea : First, run dfs on capital vertex. While running dfs, make every path as bi-directional. Now build Strongly Connected Commponents. Count number of vertices which has 0 indegree expect the one containing capital vertex.

let

each entry represent the probability (ex : 1 → 2 is the probability of going from 1 to 2)

Then, A² =

(this one is bit hard to recognize, by the way.)

By generalization,

where ... can be any sequence of n - 1 vertices

The answer is MAX_line(sum - of - the - (row, column)[M_line * A^m - 1]) where M_line is initial state of for each line and (row=index of vertices belongs to initial line), (column=vertex index of destination) (i'm sorry this must be hard to understand, but this is my best explanation) (and with some optimizations originally written in editorial)

You can google 'markov chain' for much more elegant explains.

Think x axis as position and y axis as time. then,

For moon, x = yw

For cloud with speed s, x = sy + x_o and x = sy + x_o + l where s is 1 or -1

Problem E turns out to be an exact Markov chain problem xD

LOL. Which one you think is harder?

Super fast editorial !

By reading examples on B. so I can say actually that is based on intuition instead of reading the constraints on B very carefully. (without considering whether constraint is really wrong like commented below)

LOL. So D was literally the 'upgraded version' of the older one.

Because you don't know what sequence is after N.

Whhhhat? So constraint was just like http://mirror.codeforces.com/contest/956/problem/D, which was the original one I thought and I was still not able to manage it ;'(

I've written down several equations about Problem D, but thrown it away eventually. And I realized that wind speed is always positive after the contest. :P

https://mirror.codeforces.com/blog/entry/59770?#comment-434977

Solved it using Li-Chao tree. Learned a new thing. thanks!

Your lambda code still does not satisfy the rule.

sort(s+1, s+n+1, [](string s1, string s2){
	return len(s1) > len(s2);
});

This is the right one. without the equal sign.

http://mirror.codeforces.com/blog/entry/59770?#comment-434966

For your case,

bool comp(string l, string r){
	return l.length() < r.length();
}

Let A = C + 2^a, B = C + 2^b, A ≥ B.

According to the problem, A - B = 2^a - 2^b = 2^x should hold.

Divide each side by 2^b. The equation would be 2^a - b - 1 = 2^x - b.

1) If x - b = 0, then 2^a - b - 1 = 1 -> 2^a - b = 2 -> a - b = 1 -> a = b + 1

2) If x - b ≠ 0, contradiction since left side is odd and right side is even.

So there are at most 3 which is C, C + 2^a, C + 2^a + 1

IMHO, this kind of problem is little challenging for div3 but worthy at the same time.

C++ sort requires strict weak ordering. for more, https://stackoverflow.com/questions/32263560/errorinvalid-comparator-when-sorting-using-custom-comparison-function

How to solve E?

since [205-208] is mapped to 205. if [205-212] is mapped to 205, it is illegal to condition since there are 8 values between 205 and 212 (205,206,207,208,209,210,211,212)

Ok. I'm back with my laptop. Because 0 2 0 254 254 is lexicographically greater than 0 1 1 255 254.

• wait, i misunderstood your statement. I'll fix soon.

First, sort array in non-decreasing order.

We must have a barrel which contains a₁ stave. So each maximal total sum of volumes of barrel cannot be larger than a₁ + l

let C = (number of stave which has length  ≤ a₁ + l) - N.

If C < 0, then answer is 0.

Otherwise, While picking staves, if C > 0, pick the smallest stave you have, and decrease C by 1. else, pick the largest stave you have.

How to solve F with LCP?

Does sqrt work in O(1)?

The worst excuse ever.

Oh, wow. That's a very impressive approach! Thinking final sequence as symmetry first, and removing redundant tail part. I really learned many things from your code. XD

Yeah, I also have to admit that I didn't read the statement carefully. What I'm sad is that I asked for it so late. If there were more time, I could solve it. ( since I got AC just before ;) )

Run two binary searches. one for 1,....,K and another one for K + 1, .... LARGEST_VALUE, ... K + 1

Yes. Now you panicked just like me.

Read accidentally, got spoiled. :o

Problem D. — I thought h₁ was a typo in h_1 ≤ H: no sand should go over the fence; because of the no one clause, but as reading whole statement and asking to judge, turns out it wasn't ;'(

I think this would be helpful to explain it more. :)

Firstly, unordered_map with default settings has a pretty large constant. It can be decreased a lot by calling reserve and max_load_factor methods as explained at the end of this blog. I think without this unordered_map is slightly faster than map, with this it should be much faster — assuming random input.

Although unordered_map has constant time complexity, that constant time is not the same with trivial operations such as access of array. So the actual time complexity of your code is αN² where α is the constant value of unordered_map operation. This value can easily exceed over 10^8 where α ≥ 4

Div1C. Any relation with editorial and solution code? The definition of 'state' is different at least i think. The solution code is just representing the state in base of 10.

The time limitation on Div2C is too tight.... just reassigning gcd value made it passed.. -_-

NVM. my approach was wrong. it was a simple pyramid-dp problem like answered below.

Using 2d segment-tree would be enough, I think.

Look at the title of that problem. There's a huge hint.

I realized that the TITLE of the Problem Div2D,Div1B was such a huge hint, but it was too late. no time to debug.

I asked about it and the answer was no.

upvoters : did contest with good score

downvoters : the others

fight of the most subjective voters

Although I did the contest badly, overall problems are good. But it's also true there's some mistakes on statements :'(

single line of mis-coding leads me to WA on C and I couldn't never fix it until the end of the contest.

My head just blow up. what a stupid.

Problem D. Why O(NMlog10^5) gets TLE where N = number of query1 and M = number of query2 ?

This round is for 1600 below

[33,34,35,36,37,38,39] , [236,237,238,239,240,241,242] Other numbers are 'don't care'.

Ans: 33 236 236

You can pick contiguous range, [a₁, a₂, ...a_n] where a_n - a₁ ≤ K, a_i ≤ 255, as many as you want. Each element must belong to exactly 1 group(range). Now you are given a sequence. For each element, find a group it belongs. replace the original element with the first element of that group. After replacing all elements, the result sequence should be the lexicographically smallest among all possible results.

Notice that 119 turns into 114 which means range [114, 119] is mapped to 114. so 121 cannot be mapped to such value lower than 119 since K = 7

No your factorization code looks fine. The problem is, your code still has NlogN complexity. operator [] of map is basically same with map.find which takes logN time. You have to maintain an another array that "maps" each element into another. The reason why std::map is used is to mark which index of mapping array should be mapped for each element. In short, mapping[A[i]] should be accessed in O(1) so mapping variable is just an int array. We use std;;map to fill this array.

Because nesting set operations in N² code means the total complexity becomes N^2log(n) which is nearly 3×10^9. (Normally we suppose 10^9 iterations take 1 second)

While you can map each elements into another array access time of which is O(1). To do that, prepare map < int, int >  and int[5000]mapped. Now in input phase, you can map each elements into single index of mapped.

eg) 28 -> 7. Find if 7 exists in a map. If not, map[7] = nextidx +  + . now mapped[i] = map[7].

Thanks for the awesome problems! I wish there was a explanation for a example though. :)

Problem B

Based on intuition : easy

Based on Proof : hard

That'_s not true. unordered_map is getting slower when many hash collision happens. Otherwise, unordered_map is much faster than normal map.

You ignored MAP[A[i]] that was originally stored.

test : 9 10 11 12 8 9 10 11 10 11

ans = 4 yours = 3

unordered_map is based on Hash table. Normally a search operation of hash table works in amortized(1) but worst is O(N) (caused by hash-collision). std::map, on the other hand, is based on red-black tree, which has O(logN) complexity in search operation on average. Your solution was hacked by anti-hash test.

You have to search such value which is sum of arrows until all warriors dead. When all warriors are dead, reset the value to 0 and repeat the previous step. Your approach is not considering about remaining helath of warrior (which is warrior[index]) in C2.

Ex) warriors : 3 2

arrows : 2 2

After first arrow is shoot, first warrior still has 1 hp. Your code might be ignoring it.

Choosing maximum difference regardless of sum of other values is not optimal

LOL

Parallel rounds, yeah! Hope translation of this round would be better.

According to the code(http://mirror.codeforces.com/contest/965/submission/37617599), It just merge two sets by joining smaller one to larger one.

I don't think that works.

36 2 9 3

when d = 1 or 2 : impossible

when d = 3 : possible distributions = 6,7,8 , formula gives 6. best is 7.

For E, I had right idea but failed in implementing minimizing depth.

Might be a timezone is wrong when creating a link. That should be Moscow time which is https://www.timeanddate.com/worldclock/fixedtime.html?msg=Codeforces+Round+%23476+%28Div.+2%29+%5BThanks%2C+Telegram%21%5D&iso=20180425T2035&p1=166&ah=2

Can't understand the problem.. Descriptions are so suck.

What a simple idea it was. Deleting a vertex will separate trees, that thought confused me. thanks.