In previous years, I've at least gotten a few points on the small inputs in the qualifying round. Never enough to move on, but something. This year, I can't even figure out a semi-working algorithm for the very first problem.
I'm so frustrated after staring at it for 3 hours that I want to throw my computer across the room. Of course, then I'd be retarded AND I'd have a broken computer. At least right now I'm a retard with a functioning computer.
So what obvious solution am I missing?
Other urls found in this thread:
mathworld.wolfram.com
thecodelesscode.com
pastebin.com
twitter.com
Erm, if it makes you feel any better I've done these sort of contests before and this one isn't all that obvious how it's solved
How about you forget about these tedious, frustrating, esoteric problems and write something that solves a real problem.
No shame in giving up on a riddle. This says absolutely nothing about your programing or problem solving ability. Riddles and puzzles are often confusing, frustrating and tedious on purpose, it's meant to be entertaining for people who like overcoming those sort of challenges. Giving up on one, because you are not having fun, simply means that you are probably not on of those people.
Well, you've both honed in on what is bothering me the most about it, I guess. The concern that my inability to do this is, in fact, tied to my ability to solve problems and write useful software, in general. It's disheartening to look at the number of people who've solved this one already (4000+, last time I looked) and to think that most of them won't get very far, and I'm apparently not even in reach of their level. It's a sinking feeling, like being dolphin shit headed for the ocean floor.
Thank you both for your perspective.
Would be easier to understand with a drawing.
I made numerous "drawings". It didn't help.
What field of math does that problem fall under? Looks like combinatorics but I'm not sure.
tl;dr
This should help mathworld.wolfram.com
heres something from halfchan
>Master Foo and the Programming Prodigy
There was a time when rumors began to reach Master Foo and his students of a prodigiously gifted programmer, a young man who wandered the length and breadth of the land performing mighty feats of coding and humiliating all who dared set their skill against his.
Eventually this prodigy came to visit Master Foo, who received him politely and offered him tea. The Prodigy accepted with equal politeness and explained the motive for his visit.
“I have come to you,” he said “seeking a code and design review of my latest project. For it is of surpassing complexity, and I do not have peers capable of understanding it. Only an acknowledged master such as yourself (and here the Prodigy bowed deeply) can have the discernment required.”
Master Foo bowed politely in return and began examining the Prodigy's code. After some time he raised his eyes from the screen. “This code is at first sight very impressive,” he said. “It is elegant in design, utilizing original algorithms of great ingenuity, and appears to be implemented in a craftsmanlike way which minimizes the possibility of errors.”
The Prodigy looked very pleased at this praise, but Master Foo continued: “However, I detect one significant flaw.”
“Flaw?” the Prodigy said. “What flaw?”
“This code is difficult to read,” said Master Foo. “It is only thinly commented, its invariants are not specified, and I see no narrative description of its architecture or internal data structures anywhere. These problems will seriously impede your cooperation with other programmers.”
The Prodigy drew himself up haughtily. “I do not seek the cooperation of other programmers,” he said. “Every time I thought I had found one who might match me in skill I have been disappointed. Thus, I work alone.”
“But even the hacker who works alone,” said Master Foo, “collaborates with others, and must constantly communicate clearly to them, lest his work become confused and lost.”
“Of what others do you speak?” the Prodigy demanded.
Master Foo said: “All your future selves.”
Upon hearing this, the Prodigy was enlightened.
Is "from halfchan" the latest variant of "reinvented for ifunny" cancer? Just post the link to codelesscode you fucking pleb.
what are you literally even talking about
The fucking pleb newfag though it was fucking halfchan OC! My fucking sides are in orbit.
I honestly developed PTSD from cloudflare. If I see "Attention" in my tab, I always just immediately close it. I also get triggered by the word "Attention" and get vivid memories of infinite captcha hell with slowly loading blurry pictures.
You think I could sue them for causing me mental distress?
Currently in the same boat as you. I made it past qualifying round without breaking a sweat before, but this one's just something else.
i gave up btw
Can you post a better link or copy and paste your google poozle directly into this thread? I'm the best poozle solver in the world but I can't help you because pastebin blocks tor.
No, that's a stupid meme for people who jack off about camelCase vs under_scores. (see @ Parkinson's law of triviality)
People who can write software which works 100% _ARE_ writing software the _right way_!
People forget that writing software is only a means to an end, not an end in itself -- they are also likely to delude themselves into thinking they're doing work by splitting up one contiguous chunk of code into fragments within 10 different files... write programs to SOLVE THINGS, not to jack off about design patterns or whatever the fuck.
Pick one. Design patterns matter because code is meant to be read by humans so they can fix and extend the functionality.
why not both? i enjoying writing code as if it's a poem even if that has no effect on whether the code achieves the goal or not.
Looks like it can be solved with a tree search approach (Most likely not a very good approach, mind you) where each node stores the state of the pancakes and the branches from it represent each possible action. Since you can get repeated states you could extend it into a graph search to figure out all the actions and whether there's a solution.
This sounds like an intro to AI problem.
Alright well I lied. I went back and happened to solve both the small and large data sets. Turns out it was the easiest one.
int counter = 0;
for (int m = 0; m < state.length() - K + 1; m++) {
if (state.charAt(m) == '-') {
state = flip(state, m, K);
counter++;
}
}
where state is the initial layout of the pancakes, K is the size of the "flipper", and the flip method simply changes + to - and - to + from index m to m+K in the state string.
That doesn't look like it would work it out in the minimum number of flips.
i didn't think it would work either but it did fine in both sets
Problem
Last year, the Infinite House of Pancakes introduced a new kind of pancake. It has a happy face made of chocolate chips on one side (the "happy side"), and nothing on the other side (the "blank side").
You are the head cook on duty. The pancakes are cooked in a single row over a hot surface. As part of its infinite efforts to maximize efficiency, the House has recently given you an oversized pancake flipper that flips exactly K consecutive pancakes. That is, in that range of K pancakes, it changes every happy-side pancake to a blank-side pancake, and vice versa; it does not change the left-to-right order of those pancakes.
You cannot flip fewer than K pancakes at a time with the flipper, even at the ends of the row (since there are raised borders on both sides of the cooking surface). For example, you can flip the first K pancakes, but not the first K - 1 pancakes.
Your apprentice cook, who is still learning the job, just used the old-fashioned single-pancake flipper to flip some individual pancakes and then ran to the restroom with it, right before the time when customers come to visit the kitchen. You only have the oversized pancake flipper left, and you need to use it quickly to leave all the cooking pancakes happy side up, so that the customers leave feeling happy with their visit.
Given the current state of the pancakes, calculate the minimum number of uses of the oversized pancake flipper needed to leave all pancakes happy side up, or state that there is no way to do it.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with a string S and an integer K. S represents the row of pancakes: each of its characters is either + (which represents a pancake that is initially happy side up) or - (which represents a pancake that is initially blank side up).
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is either IMPOSSIBLE if there is no way to get all the pancakes happy side up, or an integer representing the the minimum number of times you will need to use the oversized pancake flipper to do it.
Limits
1 ≤ T ≤ 100.
Every character in S is either + or -.
2 ≤ K ≤ length of S.
Small dataset
2 ≤ length of S ≤ 10.
Large dataset
2 ≤ length of S ≤ 1000.
Sample
Input
3
---+-++- 3
+++++ 4
-+-+- 4
Output
Case #1: 3
Case #2: 0
Case #3: IMPOSSIBLE
In Case #1, you can get all the pancakes happy side up by first flipping the leftmost 3 pancakes, getting to ++++-++-, then the rightmost 3, getting to ++++---+, and finally the 3 pancakes that remain blank side up. There are other ways to do it with 3 flips or more, but none with fewer than 3 flips.
In Case #2, all of the pancakes are already happy side up, so there is no need to flip any of them.
In Case #3, there is no way to make the second and third pancakes from the left have the same side up, because any flip flips them both. Therefore, there is no way to make all of the pancakes happy side up.
Now that the qualifying round is over, would you be willing to share your full solution?
that's the entire thing
rest is just io stuff
Here are a couple hints:
1. Think about all possible positions of the pan.
2. The order of flips don't matter.
3. For every position, it only matters whether you flipped the pan or not. (flipping twice does nothing)
4. Start from the leftmost pancake. How many pan positions can affect that pancake? Once that is settled, how about the next one?
I posted this!