i too missed that when b+1 > 10^9 :(.

Answer for +-- is 6 not 3.

EDIT: You encounter '+' as the first character and break the loop, so your answer = n = 3. You should be getting '3' locally too.

It can.

The case here is that the solution was failing on pretests but got pretests passed verdict and then later got hacked with the pretest itself.

If you say that's the point of hacking phase then i guess there would be no sense in having strong pretests itself or having pretests for that matter. but its like said here since number of people for which its unfair is small the round should/could still be rated. We just have to wait for an official announcement on this matter.

He probably meant to say O(1) extra space.

Have all the submission's been re-judged after the hacking phase? it doesn't look like it.

have there been such cases before? (where checker had some issues during the contest so contest was made unrated)

True, lesson learned — read twice code once. it was tough to see what the question meant once i was sure answer would be n or n-1 or -1.

Looks like the same issue i mentioned here

Hey kindly read the first post again. not swapping the type is the question solved in the editorial and the 'actual' question.
What is am solving is even if types are swapped it is possible to sort the array so we can conclude that type being exchanged or not wont matter since we just have to answer 'yes' or 'no'.

To makes things clear i am mentioning the two cases.

1) The type is not exchanged when we swap elements. meaning if we swap (a, t1, i) and (b, t2, j) we obtain (a, t1, j) and (b, t2, i). (only position is exchanged type remains the same)

For this case read the editorial.

2) The type is also exchanged. meaning if we swap (a, t1, i) and (b, t2, j). Then we would obtain (a, t2, j) and (b, t1, i). (both type and position are exchanged)

In this case too in one of the above post i have explained how we can swap two elements of same type without affecting the element of different type (without changing its type and position after the swaps), so the same idea mentioned in the editorial applies here too. so this is solvable too through the same logic.

Hope this clears things up for you and helps :).

swap (42, 1) and (45, 1) according to process shown above. and then swap (48, 0) (45, 1)

end result

(25, 1) (42, 1) (45, 0) (48, 1) array is sorted.

Think a bit on it, try it out on a paper. its possible to swap and a and c of same type using b of different type. so the solution will always work.

To add -

lets consider (45, 1) (25,1) (421,1) (48, 0)

You can swap the first two using 48,0 like i mentioned before in the above post. it wouldn't affect (48,0)

so we have (25, 1) (45, 1) (421, 1) (48, 0). and now swap (48,421) leading to final sorted array

(25, 1) (45, 1) (48, 1) (421, 0)

Try it out on paper for various cases. it is as the editorial stated. since even if types are swapped it is possible to swap(a,c) of same types if we have b of different type. so the ans would be 'yes' if such a b exists. else we check is its already sorted or not.

i didn't get what you are trying to say.

isn't it already sorted? 25 45 48 421.

According to the problem statement we do not swap the type too. meaning type is bound to the element (does not get exchanged when swapping).

but lets say we have to swap the types even, even then if we have atleast one element with a different type. lets say elements a,b,c, types t1 and t2, position i,j,k.

• a t1 i
• b t2 j
• c t1 k

If we want to swap a and c of the same type. we can do the following

swap(a,b) -> (a t2 j) and (b t1 i)

swap(b,c) -> (b t1 k) and (c t1 i)

swap(a,b) -> (b t2 j) and (a t1 k)

so finally

• a t1 k
• b t2 j
• c t1 i

a and c have swapped positions while b remains same, in the end we swap b to its correct place and thus the element would be in sorted order.

Conclusion — It doesn't matter if type's are swapped or not.

time limit is 2 seconds.

(500)^3 = 1.25 * 10^8

int ans = 0;
for(auto &it:offset)
	ans = max(ans, it.second);
cout << ans;

basically 'curr' is obtaining the number of shifts required for element at ith position to match. and then its frequency is being stored.

then in the above part of code the maximum frequency is obtained and is the answer.

if you check separately for each G then it will lead to TLE since worst case lets say there are approximately n*m G's. (can ignore the -1 due to last being '.')

Now dfs/bfs from each vertex would take approx n*m*4 steps.

so it would lead to net worst case time complexity of t*n*m*n*m*4 which would take >1 second.

I had made the same mistake initially. What you can do is just perform dfs/bfs from n,m and then check if each 'G' vertex is visited.

Its probably due to the overhead of vector being copied each time your are calling your dfs function.

Check the below submission, i changed your code to passing by reference and it got accepted https://codeforces.me/contest/1365/submission/82885046

You are applying dfs from every good vertex. worst case it would take >1 second.

What you can do is just do a single dfs from n,m and then check if every good vertex is visited and bad isn't like stated in the editorial

consider

1 3 4 2

0 1 1 1

ai XOR possible_value_of_k could be a greater value than 1024, i made the same mistake, realized it after i got the RTE.

Test 3 —

10 2 2 4 3 2 2 13 13 2 2 9 11 2 1 14 5 2 1 13 2 2 2 4 5 2 1 11 14 2 2 15 3 2 2 12 10 2 2 13 12

n!= 1 anywhere. i think you might have read the testcase incorrectly. Thw lowest case is n=2 for which answer would be -1.

Constrains were changed mid-contest, m<=n was enforced meaning your input is invalid.

We were picking the cities with min cost, then comparing its cost with cost if it was connected with any of the taken cities. This fails since like in the above test case.
order of the cities acc. to thier cost would be
3 4 5 2 6 1
so we picked 3, then 4. connected it to 3. But here it would have been better to instead pick 5, connect 3 and 5 and then connect 4 to 5.

I Had made the same mistake, found it by trying one of the later test cases.

Correct answer:- 171488866
1
3
5
3 5
2 5
4 5
1 5
3 6

Thanks for this, didn't know about it.