Page 2 of 2

Re: 732 - Anagrams by Stack

Posted: Wed Jul 23, 2008 12:24 am
by x140l31
can anyone help me?

I'm getting always RTE :cry:

Code: Select all

#include <iostream>
#include <string>
#include <vector>
using namespace std;

typedef vector<int> VI;

void process(string sw, string tw, VI &slet, string stack, string seq, int a, int b)
{
    if (b == tw.size())
    {
        seq = seq.substr(1);
        cout << seq << endl;
    }
    else
    {
        if (slet[tw[b] - 'a'] > 0)
        {
            slet[sw[a] - 'a']--;
            process(sw, tw, slet, stack + sw[a], seq + " i", a + 1, b);
            slet[sw[a] - 'a']++;
        }
        int stam = stack.size();
        if (stam > 0 and stack[stam - 1] == tw[b])
            process(sw, tw, slet, stack.substr(0, stam - 1), seq + " o", a, b + 1);
    }
}

int main()
{
    string sw, tw;
    while (cin >> sw >> tw)
    {
        cout << '[' << endl;
        if (sw.size() == tw.size())
        {
            VI slet(26, 0), tlet(26, 0);
            for (int i = 0; i < sw.size(); i++) slet[sw[i] - 'a']++;
            for (int i = 0; i < tw.size(); i++) tlet[tw[i] - 'a']++;
            bool valid = true;
            for (int i = 0; i < 26 and valid; i++)
                valid = valid and (slet[i] == tlet[i]);
            if (valid) process(sw, tw, slet, "", "", 0, 0);
        }
        cout << ']' << endl;
    }
}
I don't know in witch case it can crash... :(

Re: 732 - Anagrams by Stack

Posted: Thu Apr 09, 2015 4:12 pm
by anacharsis
This is one where the UDebug output differs from AC judge output.
The UDebug solution ignores empty lines entirely; you can't do that - if you do, you'll WA

Input:

Code: Select all

d_g
g_d

f

f
aaaabbb
ababaab
UDebug Output:

Code: Select all

[
i i i o o o
]
[
i o
]
[
i i i i o i o o i o o o i o
i i i o i i o o i o o o i o
i i o i i i o o i o o o i o
i o i i i i o o i o o o i o
]
AC output:

Code: Select all

[
i i i o o o
]
[
]
[
]
[
i i i i o i o o i o o o i o
i i i o i i o o i o o o i o
i i o i i i o o i o o o i o
i o i i i i o o i o o o i o
]
It took me a long time to figure this out, so please use this information!! :)

Re: 732 - Anagrams by Stack

Posted: Fri Aug 21, 2015 7:50 am
by RedGreenCode
I wrote an editorial about optimizing a Java solution to this problem to get it to run in under the time limit: http://www.redgreencode.com/implementin ... o-uva-732/