Codeforces Round #516 (on the problems of Moscow Team Olympiad) [Rated]

6 years ago, # ^ |

← Rev. 3 →

There is a separate round for div1 and div2.

→ Reply

prophet_ov_darkness

6 years ago, # |

+38

Unfortunately clashes with GP of Korea.

→ Reply

caojielong

6 years ago, # ^ |

where is the contest "GP of Korea"?

→ Reply

Altair

6 years ago, # |

unfourtunately that's on my school time :(

→ Reply

arthurconmy

6 years ago, # ^ |

+10

On Sunday? :o

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+32

Yes, in arabic countries the firday is a day-off, not the sunday

→ Reply

Ashishgup

6 years ago, # ^ |

+42

Lol, this comment chain is a copy of this one from the first Moscow Team Olympiad held on Codeforces.

Guess somethings never change xD

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+13

\(0_0)/

→ Reply

sguu

6 years ago, # ^ |

+20

i wish there a country where every day is off the school :P

And Hii Bau :D

→ Reply

6 years ago, # ^ |

hi sguu

→ Reply

Nimazare

6 years ago, # ^ |

not only Arabic countries , in Iran the friday is a day-off.

→ Reply

fafafa

6 years ago, # ^ |

In many Chinese senior high schools, Saturday and Sunday are school time. ( >﹏<。)～

→ Reply

BeautyYu

6 years ago, # ^ |

very real

→ Reply

SirirNicheBirirDokan

6 years ago, # |

+30

A Russian Olympiad clashing with open cup, why am I not surprised?

→ Reply

Timm27

6 years ago, # |

← Rev. 2 →

+68

We're going to write it tomorrow official and my team is really scared of Mr.GreenGrape in problemsetters

→ Reply

SrO

6 years ago, # |

+14

Perfect time for Chinese users!

→ Reply

tzc___________________wk

6 years ago, # ^ |

-18

%%%

→ Reply

ko_osaga

6 years ago, # |

+22

Perfect time for Korean users, as the contest is in 7PM, and they can't take today's GP!

→ Reply

fafafa

6 years ago, # |

GL&HF

→ Reply

tzc___________________wk

6 years ago, # |

-7

hope not a mathforces

→ Reply

cai_lw

6 years ago, # |

-20

Really bad time for US users :(

→ Reply

aryaman

6 years ago, # ^ |

Just go back to sleep after the contest :)

→ Reply

BeautyYu

6 years ago, # ^ |

+10

Really good time for Chinese users :)

→ Reply

lqs2015

6 years ago, # |

+15

Perfect time for Chinese users.Thank you Codeforces!

→ Reply

vaibhavvg

6 years ago, # |

The site has slowed down significantly.

→ Reply

pa.n.ik

6 years ago, # |

In Div 2 problem D, the time limit is very strict. Python solution not passing pretest 8 even after all possible optimisations.

→ Reply

gatecse2018

6 years ago, # |

Div2 D pretest 13?

→ Reply

isaaclo97

6 years ago, # ^ |

Yes, this one killed me too

→ Reply

krishna_7

6 years ago, # ^ |

Mine too gave WA on 13, using DFS. Bypassed it by using BFS. Probably recursion stack size was the issue.

→ Reply

DB.LesterLv

6 years ago, # ^ |

the same experience as yours,but my bfs was hacked because i didn't use priority_queue.

→ Reply

CriticalPundit

6 years ago, # ^ |

I too got WA, solved using DFS!

→ Reply

aryanc403

6 years ago, # |

+91

Interactive Problem and Binary Search again.

→ Reply

Linkus

6 years ago, # |

-6

What were the hacks on Labyrinth about?

→ Reply

ez_zh

6 years ago, # ^ |

← Rev. 10 →

+25

Input

20 7
3 6
5 2
......*
.****.*
.****.*
....*.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**....*
*******

Output

for those who used a single queue.

UPD: It seems that not everyone used a single queue failed on this test.

→ Reply

soul_voyage

6 years ago, # ^ |

Then my D will fail systest

→ Reply

2016gdgzoi471

6 years ago, # ^ |

-18

Careless boy

→ Reply

Amoo_Safar

6 years ago, # ^ |

I am using single queue but i pass this test

→ Reply

6 years ago, # ^ |

Same situation in my case.

→ Reply

Linkus

6 years ago, # ^ |

← Rev. 2 →

Lol?

I used a single queue and passed systests in 140ms.

Could you elaborate on why was that supposed fail?

→ Reply

juanigsrz

6 years ago, # ^ |

← Rev. 2 →

Your solution works cause you're checking for a better answer on

if(lf[xx-DX][yy-DY] < lx)

Which is pretty much the same thing as removing the if and making sure you visit the node with the least amount of horizontal moves as possible (i.e., by using a priority queue and sorting by increasing number of horizontal moves)

→ Reply

Adhami

6 years ago, # |

CSAcademy saved me on E with the geometry tool.

→ Reply

6 years ago, # |

← Rev. 3 →

+61

yeah i managed to hack the Grandmaster last minute!!!

→ Reply

6 years ago, # |

+83

After one hour of rocket science, I realised that answer for C is.

sort(s.begin(), s.end()); cout<<s;

→ Reply

6 years ago, # ^ |

So the correct answer for asasas is aaasss, isn't it asasas better? First one has 8 palindrom substrings and the second one has 12.

→ Reply

Jynx

6 years ago, # ^ |

First one also has 12

→ Reply

dorijanlendvaj

6 years ago, # ^ |

First one has:

aaa

sss 12 in total.

→ Reply

6 years ago, # ^ |

Now I understand, thank you all. :)

→ Reply

6 years ago, # ^ |

No, first one too has 12 palindromic substrings..

'a - 3 times, aa - 2 times aaa - 1 time, total - 6

and similarly 6 for sss so, 12

→ Reply

Priyam2k

6 years ago, # ^ |

It's 12 for both. Single character is also a palindromic substring.

→ Reply

isaaclo97

6 years ago, # ^ |

what is the correct approach to this problem?

→ Reply

6 years ago, # ^ |

← Rev. 4 →

+53

It is a correct approach, which can be proven.

Basically the idea is that if you consider any palindrome, its both ends must have same character.

This implies natural bound on the number of palindromes having end of character c occuring x times: x(x + 1) / 2.

One can see, that sorted string reaches that bound exactly.

→ Reply

6 years ago, # |

← Rev. 2 →

+22

I bet there will be lots of FST (failed system test) on Div1.B/ Div2.D, since lots people are using queue instead of priortiy queue, which will results in TLE. Though, it is not easy to hack them :(

→ Reply

EarlOfDitches

6 years ago, # ^ |

+11

Deque is enough, thought

→ Reply

6 years ago, # ^ |

Wait. I don't understand. Wouldn't the same element be put into queue for more than one time? Just like SPFA? Does anyone want to explain that to me?

→ Reply

EarlOfDitches

6 years ago, # ^ |

← Rev. 6 →

Usual 0-1bfs — deque + array that indicates visited cells

You won't visit cell with better cost than first visit.

First time (using 0-1bfs) — cell will be visited with L left moves and R right moves, all other times it will be L+k and R+k where k>=0

P.S. I hope it understandable enough

→ Reply

6 years ago, # ^ |

So the cost will be different if you move vertically instead of horizontally, right? which means the cost in your queue can be not monotomous.

→ Reply

6 years ago, # ^ |

+13

No, it will always be monotonous.

The idea, is to push a vertex at back of deque if the weight is 1, and at the front of deque if weight of edge is 0. Since, there can be atmost two levels of weight in queue, it will always be monotonous.

My submission

You can read about it here

→ Reply

6 years ago, # ^ |

Oh! Use deque, then it is always monotonous! Such a neat application of deque! I got it. Thank you so much!

→ Reply

6 years ago, # ^ |

I didn't think of why you use a deque instead of queue. Now I get it. Thank you!

→ Reply

eXCore

6 years ago, # |

← Rev. 2 →

-139

I am eblan.

→ Reply

Vivek1998299

6 years ago, # |

+14

whats the correct approach for div2 d?

→ Reply

6 years ago, # ^ |

+22

0-1 bfs

→ Reply

6 years ago, # ^ |

I have done same but got TLE in pretest 8

→ Reply

6 years ago, # ^ |

you used map, but it is slow here

→ Reply

6 years ago, # ^ |

So how to speed up my solution? using unordered_map ?

→ Reply

6 years ago, # ^ |

Use 2d array

→ Reply

6 years ago, # ^ |

Thank you very much Numb! :)

→ Reply

rohan1506

6 years ago, # ^ |

so why does bfs fail ??

→ Reply

6 years ago, # ^ |

← Rev. 9 →

10 6  
10 6  
5 2  
**....  
**.**.  
**.**.  
**.**.  
**.**.  
**.**.  
**.**.  
....*.  
.****.  
......

usual bfs will find (8;3) with 5 lefts and 2 rights and won't go to (8;4)

→ Reply

mousehunt123

6 years ago, # ^ |

If we were to use dijkstra's instead, do we sort the items in the priority queue based on the number of left moves, or the number of right moves, or does it not matter? And also, do we sort it in ascending or descending order?

→ Reply

6 years ago, # ^ |

the number of left plus right moves, ascending order (firstly take the least)

→ Reply

6 years ago, # ^ |

← Rev. 2 →

By 0-1 bfs do you mean we will have to take n*m*4 states.I was doing the same.But I could not submit the code because of a bug I had in my code.But my code passes the test you have given above.

→ Reply

6 years ago, # ^ |

Why 4nm?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

-6

Because n*m states for each cell and 4 states for from which direction i entered to that cell.Otherwise if i take n*m states then it was not unique enough and creating conflict.

→ Reply

t1016d

6 years ago, # ^ |

Why do you need the information "from which direction i entered to that cell"?

→ Reply

6 years ago, # ^ |

+10

Yeah.The extra state is not needed.My code is giving correct answer without it.Thank you.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

ignore

→ Reply

2kan

6 years ago, # |

I had RE 8 on D problem because of pragma

pragma

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC diagnostic ignored "-Wunused-result"

I think it can be a problem of new servers. MikeMirzayanov, can it be fixed?

→ Reply

aryanc403

6 years ago, # ^ |

I also got RE 8.

→ Reply

Ashish

6 years ago, # ^ |

I too got RTE on pretest 8

→ Reply

jcvb

6 years ago, # |

+38

how to solve F?

→ Reply

GreenGrape

6 years ago, # ^ |

Let dp(i) be the maximum length of a journey starting at position i.

Then, dp(i) ≥ x iff there exists such j that i + x ≥ j, dp(j) ≥ x - 1 and s[j, j + x) matches either s[i, i + x) or s[i + 1, i + x + 1).

→ Reply

radoslav11

6 years ago, # ^ |

← Rev. 2 →

You can get different $\text{[math]}$ and $\text{[math]}$ solutions with the following observation:

There exists an optimal journey such that these conditions hold:

1) The maximal length of a string in the journey is $\text{[math]}$ .

2) The difference in lengths of two consecutive strings in the journey will always be 1.

Mine didn't pass but maybe someone passed with such a solution.

→ Reply

6 years ago, # ^ |

We believe $\text{[math]}$ shouldn't pass.

Try thinking about $\text{[math]}$ solution :).

→ Reply

tfg

6 years ago, # ^ |

It passes in 2.6 seconds. Turns out using a suffix array to help finding the groups of suffixes that have lcp >= i makes it a lot faster. http://codeforces.net/contest/1063/submission/44310989

→ Reply

jtnydv25

6 years ago, # ^ |

← Rev. 3 →

+34

My solution is $\text{[math]}$ . Not sure if it will pass.

I am going to assume the string to be reversed.This way the strings in a journey are going to be increasing in length.

We can prove that there always exists an optimal answer when t_i has length i. Now, let dp_i be the largest possible length, such that the last string ends at position i. Note that if we can have a valid length l ending at i, we can also have a valid length l - 1, so it makes sense to define such a dp state.

We can binary search on dp_i. For a length l, the second last string is either same as s_{i - l + 1... i - 1} or the same as s_{i - l + 2...i}. We find the rightmost such string which doesn't intersect the last string, and check if this string could be used according to the dp state.

Finding the rightmost possible second last string can be done using persistent segment tree in $\text{[math]}$ . Basically, we have a range on the rank in suffix array the secondlast string can belong to, and a maxmium possible rightmost index for the secondlast string as the constraints.

→ Reply

GreenGrape

6 years ago, # ^ |

-8

It won’t :(

Try to replace binary search with some monotonic observation.

→ Reply

jtnydv25

6 years ago, # ^ |

Passed with small optimizations. Sad that both the accepted solutions have worse complexity.

→ Reply

6 years ago, # |

← Rev. 2 →

-17

Time limit for Problem D is too strict :(

→ Reply

ymz

6 years ago, # ^ |

← Rev. 2 →

Not at all. It can be solved in O(nm).

→ Reply

6 years ago, # ^ |

← Rev. 2 →

my solution is also O(nm) but i am using map which give me TLE on test 8

→ Reply

ymz

6 years ago, # ^ |

+11

So your map don't have a log?

→ Reply

6 years ago, # ^ |

I am using map<pair<int,int>,pair<int,int>> which is very slow When I get the idea why my solution is slow I am very late

→ Reply

Mindjolt

6 years ago, # ^ |

Each access is O(log(n)) time, which seem to be timing out under the current constraints. Instead, try using a 2D array of pairs, so that the time required for each access is constant.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Thanks! after replacing map with 2d array i passed the time limit but I got wrong answer on test 33. Do you have any idea why my solution is incorrect on test 33 http://codeforces.net/contest/1064/submission/44324094

→ Reply

tmwilliamlin168

6 years ago, # |

+23

How to solve Div1 D?

→ Reply

ch_egor

6 years ago, # ^ |

+13

Think of $\text{[math]}$ solution.

→ Reply

nik1996

6 years ago, # |

My solution for Div2 D is failing on test 13. Could anybody help me where I am making a mistake? Thanks!!

→ Reply

striver_79

6 years ago, # ^ |

The time limit is too strict, possibly due to recursion and stack size.

→ Reply

Heisenberg302

6 years ago, # ^ |

← Rev. 2 →

As far as I understand you did a dfs and checked the conditions and you dont visit the same place twice. However consider this

.....

.*.**

.x.**

x is where you are initially.

lets say you can go left at most once and right at most twice.

Then if you go left and go up twice and go right twice you will mark (0,2) as visited and when you come there again from (2,1) -> (2,2) -> (1,2) -> (0,2) you wont continue since it (0,2) is visited however you went right only once and if you continued you could go right.

→ Reply

Ashish

6 years ago, # ^ |

Expected answer is 9. right?

→ Reply

SJ151

6 years ago, # ^ |

Thanks bro i got my mistake

→ Reply

CriticalPundit

6 years ago, # ^ |

So what's the correct approach to solve it using DFS? Thanks for pointing out the mistake though.

→ Reply

brdy

6 years ago, # ^ |

It's very hard to (if possible) because dfs doesn't have properties of shortest paths.

→ Reply

CriticalPundit

6 years ago, # ^ |

Ok Thanks that makes sense.

→ Reply

szawinis

6 years ago, # |

What’s pretest 10 in div 2 E?

→ Reply

Daili

6 years ago, # ^ |

Probably something like 1 black and 29 white.

→ Reply

Ranadev_CaptainR

6 years ago, # ^ |

Yeah I was getting wrong answer on pretest 10

→ Reply

6 years ago, # ^ |

+17

n = 30, jury mostly assigns colors randomly.

However there is a small twist: in all of jury tests (except for sample) if it is possible to assign a color, such that it makes impossible to separate points later jury will always do that :).

→ Reply

6 years ago, # |

← Rev. 2 →

Div 2 Problem C was tricky. I can't prove solution correctness. Can anyone give me a proof ?

→ Reply

NewBalance

6 years ago, # ^ |

+31

answer is just sorted s. if N_x is number of occurrences of x in s. then number of palindrome substrings $\text{[math]}$ because first and last letter of palindrome must be same. on the other hand this number is achieved when s is sorted.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

-10

I am trying to understand this formula you stated.

→ Reply

NewBalance

6 years ago, # ^ |

$\text{[math]}$ is number of ways to choose substring so that it starts and ends with x

→ Reply

6 years ago, # ^ |

← Rev. 3 →

-24

Shouldn't it be (nx) * (nx — 1) / 2 then ?

Number of ways of picking 2 things out of nx. (Combinations)

→ Reply

NewBalance

6 years ago, # ^ |

substring can have only 1 character

→ Reply

6 years ago, # ^ |

← Rev. 2 →

-11

Oh thanks!

Got the same formula after accounting for substrings of length 1 (adding Nx to my formula)

→ Reply

roll_no_1

6 years ago, # ^ |

I am still not able to understand this formula. The no. of palindromes in a string of length n having all characters equal to c will definitely be n * (n + 1) / 2 but how does that justify that summing over this expression over the frequencies of all chars in a string having more than one character gives an upper bound on the no. of palindromes that we can have in a permutation of the string ?

→ Reply

6 years ago, # ^ |

see this comment

→ Reply

roll_no_1

6 years ago, # ^ |

That helped. Thanks. :)

→ Reply

MiohitoKiri5474

6 years ago, # |

-10

gag forces?

→ Reply

6 years ago, # |

With new Judging infrastructure, I hope System testing would be a bit faster.

So that i upsolve after that :)

→ Reply

mango_lassi

6 years ago, # |

← Rev. 2 →

+29

C and D combined made this the worst problemset in my opinion I've seen so far in codeforces.

C was binary search. Nothing else, just binary search, just hidden behind a silly problem statement about lines. There's lots of complaints about every interactive problem being binary search and then we get new problems like this :/

D was a math problem emphasizing exactly what I hate about most math problems. You just have to make a trivial observation (either n or the number of rounds is small), and then calculate stuff. Of course, the calculation isn't interesting either, It's just super annoying case handling.

The especially annoying thing about D was that the last person can take just one candy, even if they have a sweet tooth. That adds nothing to the creative part of solving the problem, and around doubles the amount of case handling. Why was that there?

In my recent memory I don't remember any problem worse than either of these, and now we got two of them on the same round :/

→ Reply

bazsi700

6 years ago, # ^ |

-10

I 100% agree. Missed that sweet tooth — one candy case for 30 minutes during contest...

→ Reply

6 years ago, # ^ |

+73

Well, while I will agree that D had hard technichal part, I not very much agree with your complaints on C.

You just needed to come up with cute binarysearch-like construction and the implementation is very short. If the problem was obvious to you -- just get AC in 5 mins and move on!

→ Reply

6 years ago, # ^ |

+10

For me div1C was not trivial, and had a lot of challenges, not just "implement binary search". I don't think the geometrical construction was obvious at all.

→ Reply

vipin1407

6 years ago, # |

In problem D Div 2, why dfs not working ?? thanks

→ Reply

6 years ago, # ^ |

← Rev. 3 →

+16

(edited) dfs won't work, because you can end up in a square with "wastefully expended left/right moves". Meaning, you could end up in the same square later with fewer left/right moves. What do you do at this point? If you reprocess the square and start doing dfs again from it, you will TLE for sure. If you don't reprocess the square, you might get WA if later on you fail to reach some square because you had wastefully expended left/right moves earlier.

edit 2: or maybe dfs will work if you can do dfs in such an order that you never wastefully expend left/right moves?

→ Reply

vipin1407

6 years ago, # ^ |

thanks, baobab. I have found the mistake :)

→ Reply

Heisenberg

6 years ago, # ^ |

← Rev. 3 →

Consider you started from vertex 'X' and at some point you are at vertex 'Y'

DFS ensures that you visit every vertex only once so you won't come to vertex 'Y' again. But as the graph formed might be cyclic i.e. there can be multiple ways to reach a vertex 'Y' from 'X' and there can be a possibility that there is some shorter path to 'Y' that you'll miss.

PS: Dijkstra :)

→ Reply

6 years ago, # ^ |

Also: BFS

→ Reply

6 years ago, # ^ |

Dijkstra can be fast enough on C++ but on Java it apparently wasn't: https://codeforces.net/contest/1064/submission/44311014

→ Reply

aryaman

6 years ago, # |

← Rev. 2 →

I got trolled by div2 C lol :/ Wrote 80 lines of buggy code...

→ Reply

manuchroma

6 years ago, # ^ |

My solution in python:

def ans():
    n = int(input())
    c = bin(n).count("1")
    ans = pow(2, c)

    print(ans)

tc = int(input())
for _ in range(tc):
    ans()

→ Reply

aryaman

6 years ago, # ^ |

Oh sorry, I meant div2C. My solution for B was the same idea.

→ Reply

BogdanRazvan

6 years ago, # |

+47

Test 40 Div2D distroyed so many dreams :(

→ Reply

Slow_But_Determined

6 years ago, # ^ |

There goes my hopes of entering div1 :(

→ Reply

egor.okhterov

6 years ago, # ^ |

wat is hope?

→ Reply

---o_o---

6 years ago, # |

+10

weak pretests in div2 D

→ Reply

Gassa

6 years ago, # |

+63

The Div1 problem E about lasers is beautiful in my opinion, thanks to the authors!

→ Reply

mingaleg

6 years ago, # ^ |

+10

You are very welcome :)

→ Reply

Radewoosh

6 years ago, # |

+18

I guess that my solution to F has complexity O(n^2.5)... I implemented O(n^1.5·log(n)), but it turned out to be slower and more memory-eating, so I resubmitted older brute force, which passed with max time lower than one second.

→ Reply

jtnydv25

6 years ago, # ^ |

+12

WOW, and my $\text{[math]}$ solution failed!

→ Reply

Radewoosh

6 years ago, # ^ |

← Rev. 2 →

+27

OK, OK, sorry, it's O(n^1.5), just noticed some amortization.

→ Reply

WisdenCoder

6 years ago, # |

I GOT TLE IN TEST 10,IN DIV 2 C MY SOLUTION time complexity in o(nlogn) but still it got timed out. is it due to slow input output?

→ Reply

MiohitoKiri5474

6 years ago, # ^ |

Actually it could be O ( N ). Flash sort!

→ Reply

katana_handler

6 years ago, # |

Can somebody please help me finding why my code for DIV2 D gives a run time error?? CODE

→ Reply

AkshajK

6 years ago, # |

+52

The difficulty curve was.. 98.9%, 75.2%, 73.7%, 5.9%, 2.1%, 0.4% (percentage of people who solved each problem)

Perhaps codeforces should consider including problems solved by between 6% and 73% of participants???

→ Reply

6 years ago, # ^ |

-8

Impossible

→ Reply

6 years ago, # ^ |

+23

It was a bit... unexpected to us.

We held a presolving of the moscow team olympiad, from which the problems are. And most of the teams got accepted all problems except problem corresponding to Div1F.

So I was even worrying whether our Div1D and Div1E are a bit too easy.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

maybe the next time the presolvers group should contain not only red and orange coders, not only ROI prizers and ROI winners?

→ Reply

code_kika

6 years ago, # |

What's Test 27 in Div2 D?

→ Reply

aniketgattani

6 years ago, # |

Can someone explain why Div2 D Test 40 failed for me??

44306721

→ Reply

GGAutomaton

6 years ago, # ^ |

Just go left, straight up and down, then go right. You can visit all the free cell. 0-1 bfs can solve this problem. Because moving up and down costs 0, you should push one colomn into the queue at the same time when visiting a new cell.

→ Reply

aniketgattani

6 years ago, # ^ |

but what is the issue with normal bfs even in normal bfs i am trying to find the node closest to a popped node so that the nearest nodes are reached first.

→ Reply

GGAutomaton

6 years ago, # ^ |

Normal bfs just visits the nodes as quick as possible. This means it may go left and right for several times and reach the limits. But it is possible that existing a path which is longer than the first one but turn left or right less. In this situation, bfs will visit a node that already been visited, and won't push the new node into the queue, leaving some of the nodes not visited. My code

→ Reply

aniketgattani

6 years ago, # ^ |

← Rev. 2 →

Thanks GGAutomaton understood :)

→ Reply

KNaga

6 years ago, # |

How to solve Div2 E??

→ Reply

kronos

6 years ago, # ^ |

Use binary search! Put x somewhere to the middle (from 1 to 999999999) and fix it (x=3, for example) and try (3,0) (save the color). Next try (3,500000000). If these two point have the same color next point you should try is (3, 750000000) if colors are different next point should be (3, 250000000). Beware of edges cases: one with all points with the same color and when another one only one color is different 44313158 (very bad code, sorry)

→ Reply

gurshaan

6 years ago, # |

Can someone look into my solution for DIV 2 D problem 44308344 and tell me where I am going wrong. Thanks :)

→ Reply

6 years ago, # |

How would you guys come up with the solution for problem C, Div 2? And how would you test it to make sure that every time you sort the string’s characters you get maximum number of palindromes?

→ Reply

6 years ago, # ^ |

Sixth sense!

→ Reply

6 years ago, # ^ |

I manually checked it for random strings of length 10

→ Reply

6 years ago, # ^ |

+13

I was trying something on paper and I suddenly saw that for aaaaab the count is much higher than its other permutations, once I realised that I could prove it easily as :

suppose you are counting palindromes with a as it ends, now if you insert anything in between two a's, that may decrease count by 1. Hence all occurences of a character must be together.

→ Reply

newbiegcz

6 years ago, # |

where is the editorial?

→ Reply

DmitriyH

6 years ago, # |

← Rev. 4 →

DIV1 B:
Suppose, system tests are weak.
This solution based on simple BFS and single queue (not BFS-0-1) 44319324 passed all the tests.
UPD: tests are not weak, my solution differs from BFS in visiting vertexes twice and more times.

→ Reply

6 years ago, # ^ |

I think this solution is right. It has right answer on my hack

→ Reply

cai_lw

6 years ago, # ^ |

← Rev. 2 →

+21

This is equivalent to SPFA (or Bellman-Ford with queue). It is a correct shortest path algorithm, and although its worst case complexity is O(VE), practically it's very fast for most graphs.

SPFA can be hacked by specially constructed graphs, but I don't know whether such graph exists given the restrictions of this problem. Also, since SPFA is not popular outside China, non-Chinese problem setter usually don't make anti-SPFA tests.

Disclaimer: My solution used the same algorithm.

→ Reply

DmitriyH

6 years ago, # ^ |

+18

Thanks for the information, didn't know neither about SPFA neither about Bellman-Ford. There is a reason to read something.
Finally, found the difference between my solution and simple BFS: in my case one vertex can be visited once again, if there is better path found.

→ Reply

6 years ago, # ^ |

I've just known that some of the solutions implement BFS using deque instead of a queue, which allows them to keep the queue monotonous. Then the complexity is the same as a standard BFS — O(V + E), which is correct. However, I do think those solutions using queue is hackable, but there might not be anti-SPFA tests.

→ Reply

vivek17geek

6 years ago, # |

Div2 D Time depends a lot on Compiler, same solution in c passed and c# TLE

→ Reply

arg_53

6 years ago, # |

← Rev. 2 →

It's possible to pass Div2 D using shortest path if you use a faster heap in C++... http://codeforces.net/contest/1064/submission/44318340

→ Reply

prakhar17252

6 years ago, # ^ |

Even built-in priority_queue worked fine for me. Here is my solution.

→ Reply

madhur4127

6 years ago, # ^ |

simply use deque and it passes in tenth of your time.

→ Reply

11101001

6 years ago, # |

How to solve Div2 F? Can this problem be solved with binary search？

→ Reply

SJ151

6 years ago, # |

Can anyone tell me why i am getting runtime error on pretest 8 44315444 Please help i am not getting the mistake

→ Reply

madhav_1999

6 years ago, # |

← Rev. 2 →

-6

Hey, ch_egor MikeMirzayanov cdkrot, my submission 44312315 gave TLE during contest, but identical submission 44320638 gives AC now. Can anything be done about it?

→ Reply

tanmay28

6 years ago, # ^ |

Nothing can happen now. Same thing has happened with me twice, but they don't re-evaluate our code after the contest. See the codes 37815677, 37820871. They are identical but one gave TLE during system testing while the other one passed after the contest. I also posted about it in a comment, but no one even cared to reply. I also messaged Mike on CF, but he also just ignored the message. Here is the link for the discussion.

→ Reply

Jakube

6 years ago, # ^ |

Dude, your identical submission also nearly TLE'd. So the TLE during the contest seems reasonable. There is no reason to judge your solution again.

→ Reply

madhur4127

6 years ago, # |

shorest solution I ever encountered:

input();print(''.join(sorted(input();input())))

→ Reply

6 years ago, # ^ |

+24

31086861

→ Reply

madhur4127

6 years ago, # ^ |

probably it is shortest for div 2 C?

→ Reply

6 years ago, # ^ |

+16

26869940

→ Reply

tantam75

6 years ago, # ^ |

did you write a script to find that?

→ Reply

6 years ago, # ^ |

+17

no
i just remember

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Cool :)

→ Reply

fmqjpt

6 years ago, # |

-10

what is this c

ugh

→ Reply

stevie1024

6 years ago, # |

Is it possible to get the complete input for test #10 in div2D? I'm really curious what I did wrong in #44322132 and can't get it...

→ Reply

stevie1024

6 years ago, # ^ |

Well nevermind, found my mistake.

→ Reply

kronos

6 years ago, # |

BFS with one queue is fine for div2 D: 44322392

→ Reply

_overrated_

6 years ago, # |

-17

Thank you for pretests, GreenGrape

→ Reply

GreenGrape

6 years ago, # ^ |

+42

Joke’s on you, but I was involved only in d1F.

→ Reply

_overrated_

6 years ago, # ^ |

You stole my rating and now you’re trying to steal my contribution

→ Reply

I_Love_CardiB

6 years ago, # ^ |

Funny, its the first time i have seen author trolling the participant xD

→ Reply

Ninjaclasher

6 years ago, # |

-13

So much math.

→ Reply

Heisenberg

6 years ago, # |

+23

Test 40 for Div2-D be like

→ Reply

noobied

6 years ago, # |

How to solve Div 2 B i didn't able to find the approach

→ Reply

kronos

6 years ago, # ^ |

Brute force solution for a from 0 to 20 and try to find a connection between a and the answer

→ Reply

juanigsrz

6 years ago, # ^ |

This is a good tip in general, it's way easier to prove if something in particular works (or doesn't) rather than finding the solution itself

→ Reply

6 years ago, # ^ |

← Rev. 2 →

just observe that since $\text{[math]}$

If i'th bit of a is 1, then if i'th bit of x is 0 or 1, in both cases i'th bit of $\text{[math]}$ is 1, and we are safe.

But if i'th bit of a is 0, then i'th bit of x must be 0, i'th bit of $\text{[math]}$ will be 2,i.e, greater than 0. which will make $\text{[math]}$ greater than a.

hence the answer is $\text{[math]}$

→ Reply

Himitsu

6 years ago, # ^ |

← Rev. 2 →

But in case when ith bit of a=0 and x=0,

$\text{[math]}$ will also give 0 which is equal to a right?

→ Reply

6 years ago, # ^ |

Yes, that's the point, if i'th bit of a is zero then i'th bit of x must be zero.

→ Reply