259 - Software Allocation

All about problems in Volume II. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Re: Runtime Error

Postby K0stIa » Fri Sep 24, 2010 6:04 pm

helloneo wrote:
Is that valid input..?
My AC code returns "_AB_______" :(

Anyway, your approach look correct..
But, your code is missing '\n' after the last case.. (when the output of the last case is not '!')


So, it's still WA :( I'm very disappointed. Can u show me ur code ? I don't understand what wrong with it :(

And, if there multi answer allowed, what kind of case I should to choose for my answer ?

And, what do u think about next test?
A1 2;
C1 1;
B1 12;
B1 1234;

According to the UVA toolkit the answer must be equal to "_CABB_____";
now I'm going to research this test case more deeply.

User 1 comes to solve him one problem "A", he can to do it only on 2nd computer,
then user 2 has one problem "C" and he can solve it only on first computer,
user 3, have one problem B , and cans solve it only on first r second machine,
user 4, as user 3, also has the same "B", but he can solve it on 1,2,3,4 computers.

according to the uva toolkits answer user 3 can solves his problem on computer 3 & 4 also, it looks naturally if user 3 and 4 has problems identical "B".
Ok, lets try to look on the next two test cases:

A1 2;
C1 1;
V1 234;
B1 2345;
B1 3;

and

A1 2;
C1 1;
V1 23;
B1 2345;
B1 3;

Who can explain to me why first has answer "_CABVB____" and second has "_CAVBB____" according to the UVA toolkit?

Who has solved this damned PROBLEM ?

So, i'm interested in input data from the UVA server, how i can get it ?
K0stIa
New poster
 
Posts: 4
Joined: Thu Sep 23, 2010 10:20 pm

Re: 259 - optimizing..

Postby helloneo » Mon Sep 27, 2010 11:31 pm

I PMed you..

Don't go deeper.. There are many other good problems.. :)
helloneo
Guru
 
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 259 - optimizing..

Postby AhmadKhatar » Fri Jul 20, 2012 5:56 pm

Hi!
Does any body know where my mistake is?
I spent a lot of time but I couldn't find it! :(
Thanks in advance! :D
Code: Select all
#define SOURCE 36
#define SINK 37
#define FIRSTCMP 26

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <queue>
using std::queue;

#include <string>
using std::string;

using std::min;

int f [ 38 ][ 38 ]; // 0..25 are chars, 26..35 are computers, 36 is source, 37 is sink,
int p [ 38 ];
int totalWorks;

void process();
int bfs();

int main()
{
   char tempL [ 15 ];

   // initialize
   for ( int i = 0; i < 38; i++ )
   {
      for ( int j = 0; j < 38; j++ )
      {
         f[ i ][ j ] = 0;
      }
   }

   totalWorks = 0;


   while ( cin.getline( tempL, 15, '\n' ) )
   {
      if ( tempL[ 0 ] == NULL )
      {
         process();

         // refresh
         for ( int i = 0; i < 38; i++ )
         {
            for ( int j = 0; j < 38; j++ )
            {
               f[ i ][ j ] = 0;
            }
         }

         totalWorks = 0;
      }
      else
      {
         totalWorks += tempL[ 1 ] - 48;
         int lastGoodInd = 3;
         for ( int i = 4; tempL[ i ] != ';'; i++ )
         {
            lastGoodInd++;
         }

         f[ SOURCE ][ ( tempL[ 0 ] - 65 ) ] = tempL[ 1 ] - 48;
         for ( int i = 3; i <= lastGoodInd; i++ )
         {
            f[ ( tempL[ 0 ] - 65 ) ][ FIRSTCMP + tempL[ i ] - 48 ] = tempL[ 1 ] - 48; // here we could assign to 1
            f[ FIRSTCMP + tempL[ i ] - 48 ][ SINK ] = 1;
         }
      }
   }

   return 0;
}

void process()
{
   string toOut = "__________";
   
   int maxFlow = 0;
   int incPath;
   while ( bfs() != 0 )
   {
      incPath = -1;
      for ( int i = SINK; i != SOURCE; i = p[ i ] )
      {
         if ( incPath == -1 )
         {
            incPath = f[ p[ i ] ][ i ];
         }
         else
         {
            incPath = min( incPath, f[ p[ i ] ][ i ] );
         }
      }

      for ( int i = SINK; i != SOURCE; i = p[ i ] )
      {
         f[ p[ i ] ][ i ] -= incPath;
         f[ i ][ p[ i ] ] += incPath;
      }

      maxFlow += incPath;
   }

   if ( maxFlow < totalWorks )
   {
      cout << "!" << endl;
   }
   else
   {
      for ( int i = 0; i <= 25; i++ )
      {
         for ( int j = 26; j <= 35; j++ )
         {
            if ( f[ j ][ i ] == 1 ) // NOTE THAT here f[ i ][ j ] == 0 doesn't work
            {
               toOut[ j - 26 ] = static_cast<char>( ( i % 26 ) + 65 );
            }
         }
      }

      cout << toOut << endl;
   }
}

int bfs() // returns sink plus the augmenting path
{
   int curNode;
   queue<int> q;
   int color[ 38 ];
   
   for ( int i = 0; i < 38; i++ )
   {
      color[ i ] = 0; // 0 is white, 1 is gray
      p[ i ] = -1;
   }

   q.push( SOURCE );
   color[ SOURCE ] = 1;

   while (!q.empty())
   {
      curNode = q.front();
      q.pop();

      for ( int i = 0; i < 38; i++ )
      {
         if ( f[ curNode ][ i ] > 0 && color[ i ] == 0 )
         {
            p[ i ] = curNode;
            color[ i ] = 1;
            if ( i == SINK )
            {
               return SINK; // a positive integer
            }
            q.push( i );
         }
      }
   }

   return 0; // because no vertex has value 0 (vertex numbers start from 1) no problem is with 0
}
AhmadKhatar
New poster
 
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 259 - optimizing..

Postby brianfry713 » Sat Jul 21, 2012 12:54 am

Doesn't match the sample I/O.
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5517
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - optimizing..

Postby AhmadKhatar » Sat Jul 21, 2012 5:18 am

Hi!
Perhaps I'm wrong, but the sample output and my output are equal! :-?
AhmadKhatar
New poster
 
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 259 - optimizing..

Postby brianfry713 » Mon Jul 23, 2012 11:22 pm

You're missing the !
http://ideone.com/QTMIa
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5517
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - optimizing..

Postby AhmadKhatar » Tue Jul 24, 2012 2:52 am

Thanks!
But your input needs another new line!
AhmadKhatar
New poster
 
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 259 - optimizing..

Postby brianfry713 » Tue Jul 24, 2012 10:59 pm

I don't think so. Try to make your code work either way.
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5517
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - optimizing..

Postby AhmadKhatar » Tue Jul 24, 2012 11:17 pm

Thanks! :D
You were right! Newline should be between inputs not after each of them.
AhmadKhatar
New poster
 
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 259 - optimizing..

Postby vsha041 » Mon Mar 31, 2014 9:02 am

Any one can get runtime error because input may be like

A1 13579;
B1 a-123;

Handle this i got accepted other wise i got runtime error.


There is no test case like this in the judge's input. Input format isn't tricky either. I use cin and cout to read/write input/output.
vsha041
New poster
 
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

259 WA

Postby moxlotus » Tue Aug 12, 2014 6:18 pm

Getting WA on this problem.
Can someone provide me with some tricky corner case? or is there something abt the output format that i m missing here?
Totally can't figure out whats wrong with my code :(

AC
Last edited by moxlotus on Fri Aug 15, 2014 11:34 am, edited 1 time in total.
moxlotus
New poster
 
Posts: 18
Joined: Sat Sep 17, 2011 6:47 am

Re: 259 - Software Allocation

Postby brianfry713 » Tue Aug 12, 2014 9:11 pm

Next time post in the existing thread.

Input:
Code: Select all
A9 2;
B1 3;

A1 78;
B3 012345689;

A8 169;

A2 89;
B2 0127;

A2 7;

A2 012346789;

A1 2;
B1 169;

A3 125689;

A2 123456789;
B1 02456789;
C5 0124569;
D2 012345789;

A6 01345;
B2 01235689;


A7 01234678;
B3 15;
C1 3579;

A1 0123456789;

A2 029;
B1 12589;
C1 8;
D1 0149;

A3 1678;

A6 03678;

A1 038;
B1 69;

A: 02369;
B1 03456789;

A5 16789;
B1 024567;
C3 013678;

A4 0123456789;
B1 0134568;
C2 123479;
AC output:
Code: Select all
!
BBB____A__
!
BB______AA
!
AA________
_BA_______
_AA__A____
CAADCCCDBC
!
__________
!
A_________
ABA_D___C_
_A____AA__
!
A_____B___
!
!
AAAAB__C_C
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5517
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - Software Allocation

Postby moxlotus » Fri Aug 15, 2014 6:36 am

Thanks Brian.
Didnt want to spawn a new thread but there is alrdy so many around i dunno which is a better one to append to. xD
moxlotus
New poster
 
Posts: 18
Joined: Sat Sep 17, 2011 6:47 am

Re: 259 - Software Allocation

Postby brianfry713 » Fri Aug 15, 2014 8:08 pm

I merged all of the "Help on the Problemset" threads about this problem into this one.
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5517
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Previous

Return to Volume II

Who is online

Users browsing this forum: No registered users and 1 guest