Topcoder Open 2015 Round 2B post-match discussion

9 лет назад, # ^ |

+22

Matching of what with what?

The only passing solution I've seen so far goes like this: First, add a white border around the whole thing. Mark two connected components of opposite colors as "neighbors" if they share an edge. Prove that the graph of neighbors is a tree (use the diagonally-connected condition for this). Prove that this graph never changes (up to isomorphism which preserves the border node) when you make a move. Prove that any pattern with the same neighborhood graph (again up to isomorphism which preserves the border node) can be reached. Look up the rooted tree isomorphism problem on the internet, it's kinda well-known.

→ Ответить

Reyna

9 лет назад, # ^ |

Thanks for answering, i would rather not embarrass myself with saying what i did anyway it's not worth your time xDD thanks again for answering

→ Ответить

KuribohG

9 лет назад, # ^ |

I don't know how to prove that any pattern with the same neighborhood graph. Can you describe it in detail? Thank you! And also I want to know is there a solution for this problem modified a bit. What if change the condition "Each character of initial and target represents a 10000 by 10000 square of cells, all of the same color." to "Each character of initial and target represents a 1 by 1 square of cells, all of the same color." I don't know how to solve this...

→ Ответить

9 лет назад, # ^ |

+16

About the tree: For each connected component C, divide the neighboring cells (not components) into two categories: inside and outside. A cell is called inside if there is no 4-connected path from that cell to some far-away cell (for example, cell (1e20,1e20)) that doesn't contain cells from C. I claim that all the outside neighbors belong to the same connected component. Proof: they are 8-connected (since they lie along the outside edges of C), so they are also 4-connected (since the task says that whatever is 8-connected is also 4-connected). View this outside neighbor component as the "parent" and the inside ones as the "children", and it's a tree. Ok, this is still not the most mathematically formal proof, but hopefully good enough for you.

About the 1x1 square of cells: It doesn't change anything, see my post further down in the thread.

→ Ответить

KADR

9 лет назад, # ^ |

+26

I used maximum matching to check if two trees are isomorphic. It's definitely not the easiest way to do that, but it works, too.

→ Ответить

xorfire

9 лет назад, # ^ |

Out of curiosity, how would you use max matching to check (rooted)tree isomorphism? I am unable to understand from your code.

→ Ответить

KADR

9 лет назад, # ^ |

+19

Let f(v1, v2) be the function that is equal to 1 when subtrees rooted in v1 and v2 (v1 is from the first tree and v2 is from the second one) are isomorphic and 0 otherwise. In particular, we are interested in finding f(0, 0) which is the answer to our problem.

A few properties:

1) If v1 and v2 have different number of children, then f(v1, v2) = 0.

2) If v1 and v2 are both leaves, then f(v1, v2) = 1.

3) If v1 and v2 are both non-leaves, then we can first find f(w1, w2) for all pairs (w1, w2) where w1 is a child of v1 and w2 is a child of w2. Then for each subtree rooted in w1 we need to find a corresponding subtree rooted in w2 and these subtrees have to be isomorphic to each other (i.e. f(w1, w2) = 1). The latter can be done with maximum matching on the graph where nodes are children of v1 and v2 and there are edges between all nodes w1 and w2 for which f(w1, w2) = 1.

→ Ответить

permin

9 лет назад, # |

Is smth wrong with 8-connected metric for 500ptr?

→ Ответить

permin

9 лет назад, # ^ |

ok, everything is fine with it :)

→ Ответить

9 лет назад, # |

← Rev. 2 →

The 1000-pointer seemed awfully similar to an old ACM task, though I can't remember which ACM competition it was, can anyone help? The ACM version was a general graph, not a tree, but without the "use each edge at most twice" restriction.

The ACM version is solved the following way: keep an upper limit d[i] for the minimum cost if the token starts on node i. Keep updating as follows until we no longer see improvement: For each starting point s and each value C, find the minimum cost K (using min-cut) to block the token from reaching a leaf assuming that it's not allowed to go through any node v with d[v]<=C. Then assign d[s]=min(d[s],C+K). Obviously d is an upper bound, and you can do a long and complicated proof that it's in fact the exact value.

How to add the "each edge twice" restriction to this?

→ Ответить

zxqfl

9 лет назад, # ^ |

I'm the round writer; the code is pretty short so I'll let it replace the explanation: http://pastebin.com/nS22YuWN

nodes[i].dp[x] = cost paid by Alice when we are at node i and the graph above node i will let Bob force Alice to pay x.

→ Ответить

TomConerly

9 лет назад, # ^ |

The ACM version is tunnels from 2007 world finals (https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=1812).

→ Ответить

9 лет назад, # |

+16

Note to self: Polynomial hashing is not good for isomorphism of trees.

→ Ответить

9 лет назад, # ^ |

If I needed to challenge such a solution, I would be completely stumped (assuming the number of children was also directly involved in the hash, so you don't hash {0} to the same thing as {0,0}). What's the challenge?

→ Ответить

9 лет назад, # ^ |

+16

This is relevant part of code:

int GetHashTree(int v) {
    vis[v] = 1;
    VI neis;
    for (auto nei : tree[v]) {
      if (vis[nei]) { continue; }
      neis.PB(GetHashTree(nei));
    }
    sort(ALL(neis));
    int acc = 1;
    for (auto x : neis) {
      acc = acc * P + x;
    }
    return acc * B;
  }

and this is challenging test: http://ideone.com/zkyaO2

I'm too lazy to check it properly, but hash of resulting trees are just equal polynomials of variables B and P (which is pathetic).

When changed to this:

    sort(ALL(neis));
    int acc = 1;
    srand(0xC0FFEE);
    for (auto x : neis) {
      acc += x * rand();
    }
    return acc;

it works well.

→ Ответить

riadwaw

9 лет назад, # ^ |

+11

Size of the board is small so actually, you don't have to hash anything at all. You may just sort it in each level like here

→ Ответить

9 лет назад, # ^ |

Yes, I noticed this during challenge phase. I keep forgetting that in TC we often are meant to do things in more stupid way than we should :P.

→ Ответить

al13n

9 лет назад, # ^ |

+32

Why use any hashing at all if deterministic solution is simpler:

map<vector<int>,int> C;
int GetClassOfTree(int v){
  VI neis;
  for (auto nei : tree[v]) {
    neis.PB(GetClassOfTree(nei));
  }
  sort(ALL(neis));
  if (!C.count(neis)){
    int t = C.size();
    C[neis] = t;
  }
  return C[neis];
}

→ Ответить

9 лет назад, # |

-44

Can anyone please explain how to solve the 250 point problem? I don't feel like wasting more time and effort in trying to find a solution myself for such a horrendous problem.

TopCoder keeps its legacy of ugly and boring problems. Well, at least we'll have two Codeforces rounds next week.

→ Ответить

9 лет назад, # ^ |

+19

Yeah, truly horrendous ( ͡° ͜ʖ ͡°):

LD res = 0;
LD prod = 1;
for (int i = 0; i < SZ(p) - 1; i++) {
  res += p[i] * (100 - p[i + 1]) / 1e4;
  res += (100 - p[i]) * p[i + 1] / 1e4;
  prod *= p[i] / 1e2;
}
prod *= p.back() / 1e2;
return res + prod;

Needed number of changes is just number of pairs of different adjacent digits or 1 in case if all symbols are 1 (in which case number of different adjacent digits is 0). Linearity of expectation and we are done.

→ Ответить

9 лет назад, # ^ |

I don't understand how that works. Do you have a prrof?

Sometimes I feel really stupid, like I have mental problems...

→ Ответить

niting112

9 лет назад, # ^ |

Hi,

Can you please provide the proof for:-

"Needed number of changes is just number of pairs of different adjacent digits or 1 in case if all symbols are 1"

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

+11

Count number of blocks of consecutive 0's/1's. In case you are doing a flip on prefix/suffix which ends inside a block — you will only increase number of blocks by 1 (by splitting this block into two); when your flip ends between blocks — you will decrease number of blocks by 1. Therefore you need X-1 operations to reach a state with single block starting from X blocks.

If you have at least 2 blocks — you can do moves in such a way that leftmost block is always 0's (by fliping either prefix or suffix), so you'll end up with a string consisting of all 0's. However, for a single block of 1's it does not work — you need that additional move to flip whole string.

→ Ответить

9 лет назад, # ^ |

Nice explanation.

Now I get it, and now I feel even more stupid because the problem was actually quite simple. I don't get how I can solve A,B,C in a Codeforces contest and then fail to solve 250 at TopCoder, when a lot of coders solve it in under 5 minutes... I also failed to solve problem A from last GCJ Round 2, which was VERY easy. Sometimes I feel like I am improving and then those things happen and everything crumbles...

→ Ответить

9 лет назад, # ^ |

← Rev. 6 →

-32

Horrendous in the same way most TopCoder problems are. TC was never characterized for having pretty problems, but it's become much worse lately. In the past, I remember some problems with a background that were fun to solve, like arranging furniture or planning a travel itinerary. Problems were disguised into some scenario/story, which gave you an incentive to approach them. Now, you don't find that anymore. All you find in the problem statements are numbers, conditions, formulas and a bunch of other technical stuff.

Codeforces problems are always presented nicely, with a background story and sometimes even with graphics, which makes them fun to solve. On the other hand, TopCoder problems are always like "You have this array a₁, a₂, ..., a_n, and you can perform operations like ... blah blah blah... calculate the expectancy of this or that", or "You have an undirected graph of n vertices and m edges, with the property that... blah blah blah... compute and return something". That's really boring. What's the incentive in tackling a problem if all you read in the statement is boring crap like that? I don't take part in contests to do that, if I were looking for algorithm exercises, then I'd go read a book.

→ Ответить

Zuza

9 лет назад, # ^ |

+41

Oh come on, the difference isn't THAT huge :)

"Vasya is buying tomatoes to make a vegan pizza and got challenged by Misha to help her solve a problem. Given an array a1, a2, ..., an Vasya can perform operations like ..... Help Vasya calculate the expectancy of ...."

→ Ответить

xorfire

9 лет назад, # ^ |

+30

If you ask me, I kind of hate Codeforces problems for the reason that it has these stories that distract you from the actual problem itself. You have to read the stories carefully to see if some important points are hidden. I prefer problems written more directly like Topcoder. I guess it depends on the person's likes. I can also retort by saying that if you were looking for kid stories, then read a "30 bedtime stories" book. The fun part is solving the problem. Your opinion doesn't make Codeforces problems nice and Topcoder problems horrendous.

Anyway, I know at least one other guy who loves these stories, so it is important in some sense too. And you can always stop taking part if you do not like it or just don't care about rating(by rage quitting whenever the contest pisses you off).

→ Ответить

TerryMcGinnis

9 лет назад, # ^ |

Yeah, Ragequitting was the way to go in this one. I knew this was going to be solved by linearity of expectation due to encountering a problem in GCJ and in my timezone, the round took place at 3:30 am, so sleep was out of the question since once I sleep, I dont wake up. :p I really dont care about the rating but getting a problem right means a lot to me. I just wanna improve! So, how did we arrive from 'Needed number of changes is just number of pairs of different adjacent digits or 1 in case if all symbols are 1 (in which case number of different adjacent digits is 0)' to the code given by Swistak?

Sometimes, even I feel really stupid, as if I have mental problems :p

→ Ответить

klamathix

9 лет назад, # ^ |

I think that more generally it's about a problem's "depth". It should either have a simple/natural statement, a novel solution or be meaningful mathematically. I think the 500 did a good job on this. It has an interesting statement, it introduces you to a very deep topic but by means of a clean algorithmic flavor :). For me the 250 wasn't very guilty of being artificial (I've seen much worse), however it is guilty of being yet another straightforward linearity of expectation problem, of which TopCoder does have a disproportionate amount. I really enjoy discovering new ways of solving expectation problems, but this wasn't the case.

But TopCoder shouldn't be singled out on the "depth-lacking" problem issue. I think they're doing rather well (although admittedly not as well as in the past). Basically everybody that hosts regular contests is bound to propose such problems. Codeforces has its fair share. At the end of the day, there are way too many contests relative to how many quality problems are developed out there :). Unsurprisingly the IOI, Code Jam (superior stages), TCO (superior stages), ACM-ICPC(minus the oh-so-frequent inhuman geometry), usually have the best problems, because they are rare events. While on the topic I'd like to give a shout out to Polish contests, which I think have awesome, really uncommon consistency in their quality :) And of course Petr Mitrichev contests, which are on such a different level difficulty-wise that they're almost irelevant in this general context :)

→ Ответить

I_Love_Michelle_Shen

9 лет назад, # ^ |

-30

Why this post gets so many downvotes? The problem was quite bad...

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

-36

Because no one likes it when you criticize something. It doesn't matter what you are criticizing or for what reason. It always gets downvoted. Looks like the world has to be flowers and rainbows for everyone...

→ Ответить

9 лет назад, # ^ |

← Rev. 3 →

+29

Note that you got upvoted for your post which explains why the problem is horrendous (regardless of whether people agreed with you). Your downvoted post didn't criticize anything, it just insulted.

EDIT: When I posted this, the explanation post was +8. At the time of this edit, it's -19. I don't know what to think.

→ Ответить

9 лет назад, # ^ |

← Rev. 3 →

-26

I got downvoted on every post I complained about Topcoder, whether I gave a reason or not. I made a post of around 20 lines explaining why I like Codeforces more than Topcoder and I got -20+ of downvotes, so it's not like you say. People just can't take someone complaining. They expect everyone to be happy about everything. In other words, they expect everyone to be false and demagogic. Well, that's not me. I'm authentic and straight, and if I don't like something, you'll certainly know.

Every.Single.Time I complain about anything here in Codeforces (or any other forum for the matter), people downvote me because they just can't tolerate someone complaining.

Well then, downvote me all you want, I don't care. I'll still complain about things I don't like, I won't say "Nice contest!" like everyone does when in fact I think the contest was pure shit. Go on Codeforces users, downvote me here again, like you always do.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

I'm a simple man. I see complains, I press downvote :P

Seriously — criticizing can be reasonable or not. It depends on your arguments and yours are pretty pathetic to be frank in this thread, so here are downvotes :P.

Here you have few examples of my comment when I criticized something and I got ~130-200 upvotes: http://mirror.codeforces.com/blog/entry/15725#comment-206492 http://mirror.codeforces.com/blog/entry/15725#comment-206530 http://mirror.codeforces.com/blog/entry/17548#comment-224303 and here you have an example of mine pretty stupid critical post, so I got 22 downvotes: http://mirror.codeforces.com/blog/entry/18222#comment-231317 :P

As you see it heavily depends on a matter of your comment and CF community (correctly) judgded that your comments are completely unjustified.

→ Ответить

9 лет назад, # ^ |

-38

I really don't think my arguments are pathetic. I'm just stating my preferences. When I solve a problem, I like to picture something in my mind, not just a bunch of numbers or points and lines.

Take for example this great problem: 497C - Distributing Parts . All it does is say the problem is about a musical, songs and actors. That alone makes me picture an auditorium, with actors rehearsing while a conductor gives directions. Only a few words can change a problem completely. If the statement said "Assign these pairs to the following integers so that each pair is assigned to at most k integers, the assigned integer lies inside the range of the pair and each integer is assigned to at most one pair. Maximize the number of assignments", then the problem would be really boring and tedious to solve. And in fact, the way it is, it's one of my favourite problems.

→ Ответить

ikbal

9 лет назад, # ^ |

If you want to hear some interesting stories then read books, competitive programming is not your place. Problems do not earn their reputation by some (imo time wasting) stories.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

-13

Well then, go tell that to IOI, ACM/ICPC, Google and Facebook, 'cause apparently they didn't get the memo...

ACM/ICPC: Catering, Weather Forecast, Ship Traffic

IOI: Gondolas, Rail, Holiday, Wall

Google Code Jam: Kiddie Pool, Smoothing Window, Drum Decorator

Facebook Hacker Cup: Fox Lochs, Fox Hawks, Gentrification, Lunch Scheduling

And that's just to name a few, because virtually a problem you come across in these major competitions has a background story, and sometimes a picture as well.

So, if you really want the problems to be just letters over a solid color background and a bunch of numbers and signs, please send a letter to each of those major institutions so they can start changing problem setters.

Or maybe you're just wrong and I'm right.......... I wonder.

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

-8

Yes, you're wrong, go and read some Harry Potter or whatever. If someone has a really nice story to tell then it's ok. I have to admit that I especially enjoyed story of problem about mispelling Dijkstra and quaternions from this year GCJ's qualifications — it was very hilarious for me. It is often case that a problem may originate from 'real life' situation, then it is also ok to put story. But when you have a problem on some weird expectation thingy or some operations needed to be handled on an array then it is perfectly fine to put no story rather than come up with some really weird story like "Dima has a birthday today. His friend Vasya gave him an array of 10⁶ integers as a gift. Now Dima wants to perform some operations on that array. Help him do that!".......

What matters the most is the algorithmical 'body' of the problem, not some silly character from description. If there is a nice/funny story attached to problem then it is nice, but that is definitely not a substantial factor when judging problem. Some worst cases include authors which badly wanted to come up with a story even though they haven't got any good idea and so put a long weird story which was hard to understand and caused much confusion.

→ Ответить

9 лет назад, # ^ |

-24

"Dima has a birthday today. His friend Vasya gave him an array of 106 integers as a gift. Now Dima wants to perform some operations on that array. Help him do that!"

That bullshit is not what I'm talking about! What the f**k do I care where the array comes from? It's still an array, for God's sake.

I'm saying give the problem some background. Take Kiddie Pool from GCJ Round 2, for example. Instead of water sources and a pool, the problem could have been written as just floating point numbers and averages, without any background, and it would have been boring as hell.

And it looks like some problem setters deliberately don't give the problems any background. The problem in question here (250 from last round) could have been easily transformed into a row of lights, each with 2 switches above that change the states of all lights to the left or to the right. Find a way to turn all the lights off with minimum number of switch presses. It's more interesting than "You have a binary string and the allowed operations are...$.

→ Ответить

9 лет назад, # ^ |

I think the best solution of that problem is that you should prepare a round for TC and write appriopriate stories for each problem :P.

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

Just curious: is reading a story your favorite and most enjoyable part of problem solving process? :)

→ Ответить

9 лет назад, # ^ |

← Rev. 2 →

-8

No, the most enjoyable part is finding and coding a solution while picturing the background of the problem in my mind. It's clearly not the same to solve a problem while you imagine a transportation system in a city than just picturing a lot of nodes and lines in your head. And not just because it's more fun (which certainly is), but also because a lot of times, picturing something more tangible and real in your head makes it easier to solve the problem.

→ Ответить

9 лет назад, # ^ |

So if it is easy to transform a problem to one with a story then do it by yourself (just as you did with that row of lights) and when you're unable then it means that it is troublesome to do so and problemsetter is justified :)

→ Ответить

Gnay_Oahnauhz

8 лет назад, # ^ |

You must be a smart guy. There's a saying that some smart people can view the problems encountered as vivid pictures.

→ Ответить

9 лет назад, # |

+61

I have to admit that I very enjoyed 500 problem. It is very rare to encounter topological problems (I think that this word fits well here).

→ Ответить